4551
правка
Быстрая минимальная триангуляция: различия между версиями
Перейти к навигации
Перейти к поиску
Быстрая минимальная триангуляция (посмотреть исходный код)
Версия от 00:22, 14 мая 2014
, 14 мая 2014→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 68: | Строка 68: | ||
Алгоритм разбиения Partition | '''Алгоритм разбиения Partition''' | ||
Дано: | |||
Часть I: определение P | '''Дано:''' граф H = (U, D) (подзадача, извлеченная из <math>Q_1</math>). | ||
Снять отметки со всех вершин H; k = 1; | |||
while существует непомеченная вершина u do | '''Требуется:''' найти подмножество A множества U, такое, что либо A = N[K] для некоторого связного H[K], либо A является потенциально максимальной кликой H (и G'). | ||
if | |||
'''Часть I: определение P''' | |||
Снять отметки со всех вершин H; k = 1; | |||
'''while''' существует непомеченная вершина u '''do''' | |||
'''if''' <math>E_{\bar H}(U \mathcal{n} N_H[u]) < \frac{2}{5} | \bar E (H)|</math> '''then''' пометить u как s-вершину (стоп-вершину); | |||
'''else''' | |||
Ck = fug; пометить u как c-вершину (вершину компонента); | Ck = fug; пометить u как c-вершину (вершину компонента); | ||
while существует вершина v 2 NH[ Q ], непомеченная или помеченная как s-вершина do | while существует вершина v 2 NH[ Q ], непомеченная или помеченная как s-вершина do | ||
if Ta(U\NH[CkU{v}]) > f|£(H)| then | if Ta(U \mathcal{n} NH[CkU{v}]) > f|£(H)| then | ||
Ck = C U {v}; пометить v как c-вершину (вершину компонента); else | Ck = C U {v}; пометить v как c-вершину (вершину компонента); else | ||
Пометить v как p-вершину (вершину потенциально максимальной клики); Ассоциировать v с Ck; k = k + 1; P = множество всех p-вершин и s-вершин; | Пометить v как p-вершину (вершину потенциально максимальной клики); Ассоциировать v с Ck; k = k + 1; P = множество всех p-вершин и s-вершин; | ||
Часть II: определение A | Часть II: определение A | ||
if H[U n P] содержит полную компоненту C then A = NH[C]; | if H[U \mathcal{n} P] содержит полную компоненту C then A = NH[C]; | ||
else if существуют две несмежные вершины u, v, такие, что u является s-вершиной, а v является s-вершиной или p-вершиной then A = NH [ u ]; | else if существуют две несмежные вершины u, v, такие, что u является s-вершиной, а v является s-вершиной или p-вершиной then A = NH [ u ]; | ||
else if существуют две несмежные p-вершины u и v, где u ассоциирована с C, а v ассоциирована с Cj, u 62 NH(CJ) и V 2 6NH(Ci) then A = NH[Ci[f u g]; | else if существуют две несмежные p-вершины u и v, где u ассоциирована с C, а v ассоциирована с Cj, u 62 NH(CJ) и V 2 6NH(Ci) then A = NH[Ci[f u g]; | ||