Параметризованные алгоритмы графического представления графов: различия между версиями

Перейти к навигации Перейти к поиску

Параметризованные алгоритмы графического представления графов (посмотреть исходный код)

Версия от 19:19, 30 марта 2016

184 байта добавлено ,  30 марта 2016
м
→‎Основные результаты
Строка 80: Строка 80:
Лемма 5 позволяет сформулировать следующее правило:
Лемма 5 позволяет сформулировать следующее правило:


Правило RR1: Для каждой пары вершин {u, v} из V2 с cuv = 0 необходимо включить u <2 v. В приведенном примере d будет полностью включено в результате применения правила RR1, поскольку столбец d в матрице пересечений заполнен нулями; следовательно, в последующих действиях d можно игнорировать. Алгоритм 1 представляет собой простой алгоритм поиска по дереву для задачи OSCM, последовательно применяющий правило RR1.
'''Правило RR1''': Для каждой пары вершин {u, v} из <math>V_2 \;</math> с <math>c_{uv} = 0 \;</math> включить <math>u <_2 v \;</math>. В приведенном примере d будет полностью включено в результате применения правила RR1, поскольку столбец d в матрице пересечений заполнен нулями; следовательно, в последующих действиях d можно игнорировать.




Лемма 6. OSCM можно вычислить за время 0*{2k).
Алгоритм 1 представляет собой простой алгоритм поиска по дереву для задачи OSCM, последовательно применяющий правило RR1.


Доказательство. До того, как будет производиться какое-либо ветвление, выполняется редукция экземпляра графа таким образом, чтобы любая невключенная пара вершин {u, v} из V2 удовлетворяла условию minf cuv;cvug > 1. Следовательно, каждое рекурсивное ветвление уменьшает параметр как минимум на 1. □
Этот простой алгоритм поиска по дереву можно улучшить. Во-первых, отметим, что нет необходимости ветвления в {x, y} С V2, если cxy = cyx. Это позволяет внести две модификации в


Алгоритм 1:
'''Лемма 6'''. OSCM можно вычислить за время <math>0^*(2^k) \;</math>.
yx.
 
• На строке 5 следует исключить cxy = c
Доказательство. До того, как будет производиться какое-либо ветвление, выполняется редукция экземпляра графа таким образом, чтобы любая невключенная пара вершин {u, v} из <math>V_2 \;</math> удовлетворяла условию <math>min \{ c_{uv}, c_{vu} \} \ge 1 \;</math>. Следовательно, каждое рекурсивное ветвление уменьшает параметр как минимум на 1.□
• На строке 12 следует произвольным образом включить некоторую пару {x, y} С V2, которая еще не была включена, и рекурсивно повторить действие; только если включены все пары {x, y} С V2, следует вернуть значение ДА.
 
 
Этот простой алгоритм поиска по дереву можно улучшить. Во-первых, отметим, что нет необходимости ветвления в {x, y} С V2, если cxy = cyx. Это позволяет внести две модификации в Алгоритм 1:
 
• На строке 5 следует исключить <math>c_{xy} = c_{yx} \;</math>.
 
• На строке 12 следует произвольным образом включить некоторую пару <math>\{ x, y \} \subset V_2 \;</math>, которая еще не была включена, и рекурсивно повторить действие; только если включены все пары <math>\{ x, y \} \subset V_2 \;</math>, следует вернуть значение ДА.




Irina
4551

правка

Источник — http://pco.iis.nsk.su/wega/index.php/Служебная:Сравнение_версий/11222

Навигация