Быстрая минимальная триангуляция: различия между версиями

Перейти к навигации Перейти к поиску

Быстрая минимальная триангуляция (посмотреть исходный код)

Версия от 15:07, 13 мая 2014

368 байт добавлено ,  13 мая 2014
→‎Постановка задачи
Строка 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 Q1 непусто do
 
Извлечь граф H = (U; D) из Q1;
  Создать нулевую матрицу M со строкой для каждой вершины из V (столбцы будут добавлены позднее);
Вызвать процедуру Algorithm Partition(H), возвращающую подмножество вершин A С U;
 
Поместить множество вершин A в Q3;
  '''while''' <math>Q_1</math> непусто '''do'''
for каждой связной компоненты C из H[Un A] do
 
Добавить столбец в M, такой, что M(v, C) = 1 для всех вершин v 2 NH(C); if существует антидуга UV в H[NH[C]] с u 2 C then
      Извлечь граф H = (U, D) из <math>Q_1</math>;
Поместить HC = (NH[C]; DC) в Q2, где MV ^ DC если u 2 C и MV ^ D; Вычислить MMT;
 
      Вызвать процедуру '''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;
Irina
4430

правок

Источник — http://pco.iis.nsk.su/wega/index.php/Служебная:Сравнение_версий/10611

Навигация