Главная
Новости
Строительство
Ремонт
Дизайн и интерьер




18.04.2021


18.04.2021


18.04.2021


18.04.2021


18.04.2021





Яндекс.Метрика

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

26.09.2021

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

Определение. Функция ϕ ( V ) {displaystyle phi (V)} называется обобщённой (строгой) развёрткой ориентированного графа G = ( V , E ) {displaystyle G=(V,E)} , если ∀ e ∈ E {displaystyle forall ein E} , идущей от v 1 {displaystyle v_{1}} к v 2 {displaystyle v_{2}} выполняется неравенство ϕ ( v 1 ) ≤ ϕ ( v 2 ) ( ϕ ( v 1 ) < ϕ ( v 2 ) ) {displaystyle phi (v_{1})leq phi (v_{2})(phi (v_{1})<phi (v_{2}))} .

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

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

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