4551
правка
Быстрая минимальная триангуляция: различия между версиями
Материал из WEGA
Быстрая минимальная триангуляция (посмотреть исходный код)
Версия от 15:07, 13 мая 2014
, 13 мая 2014→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 11: | Строка 11: | ||
Алгоритм быстрой минимальной триангуляции FMT. Дано: произвольный граф G = (V, E). Требуется: найти минимальную триангуляцию G' графа G. | '''Алгоритм быстрой минимальной триангуляции FMT.''' | ||
'''Дано:''' произвольный граф G = (V, E). | |||
'''Требуется:''' найти минимальную триангуляцию G' графа G. | |||
Пусть <math>Q_1</math>, <math>Q_2</math> и <math>Q_3</math> – пустые очереди; поместить G в <math>Q_1</math>; G' = G; | Пусть <math>Q_1</math>, <math>Q_2</math> и <math>Q_3</math> – пустые очереди; поместить G в <math>Q_1</math>; G' = G; | ||
'''repeat''' | '''repeat''' | ||
Создать нулевую матрицу M со строкой для каждой вершины из V (столбцы будут добавлены позднее); while | |||
Извлечь граф H = (U | Создать нулевую матрицу M со строкой для каждой вершины из V (столбцы будут добавлены позднее); | ||
Вызвать процедуру Algorithm Partition(H), возвращающую подмножество вершин A | |||
Поместить множество вершин A в | '''while''' <math>Q_1</math> непусто '''do''' | ||
for каждой связной компоненты C из H[ | |||
Добавить столбец в M, такой, что M(v, C) = 1 для всех вершин v | Извлечь граф H = (U, D) из <math>Q_1</math>; | ||
Поместить | |||
Вызвать процедуру '''Algorithm Partition'''(H), возвращающую подмножество вершин <math>A \subset U \; </math>; | |||
Поместить множество вершин A в <math>Q_3</math>; | |||
'''for''' каждой связной компоненты C из H[U\A] '''do''' | |||
Добавить столбец в M, такой, что M(v, C) = 1 для всех вершин <math>v \in N_H(C)</math>; | |||
'''if''' существует антидуга uv в <math>H[N_H[C]]</math>, такая, что <math>u \in C</math> '''then''' | |||
Поместить <math>H_C = (N_H[C], D_C) \; </math> в <math>Q_2</math>, где <math>uv \notin D_C \; </math>, если <math>u \in C</math> и <math>uv \notin D</math>; | |||
Вычислить <math>MM^T</math>; | |||
Добавить к G0 дуги, обозначенные ненулевыми элементами MMT; while Q3 непусто do | Добавить к G0 дуги, обозначенные ненулевыми элементами MMT; while Q3 непусто do | ||
Извлечь множество вершин A из Q3; | Извлечь множество вершин A из Q3; | ||
