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

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

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

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

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

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

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


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Смотреть что такое "Развертка графа" в других словарях:

  • Развёртка графа — Для улучшения этой статьи желательно?: Проставить интервики в рамках проекта Интервики. Найти и оформить в виде сносок ссылки на авторитетные источники, подтверждающие написанное …   Википедия

  • Нерешённые проблемы математики — Нерешённые проблемы (или Открытые проблемы)  проблемы, которые рассматривались математиками, но до сих пор не решены. Часто принимают форму гипотез, которые предположительно верны, но нуждаются в доказательстве. В научном мире популярна практика… …   Википедия

  • Нерешенные проблемы математики — Нерешённые проблемы (или Открытые проблемы)  проблемы, которые рассматривались математиками, но до сих пор не решены. Часто принимают форму гипотез, которые предположительно верны, но нуждаются в доказательстве. В научном мире популярна практика… …   Википедия

  • Нерешенные проблемы теории чисел — Нерешённые проблемы (или Открытые проблемы)  проблемы, которые рассматривались математиками, но до сих пор не решены. Часто принимают форму гипотез, которые предположительно верны, но нуждаются в доказательстве. В научном мире популярна практика… …   Википедия

  • Нерешённые проблемы теории чисел — Нерешённые проблемы (или Открытые проблемы)  проблемы, которые рассматривались математиками, но до сих пор не решены. Часто принимают форму гипотез, которые предположительно верны, но нуждаются в доказательстве. В научном мире популярна практика… …   Википедия

  • Функциональное программирование — Парадигмы программирования Агентно ориентированная Компонентно ориентированная Конкатенативная Декларативная (контрастирует с Императивной) Ограничениями Функциональная Потоком данных Таблично ориентированная (электронные таблицы) Реактивная …   Википедия

  • Парадигма — (Paradigm) Определение парадигмы, история возникновения парадигмы Информация об определении парадигмы, история возникновения парадигмы Содержание Содержание История возникновения Частные случаи (лингвистика) Управленческая парадигма Парадигма… …   Энциклопедия инвестора


Поделиться ссылкой на выделенное

Прямая ссылка:
… Нажмите правой клавишей мыши и выберите «Копировать ссылку»