4446
правок
Быстрая минимальная триангуляция: различия между версиями
Перейти к навигации
Перейти к поиску
Быстрая минимальная триангуляция (посмотреть исходный код)
Версия от 00:35, 14 мая 2014
, 14 мая 2014→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 90: | Строка 90: | ||
'''if''' <math>E_{\bar H}(U \mathcal{n} N_H[C_k \cup \{ u \} ]) \ge \frac{2}{5} | \bar E (H)|</math> '''then''' | '''if''' <math>E_{\bar H}(U \mathcal{n} N_H[C_k \cup \{ u \} ]) \ge \frac{2}{5} | \bar E (H)|</math> '''then''' | ||
<math>C_k = C_k \cup \{ v \} \; </math>; пометить v как c-вершину (вершину компонента); | |||
'''else''' | |||
Алгоритм разбиения. Пусть | |||
Пометить v как p-вершину (вершину потенциально максимальной клики); Ассоциировать v с <math>C_k \; </math>; | |||
k = k + 1; | |||
P = множество всех p-вершин и s-вершин; | |||
''Часть II: определение A'' | |||
'''if''' <math>H[U \mathcal{n} P] \; </math> содержит полную компоненту C '''then''' <math>A = N_H [C] \; </math>; | |||
'''else if''' существуют две несмежные вершины u, v, такие, что u является s-вершиной, а v является s-вершиной или p-вершиной '''then''' <math>A = N_H [u] \; </math>; | |||
'''else if''' существуют две несмежные p-вершины u и v, где u ассоциирована с <math>C_i \; </math>, а v ассоциирована с <math>C_j \; </math>, <math>u \notin N_H (C_j) \; </math> и <math>v \notin N_H (C_i) \; </math> '''then''' <math>A = N_H [C_i \cup \{ u \}] \; </math>; | |||
'''else''' A = P; | |||
Рис. 2. Алгоритм разбиения. Пусть <math>\bar E_H = W \; </math>, где <math>uv \in W \; </math>, если <math>uv \notin D \; </math> – множество антидуг H. Определим £/j(S) как сумму степеней H = (U, Ё) вершин S с U = V(H) | |||