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

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