4551
правка
Быстрая минимальная триангуляция: различия между версиями
Перейти к навигации
Перейти к поиску
→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 5: | Строка 5: | ||
Минимальная триангуляция заключается в добавлении к произвольному неориентированному графу минимального набора дуг, такого, что в результате получается хордальный граф. Граф является хордальным, если любой цикл длины не менее 4 содержит дугу между двумя непоследовательными вершинами цикла. | Минимальная триангуляция заключается в добавлении к произвольному неориентированному графу минимального набора дуг, такого, что в результате получается хордальный граф. Граф является хордальным, если любой цикл длины не менее 4 содержит дугу между двумя непоследовательными вершинами цикла. | ||
Пусть G = (V, E) – простой неориентированный граф, где n = | Пусть 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 представляет собой минимальную триангуляцию, если не существует F0 С F, такого, что H0 = (V;E [ F0) является хордальным. Дуги в F называются дополняющими дугами; триангуляция является минимальной в том и только том случае, если удаление любой дополняющей дуги приводит к появлению бесхордовых циклов из 4 вершин [10]. | ||