4430
правок
Параметризованные алгоритмы графического представления графов: различия между версиями
Материал из WEGA
Параметризованные алгоритмы графического представления графов (посмотреть исходный код)
Версия от 19:19, 30 марта 2016
, 30 марта 2016→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 80: | Строка 80: | ||
Лемма 5 позволяет сформулировать следующее правило: | Лемма 5 позволяет сформулировать следующее правило: | ||
Правило RR1: Для каждой пары вершин {u, v} из | '''Правило RR1''': Для каждой пары вершин {u, v} из <math>V_2 \;</math> с <math>c_{uv} = 0 \;</math> включить <math>u <_2 v \;</math>. В приведенном примере d будет полностью включено в результате применения правила RR1, поскольку столбец d в матрице пересечений заполнен нулями; следовательно, в последующих действиях d можно игнорировать. | ||
Алгоритм 1 представляет собой простой алгоритм поиска по дереву для задачи OSCM, последовательно применяющий правило RR1. | |||
Алгоритм 1: | '''Лемма 6'''. OSCM можно вычислить за время <math>0^*(2^k) \;</math>. | ||
• На строке 5 следует исключить | Доказательство. До того, как будет производиться какое-либо ветвление, выполняется редукция экземпляра графа таким образом, чтобы любая невключенная пара вершин {u, v} из <math>V_2 \;</math> удовлетворяла условию <math>min \{ c_{uv}, c_{vu} \} \ge 1 \;</math>. Следовательно, каждое рекурсивное ветвление уменьшает параметр как минимум на 1.□ | ||
• На строке 12 следует произвольным образом включить некоторую пару {x, y} | |||
Этот простой алгоритм поиска по дереву можно улучшить. Во-первых, отметим, что нет необходимости ветвления в {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>, следует вернуть значение ДА. | |||
