Русская Википедия:Развёртка графа

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

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

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

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

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

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

Шаблон:Rq