Лекции 14. Основные понятия теории графов. Некоторые виды графов (4 часа)

x_n = cⁿ / nn!, с > 1.
Нетрудно заметить, что
x_n+1 = x_nc / (n + 1).
Поэтому, как только n + 1 > c эта варианта становится убывающей, а поскольку она ограничена нулем, то предел ее также есть нуль.
Для решения NP‑полных задач известен метод, позво­ляющий сократить число шагов, сводя задачу от факто­ри­альной к экспоненциальной сложности. Этот метод извес­тен под названием «backtracing» или «алгоритм с воз­вратами». Его суть в применении к задаче построения га­миль­тоновых циклов состоит в следующем.
Будем искать решение в виде последовательности вер­шин v₁, v₂, …, v_n, начиная от корневой вершины v₁. Имея частичное решение v₁, v₂,…, v_i, i < n, пытаемся найти та­кое допустимое значение v_{i + 1,} относительно ко­то­ро­­го можно предположить, что оно может расширить частичное решение до v₁, v₂,…, v_{i + 1}. Если такое предположение возможно, то v_{i + 1} включается в частичное решение и процесс продолжается. Если никакая вершина не может пре­тен­довать на v_{i + 1}, то следует возврат на шаг к v_{i - 1}, а v_i из дан­ного частичного решения исключается. Процесс поиска но­вого допустимого значения продолжается, начиная с v_{i - 1}. Когда v_n найдено, отмечают v₁, v₂, …, v_n  как Решение:
Если поставлена задача отыскания всех решений, то попытка получения каждого нового решения осуществляется возвратом на шаг от v_n в предположении, что решение как бы получено не было. Таким образом, отыскивается мно­жество всех решений, которое, в частности, оказывается пу­стым, если гамильтонова цикла на графе не существует.
Из описания алгоритма с возвратами видно, что задача построения всех гамильтоновых циклов на графе G может быть решена путем сопоставления исходному графу неко­торого другого графа G, построенного из частично пересе­кающихся цепей v₁, v₂, …, v_i, (i  n). Подмножество G, состоящее из цепей v₁, v₂, …, v_n, таких что v_n смежна с v₁ на G представляет множество решений задачи. Граф G называется соотнесенным графом.
Рассмотрим решение задачи о коммивояжере на примере графа G, представленного на рисунке 3. Имеем пять пунктов V = {1, 2, 3, 4, 5}. Стоимость доставки информации из пункта i в пункт j представлена числами над ребрами графа. Требуется, используя компьютерную сеть, моделируемую данным графом, обеспечить перекличку пунктов (например, фирм, принадлежащих одной корпорации и т.д.), начиная из пункта 1. Для решения поставленной задачи построим гамильтонов цикл минимальной стоимости передачи информации, либо несколько таких циклов в случае их одинаковой стоимости.
Задачу будем решать в два этапа. Вначале построим все гамильтоновы циклы из пункта 1. Для этого применим алго­ритм с возвратами. Затем на множестве полученных ци­клов выберем циклы минимальной длины.
Построение цепей графа G применением алгоритма с возвратами поясняется рисунком 3. справа. На этом рисунке цепи, соответствующие гамильтоновым циклам, выделены жи­рными линиями.
Всего имеем четыре гамильтоновых цикла:

1. 
   {1, 2, 3, 5, 4, 1}
   
2. 
   {1, 2, 5, 3, 4, 1},
   
3. 
   {1, 4, 3, 5, 2, 1},
   
4. 
   {1, 4, 5, 3, 2, 1}.
   

Стоимости передачи информации каждым из этих циклов вычисляются ниже:

1. 
   9+10+2+2+6 = 29,
   
2. 
   9+8+2+5+6 = 30,
   
3. 
   6+5+2+8+9 = 30,
   
4. 
   6+2+2+10+9 = 29.
   

Решению поставленной задачи отвечают гамильтоновы циклы a) и d).
Можно показать, что алгоритмы с возвратами имеют вычислительную сложность О(сⁿ), где c > 1 — константа, оп­ределяемая свойствами присоединенного графа. Такое бы­стродействие при больших n значительно выше, чем в слу­чае применения алгоритмов факториальной сложности. На­пример, возвращаясь к рассмотренному выше примеру оцен­ки быстродействия алгоритма с возвратами при n = 20 видим, что в случае, когда с = 2 (граф G двоичное дерево)
G G
2 1
(9) (10) 2 4
3 5 3 5
(8)
4 5 3 4 2 5 2 3
1 5 (2 ) 3
(2) 1 5 4 4 1 3 1 5 2 1 3 2
(6) (5)
4 1 1 1 1

Рисунок 3.

имеем всего 2²⁰ или порядка 10⁶ вычислительных операций. На любом современном компьютере это практически не займет времени. Однако, при увеличении размерности задачи всего лишь в несколько раз снова возникают про­блемы реального времени. Это способствует развитию но­вых идей построения гамильтоновых циклов.