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

Минимальная триангуляция заключается в добавлении к произвольному неориентированному графу минимального набора дуг, такого, что в результате получается [[хордальный граф]]. Граф является хордальным, если любой цикл длины не менее 4 содержит дугу между двумя непоследовательными вершинами цикла.

Пусть G = (V, E) – простой неориентированный граф, где <math>n = |V| \; </math> и <math>m = |E| \; </math>. Граф <math>H = (V, E \cup F) \; </math>, где <math>E \cap F = \empty \;</math>, представляет собой [[триангуляция|триангуляцию]] графа G, если H является хордальным; H представляет собой [[минимальная триангуляция|минимальную триангуляцию]], если не существует <math>F' \subset F \; </math>, такого, что <math>H' = (V, E \cup F') \; </math> является хордальным. Дуги в F называются дополняющими дугами; триангуляция является минимальной в том и только том случае, если удаление любой дополняющей дуги приводит к появлению бесхордовых циклов из 4 вершин [10].

         '''if''' существует антидуга uv в <math>H[N_H[C]] \; </math>, такая, что <math>u \in C</math> '''then'''

   Добавить к G' дуги, обозначенные ненулевыми элементами <math>MM^T \; </math>;

Для множества вершин <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} \Omega] \; </math>, содержащая в своей окрестности одновременно u и v.

Рис. 2. Алгоритм разбиения. Пусть <math>\bar E_H = W \; </math>, где <math>uv \in W \; </math>, если <math>uv \notin D \; </math> – множество антидуг H. Определим <math>E_{\bar H}(S) \; </math> как сумму степеней в <math>\bar H = (U, \bar E) \; </math> вершин <math>S \subseteq U = V(H) \; </math>

Несмотря на то, что все подзадачи на одном и том же уровне могут решаться независимо, у них могут быть общие вершины и дуги, но не антидуги (т.е. пары вершин, не являющиеся смежными). Поскольку процесс триангуляции включает в себя добавление дуг, число антидуг на каждом уровне снижается, и сумма числа антидуг для всех подзадач на одном и том же уровне не может превышать <math>n^2 \; </math>. Алгоритм разбиения на рис. 2 использует этот факт; он имеет время исполнения <math>O(n^2 - m) \; </math>, что в сумме для каждого уровня дает <math>O(n^2) \; </math>. Таким образом, каждый уровень алгоритма быстрой минимальной триангуляции, приведенного на рис. 1, может быть выполнен за время <math>O(n^2 + n^{ \alpha }) \; </math>, где <math>O(n^{ \alpha }) \; </math> – время, необходимое для вычисления <math>MM^T \; </math>. Алгоритм разбиения на рис. 2 фактически находит множество A, которое определяет множество независимых разделителей, такое, что ни одна подзадача не содержит более четырех пятых всех антидуг исходного графа. В результате количество уровней алгоритма быстрой минимальной триангуляции не превышает <math>log_{ \frac{4}{5} }(n^2) = 2 \; log_{ \frac{4}{5} }(n)</math>, чем достигается время исполнения <math>O(n^{ \alpha } log \; n)</math>.