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

Теорема. Пусть G — связный граф с k вер­шинами нечетной степени. Тогда минимальное по­кры­тие графа цепями имеет мощность k / 2.
Доказательство. В силу теоремы 4.4 число вершин не­четной степени четно. Следовательно, каждая из k вершин нечетной степени должна быть концом одной из покры­ва­ющих цепей графа. Отсюда с необходимостью следует, что число всех покры­вающих цепей должно быть не менее, чем k / 2. Расширим граф G до эйлерова графа, добавив k / 2 ребер, соединяющих различные пары вершин нечетной степени. Тогда на графе определен единственный эйлеров цикл. Аннулируя ребра, вместе с каждым аннулированным ребром имеем и новую цепь. Тогда число k / 2 является также и достаточным чис­лом цепей, покрывающих граф.
Для ориентированных графов можно получить ана­логичный результат. В частности, имеет место
Теорема. Для того, чтобы на ориенти­рованном графе G существовал контур, содержащий все дуги G, необходимо и достаточно, чтобы число всех входящих и выходящих дуг было одинаковым в каждой из вершин.
Такой контур называется эйлеровым контуром.


3. Гамильтоновы циклы. Оценка временной сложности алгоритмов
Цикл на графе G называется гамильтоновым, если соответствующая ему последовательность ребер содержит каждую вершину графа G в точности один раз.
Аналогично вводится понятие гамильтонова контура на ориентированном графе.
Примеры гамильтонового цикла и графа, для которого такого цикла не существует представлены на рисунке 2.

а) v₁ б) v₁

v₂ v₄ v₅ v₂ v₄ v₅
v₃
v₃
Рисунок 2.
На рисунке 2. а) направление одного из гамильтоновых циклов отмечено стрелками. Соответствующий гамиль­тонов цикл представлен последовательностью ребер {(v₁, v₄), ( v₄, v₅), (v₅, v₃), (v₃, v₂), (v₂, v₁)}. Можно заметить, что ребро (v₄, v₃) в этом цикле не используется. Этот факт ука­зывает на то, что в гамильтоновом цикле могут участвовать не все ребра графа. Существенным в цикле данного типа яв­ляется наличие всех вершин графа. В связи с этим, в слу­чаях, когда нет кратных ребер, гамильтонов цикл запи­сывают последовательностью вершин. Так в рассмотренном примере гамильтонов цикл можно представить следующей последовательностью вершин: [v₁, v₄, v₅, v₃, v₂]. Нетрудно заметить, что при такой записи каждый гамильтонов цикл должен соответствовать некоторой допустимой перестановке всех вершин графа. Ясно, что одному и тому же графу мо­жно поставить в соответствие некоторое множество гамильтоновых циклов. Пример на рисунке 2. б) иллюстрирует случай, когда это множество пусто, поскольку вершина v₄ необходимо должна быть повторена дважды.
Укажем некоторые задачи, интерпретация которых сос­тоит в необходимости построения гамильтоновых циклов.
Задача о шахматном коне. Можно ли начиная с про­извольного поля на шахматной доске ходить конем в та­кой последовательности, чтобы пройти через все поля и вер­нуться в исходное?
Задача о званом обеде. Обед накрыт на круглом столе. Среди приглашенных некоторые являются друзьями. При каких условиях можно рассадить всех так, чтобы по обе стороны от каждого из присутствующих сидели его друзья?
Задача о коммивояжере. Коммивояжер должен объездить все n городов. Для того, чтобы сократить свои расходы он хочет построить такой маршрут, чтобы объездить все го­рода точно по одному разу и вернуться в исходный с мини­мумом затрат.
В настоящее время не по­лучено необходимых и достаточных условий суще­ств­ова­ния для гамильтоновых циклов.
С другой стороны, существует очевидный алгоритм, который казалось бы можно применить к решению любой за­дачи о гамильтоновом цикле: генерируем все перестановки вершин и проверяем, какая из них является гамиль­то­но­вым циклом. Всех перестановок, очевидно, будет n!
Оценим временную сложность этого алгоритма. Под временной характеристикой сложности алгоритма понимают асимптотическую оценку О(f(n₁, n₂, …n_k)) требуемого вре­мени работы компьютера в зависимости от мощностей n₁, n₂, …, n_k множеств исходных данных при неограниченном уве­личении этих мощностей. Поскольку компьютеры могут об­ладать различной производительностью, то оценка времен­ных затрат может быть выражена в количестве эле­мен­тар­ных операций: сложений, умножений или других опе­раций, выполняемых компьютером и принятых за основу.
Легко видеть, что ограничением применения предложенного выше метода является то, что для его реализации потребуется О(nn!) вычислительных операций (n операций на каждую из n! перестановок). Так, если n = 20 и каждый элементарный шаг компьютера выполняется за 10^-7 с, то ре­шение задачи о построении гамильтонова цикла займет по­рядка 20*20!48*10¹⁸ операций или 45*10¹¹ с, что сос­та­вляет порядка 1500 веков.
Проблема существования гамильтонового цикла принадлежит к классу так называемых NP‑полных задач. Это широкий класс задач, для которых не известен алгоритм по­линомиальной сложности их решения, то есть алгоритм с числом шагов, ограниченных полиномом от размерности за­дачи. Задача же построения гамильтонового цикла, как ука­зано выше, в максимальном случае решается алгоритмом факториальной сложности.
Для того, чтобы убедиться в том, что значения nn! растут быст­рее, чем значения произвольного многочлена, покажем, что они растут быстрее, чем значения показательной функции, начиная с неко­торого достаточно большого значения n.
Для этого рассмотрим варианту