Алгоритмы и анализ сложности (стр. 10 )

Пример графа по КНФ:

Очевидно, что граф можно построить за (длина КНФ).

1. Клику могут образовать только вершины «из разных скобок», поэтому клика содержит вершин.

2. Если БФ не выполнима, то в ней есть скобки, к-рые не могут одновременно быть =1, например,

и .

Но тогда и вершины, соот-щие литералам из таких скобок, не могут соединяться ребрами, следовательно, клика графа будет содержать вершин.

3. Если БФ выполнима, то в каждой скобке есть хотя бы один литерал со значением 1. По условиям построения графа вершины, соот-щие таким литералам, можно соединить ребром, следовательно, клика существует.

Аналогично, если существует клика, то БФ выполнима, т. е. БФ выполнима существует клика.

Следствие: задача о максимальной клике - трудная.

Теорема 4: задача о клике полиномиально сводится к задаче о вершинном (узельном) покрытии, следовательно,

задача о ВП полна.

ВП – это мн-во вершин, инцидентных всем ребрам графа.

Пусть имеется граф с кликой. Построим его дополнение и покажем, что – мн-во узлов клики графа – ВП графа .

1. Если – клика , то никакая пара вершин из не соединена ребром в , след-но, вершины из образуют ВП .

2. Если образуют ВП , то любое ребро инцидентно по крайней мере одной вершине из . Следовательно, включает ребра, соединяющие все пары вершин из .

Очевидно, что можно построить по описанию за полиномиальное время.

Теорема 5: задача о ВП полиномиально сводится к задаче поиска гамильтонова цикла в орграфе, следовательно,

задача о гамильтоновом цикле в орграфе полна.

Требуется доказать, что из исходного неориентированного графа можно за полиномальное время построить такой орграф , что

-ВП в существует в существует гамильтонов цикл.

Для каждой вершины из в графе появляются вершин ( – это число ребер, инцидентных вершине ).

Кроме того, в включаются еще дополнительных вершин, и тогда

( инцидентно ).

Каждое ребро представлено в графе подграфом из 4 вершин. Для каждой вершины организуются списки инцидентных ребер. В начала этих списков идут дуги из , из концов списков также идут дуги во все .

Гамильтонов цикл в :

- начинается в вершине ,

- проходит по цепочке вершин, соотв-х 1-й вершине ВП ,

- приходит в ,

- проходит по цепочке вершин, соотв-х 2-й вершине ВП ,

…

- приходит в ,

- проходит по цепочке вершин, соотв-х -й вершине ВП ,

- возвращается в .

Если , то при обходе переход заменяется на цепочку:

.

Аналогично можно показать, что если в есть гамильтонов цикл, то в исходном графе можно выделить соот-ее ВП.

можно построить по графу за полиномиальное время.

Теорема 6: задача о гамильтоновом цикле в орграфе полиномиально сводится к задаче о гамильтоновом цикле в неориентированном графе, следовательно,

задача о ГЦ в неориентированном графе полна.

Из заданного графа получаем (за полиномиальное время) неориентированный граф , заменяя каждую вершину на трехвершинную конфигурацию:

1. Если в исходном орграфе есть ГЦ, то он очевидно есть и в неориентированном графе .

2. Пусть ГЦ есть в , тогда по условиям построения вершины будут проходиться либо все в направлении ориентации (), либо все в противоположном направлении () – иначе невозможно включить в маршрут вершины типа .

Теорема 7: задача о ГЦ в неориентированном графе полиномиально сводится к задаче поиска оптимального маршрута коммивояжера с симметричной матрицей весов. Но последняя задача не имеет алгоритма решения,

следовательно, она является трудной.

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

.

Очевидно, что содержит ГЦ стоимость оптимального маршрута коммивояжера . При отсутствии ГЦ стоимость оптимального маршрута будет .

Следствие 1: задача поиска оптимального маршрута в общем случае – трудная.

Следствие 2: задача коммивояжера полная, т. к. существует алгоритм ее решения.

Если задача симметричная и выполняется неравенство треугольника, то можно найти субоптимальные решения (ближайший город, мин. остов и т. д.).

Но если данные условия не выполняются, то даже поиск субоптимального маршрута – трудная задача (в этом случае приближенные алгоритмы не дают гарантированного субоптимального решения).

Назовем субоптимальным маршрут, вес к-го выше оптимального в раз.

Теорема 8: задача получения субоптимального маршрута для симметричной (и, тем более, общей) задачи коммивояжера является трудной.

Полиномиально сводим задачу поиска ГЦ в графе к симметричной задаче коммивояжера, для к-рой определяем следующий частный случай:

.

Стоимость оптимального маршрута имеет ГЦ.

Стоимость любого другого маршрута должна быть, по крайней мере, .

, т. е. любой другой маршрут не является субоптимальным.

Следовательно, задача поиска субоптимального маршрута эквивалентна поиску оптимального (мы не можем установить субоптимальность, не зная веса оптимального маршрута).