Развёртка графа

Развёртка графа — функция, заданная над вершинами ориентированного графа и удовлетворяющая ряду условий.

Определение. Функция [math]\displaystyle{ \phi (V) }[/math] называется обобщённой (строгой) развёрткой ориентированного графа [math]\displaystyle{ G = (V, E) }[/math], если [math]\displaystyle{ \forall e \in E }[/math], идущей от [math]\displaystyle{ v_1 }[/math] к [math]\displaystyle{ v_2 }[/math] выполняется неравенство [math]\displaystyle{ \phi (v_1) \le \phi (v_2)( \phi (v_1) \lt \phi (v_2) ) }[/math].

Интересным свойством строгой развёртки является то, что она задаёт собой ярусно-параллельную форму графа, причём ярусами в такой ЯПФ являются поверхности уровня развёртки.

Известно, что у любого фрагмента алгоритма существует по крайней мере одна кусочно-линейная обобщённая развертка.

Строгие и обобщённые развёртки графа алгоритма используются для эффективного распараллеливания алгоритма по методике В. В. Воеводина.