Развёртка графа
Материал из Википедии — свободной энциклопедии
Развёртка графа — функция, заданная над вершинами ориентированного графа и удовлетворяющая ряду условий.
Определение. Функция φ(V) называется обобщённой (строгой) развёрткой ориентированного графа G = (V,E), если 
, идущей от v1 к v2 выполняется неравенство 
.
Интересным свойством строгой развёртки является то, что она задаёт собой ярусно-параллельную форму графа, причем ярусами в такой ЯПФ являются поверхности уровня развёртки.
Известно, что у любого фрагмента алгоритма существует по крайней мере одна кусочно-линейная обобщённая развертка.
Строгие и обобщённые развёртки графа алгоритма используются для эффективного распараллеливания алгоритма по методике В. В. Воеводина.
