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

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

Определение. Функция $\varphi (V)$ называется обобщённой (строгой) развёрткой ориентированного графа $G=(V,E)$, если $\mathrm{\forall }e\in E$, идущей от $v_1$ к $v_2$ выполняется неравенство $\varphi (v_1)\le \varphi (v_2)(\varphi (v_1)<\varphi (v_2))$.

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

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

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