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

Минимальная триангуляция заключается в добавлении к произвольному неориентированному графу минимального набора дуг, такого, что в результате получается [[хордальный граф]]. Граф является хордальным, если любой цикл длины не менее 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].