Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

Розгортка графа



Розгортка графа - функція, задана над вершинами орієнтованого графа і яка задовольнить ряду умов.

Визначення. Функція φ (V) називається узагальненої (суворої) розгорткою орієнтованого графа G = (V, E) , Якщо \ Forall e \ in E , Яка від v 1 до v 2 виконується нерівність \ Phi (v_1) \ le \ phi (v_2) (\ phi (v_1) <\ phi (v_2)) .

Цікавою властивістю суворої розгортки є те, що вона задає собою ярусно-паралельну форму графа, причому ярусами в такій ЯПФ є поверхні рівня розгортки.

Відомо, що у будь-якого фрагменту алгоритму існує принаймні одна кусочно-лінійна узагальнена розгортка.

Суворі та узагальнені розгортки графа алгоритму використовуються для ефективного розпаралелювання алгоритму за методикою В. В. Воєводіна.


Цей текст може містити помилки.

Схожі роботи | скачати

Схожі роботи:
Розгортка
Прогресивна розгортка
Інваріант графа
Доповнення графа
Розбиття графа
Компонента зв'язності графа
Притчі графа дифузора
Визначення Святійшого Синоду про графа Льва Толстого
© Усі права захищені
написати до нас
Рейтинг@Mail.ru