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

Для множества вершин <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] \mathcal{n} A \; </math>. A называется [[клика|кликой]], если G[A] является полным графом. Множество вершин <math>S \in V \; </math> называется [[разделитель вершин|разделителем вершин]], если <math>G[V \mathcal{n} S] \; </math> является несвязным; S называется [[минимальный разделитель|минимальным разделителем]] вершин, если существует пара вершин a, b <math>\in</math> V\S, такая, что a и b содержатся в разных компонентах связности <math>G[V \mathcal{n} S] \; </math> и в одной и той же компоненте связности <math>G[V \mathcal{n} S'] \; </math> для любого <math>S' \in S</math>. Множество вершин <math>\Omega \subseteq V \; </math> является ''потенциально максимальной кликой'', если не существует компоненты связности <math>G[V \mathcal{n} \Omega]</math>, содержащей 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] определяет независимые задачи минимальной триангуляции.