4430
правок
Быстрая минимальная триангуляция: различия между версиями
Материал из WEGA
Быстрая минимальная триангуляция (посмотреть исходный код)
Версия от 15:15, 13 мая 2014
, 13 мая 2014→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 35: | Строка 35: | ||
Добавить столбец в M, такой, что M(v, C) = 1 для всех вершин <math>v \in N_H(C)</math>; | Добавить столбец в 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''' | '''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>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>; | Вычислить <math>MM^T \; </math>; | ||
Добавить к | Добавить к G' дуги, обозначенные ненулевыми элементами <math>MM^T \; </math>; | ||
'''while''' <math>Q_3</math> непусто '''do''' | |||
Алгоритм быстрой минимальной триангуляции | |||
Извлечь множество вершин <math>A из Q_3</math>; | |||
'''if''' G'[A] неполно '''then''' Поместить G'[A] в '''Q_2'''; | |||
Поменять местами имена <math>Q_1</math> и <math>Q_2</math>; | |||
'''until''' <math>Q_1</math> пусто | |||
Рис. 1. Алгоритм быстрой минимальной триангуляции | |||
== Основные результаты == | == Основные результаты == | ||
