4551
правка
Быстрая минимальная триангуляция: различия между версиями
Материал из WEGA
Быстрая минимальная триангуляция (посмотреть исходный код)
Версия от 00:15, 14 мая 2014
, 14 мая 2014→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 62: | Строка 62: | ||
Принимая во внимание результаты из [1] и [7], получаем следующий рекурсивный алгоритм минимальной триангуляции. Найти множество вершин A, являющееся либо минимальным разделителем, либо потенциально максимальной кликой. Дополнить G[A] до клики. Рекурсивным образом для каждой компоненты связности C из <math>G[V \mathcal{n} A] \; </math>, где <math>G[N[C]] \; </math> не является кликой, найти минимальную триангуляцию <math>G[N[C]] \; </math>. Важное свойство алгоритма заключается в том, что множество компонент связности <math>G[V \mathcal{n} A] \; </math> определяет независимые задачи минимальной триангуляции. | Принимая во внимание результаты из [1] и [7], получаем следующий рекурсивный алгоритм минимальной триангуляции. Найти множество вершин A, являющееся либо минимальным разделителем, либо потенциально максимальной кликой. Дополнить G[A] до клики. Рекурсивным образом для каждой компоненты связности C из <math>G[V \mathcal{n} A] \; </math>, где <math>G[N[C]] \; </math> не является кликой, найти минимальную триангуляцию <math>G[N[C]] \; </math>. Важное свойство алгоритма заключается в том, что множество компонент связности <math>G[V \mathcal{n} A] \; </math> определяет независимые задачи минимальной триангуляции. | ||
Этот рекурсивный алгоритм определяет дерево, корнем которого является входной граф G, а каждая компонента связности <math>G[V \mathcal{n} A]</math> становится потомком корневой вершины, определяемой G. Этот процесс рекурсивно продолжается для каждой подзадачи, определяемой этими компонентами связности. Вершина H, являющаяся подзадачей алгоритма, находится на уровне i, если расстояние от H до корня дерева равно i. Заметим, что триангуляция всех подзадач одного и того же уровня может выполняться независимо. Пусть k – количество уровней. Если этот рекурсивный алгоритм может быть выполнен для каждого подграфа на каждом уровне за время O(f(n)), тогда общее время исполнения составит O(f(n) | Этот рекурсивный алгоритм определяет дерево, корнем которого является входной граф G, а каждая компонента связности <math>G[V \mathcal{n} A]</math> становится потомком корневой вершины, определяемой G. Этот процесс рекурсивно продолжается для каждой подзадачи, определяемой этими компонентами связности. Вершина H, являющаяся подзадачей алгоритма, находится на [[уровень|уровне]] i, если расстояние от H до корня дерева равно i. Заметим, что триангуляция всех подзадач одного и того же уровня может выполняться независимо. Пусть k – количество уровней. Если этот рекурсивный алгоритм может быть выполнен для каждого подграфа на каждом уровне за время <math>O(f(n)) \; </math>, тогда общее время исполнения составит <math>O(f(n) \cdot k) \; </math>. | ||
