- Развёртка графа
-
Для улучшения этой статьи желательно?: - Проставить интервики в рамках проекта Интервики.
- Найти и оформить в виде сносок ссылки на авторитетные источники, подтверждающие написанное.
Развёртка графа — функция, заданная над вершинами ориентированного графа и удовлетворяющая ряду условий.
Определение. Функция называется обобщённой (строгой) развёрткой ориентированного графа , если , идущей от к выполняется неравенство .
Интересным свойством строгой развёртки является то, что она задаёт собой ярусно-параллельную форму графа, причем ярусами в такой ЯПФ являются поверхности уровня развёртки.
Известно, что у любого фрагмента алгоритма существует по крайней мере одна кусочно-линейная обобщённая развертка.
Строгие и обобщённые развёртки графа алгоритма используются для эффективного распараллеливания алгоритма по методике В. В. Воеводина.
Категории:- Теория графов
- Параллельные вычисления
Wikimedia Foundation. 2010.