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

Для множества вершин <math>A \subset V</math> подграф G, порожденный A, соответствует <math>G[A] = (A, W) \; </math>, где <math>uv \in W \; </math>, если <math>u, v \in A \; </math> и <math>uv \in E \} \; </math>. Замкнутой окрестностью A является <math>N[A] = U \; </math>, где <math>u, v \in U \; </math> для каждой <math>uv \in E \; </math>, где <math>u \in A \} \; </math> и <math>N(A) = N[A]\A \; </math>. A называется [[клика|кликой]], если G[A] является полным графом. Множество вершин <math>S \in V \; </math> называется разделителем вершин, если G[V n S] является несвязным; S называется минимальным разделителем вершин, если существует пара вершин a, b 2 VnS, такая, что a и b содержатся в разных компонентах связности G[V n S] и в одной и той же компоненте связности G[V n S0] для любого S0 С S. Множество вершин Q С V является потенциально максимальной кликой, если не существует компоненты связности G[V n Q], содержащей Q в своей окрестности, и для каждой пары вершин u, v 2 Q имеется дуга uv или существует компонента связности G[V n Q], содержащая в своей окрестности одновременно u и v. Принимая во внимание результаты из [1] и [7], получаем следующий рекурсивный алгоритм минимальной триангуляции. Найти множество вершин A, являющееся либо минимальным разделителем, либо потенциально максимальной кликой. Дополнить G[A] до клики. Рекурсивным образом для каждой компоненты связности C из G[V n A], где G[N[C]] не является кликой, найти минимальную триангуляцию G[N[C]]. Важное свойство алгоритма заключается в том, что множество компонент связности G[VnA] определяет независимые задачи минимальной триангуляции.