Первая страница / Теория / Графы. Циклы и разрезы /

Гамильтоновы графы

Голосование: 20, 1

Введение

Напомним основные определения из теории графов. Пусть V непустое конечное множество. Через V(2) обозначим множество всех двухэлементных подмножеств из V. Графом G называется пара множеств (VE), где E — произвольное подмножество из V(2). Элементы множеств V и E называют соответственно вершинами и ребрами графа G. Граф G(V, E) называется полным, если любая пара его вершин соединена хотя бы в одном направлении.

Маршрутом (или путем) в графе G называется чередующаяся последовательность вершин и ребер v0, e1, v1, …, vt−1, et, vt+1, в которой ei = vi−1vi (1 ≤ i ≤ t). Такой маршрут кратко называют (v0vt)-маршрутом и говорят, что он соединяет v0 c vt; в свою очередь вершины v0, vt — это концевые вершины указанного маршрута. Длиной маршрута называют количество содержащихся в нем ребер. Заметим, что в обыкновенном графе маршрут полностью определяется последовательностью v0, v1, …, vt своих вершин. Если v0=vt, то (v0vt)-маршрут называется замкнутым.

Цепь — это маршрут без повторяющихся ребер. Цепь называется простой цепью, если в ней нет повторяющихся вершин, кроме, быть может, совпадающих концевых вершин. Замкнутая простая цепь называется циклом (или контуром).

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

Указанные названия цепей и циклов связаны с именем Уильяма Гамильтона (Hamilton W.), который в 1859 году предложил следующую игру-головоломку: требуется, переходя по очереди от одной вершины додекаэдра к другой вершине по его ребру, обойти все 20 вершин по одному разу и вернуться в начальную вершину.

Отметим, что придумано еще много других развлекательных и полезных задач, связанных с поиском гамильтоновых циклов. Сформулируем две из них.

  1. (Задача про банкет) Компанию из нескольких человек требуется рассадить за круглым столом таким образом, чтобы по обе стороны от каждого сидели его знакомые. Очевидно, для решения этой задачи нужно найти гамильтонов цикл в графе знакомств компании.
  2. (Задача о шахматном коне.) Можно ли, начиная с произвольного поля шахматной доски, обойти конем последовательно все 64 поля по одному разу и вернуться в исходное поле? (решение будет рассмотрено ниже).

Следующая теорема, доказанная Поша (Posa L.), дает достаточное условие того, что неориентированный граф является гамильтоновым. Она обобщает результаты, полученные ранее Оре (Ore O.) и Дираком (Dirac G.A.), которые приводятся здесь в виде следствий.

Теорема 1

Пусть G имеет p ≥ 3 вершин. Если для всякого n, 1 ≤ n ≤ (p−1) ⁄ 2, число вершин со степенями, не превосходящими n, меньше чем n, и для нечетного p число вершин степени (p−1) ⁄ 2 не превосходит (p−1) ⁄ 2, то G — гамильтонов граф.

Доказательство. Предположим, что теорема неверна, и пусть G — максимальный негамильтонов граф с p вершинами, удовлетворяющий условиям теоремы. Легко видеть, что добавление любого ребра в граф, обладающий указанными в теореме свойствами, приводит к графу, который так же обладает этими свойствами. Таким образом, поскольку добавление к G произвольного ребра приводит к гамильтонову графу, любые две несмежные вершины соединимы простой остовной (содержащей все вершины графа) цепью.

Покажем сначала, что всякая вершина, степень которой не меньше (p−1)/2, смежна с каждой вершиной со степенью, большей чем (p−1)/2. Допустим (не теряя общности), что degv1 ≥ (p−1)/2 и degvp ≥ p/2, но вершины v1 и vp не смежны. Тогда существует простая остовная цепь v1v2vp, соединяющая v1 и vp.

Обозначим вершины, смежные с v1, через vi1,…,vin, где n = degv1 и 2 = i1 < i2 <…< in. Ясно, что вершина vp не может быть смежной ни с одной вершиной из G вида vij−1, поскольку тогда в G был бы гамильтонов цикл
v1v2vij−1vpvp−1vijv1.

Далее, так как n ≥ (p−1)/2, то p/2 ≤ degvp ≤ p−1−n < p/2, что невозможно. Поэтому v1 и vp должны быть смежны.

Отсюда следует, что если degv ≥ p/2 для всех вершин v, то G — гамильтонов граф. (Ниже это сформулировано в виде следствия 2.) В силу изложенного выше каждая пара вершин графа G смежна, т.е. G — полный граф. Мы пришли к противоречию, поскольку полный граф является гамильтоновым для всех p ≤ 3.

Таким образом, в G — есть вершина v с degv < p/2. Обозначим через m наибольшую среди степеней всех таких вершин. Выберем такую вершину v1, что degv1=m. По принятому предположению число вершин со степенями, не превосходящими m, не больше чем m < p/2, поэтому должно быть более чем m вершин со степенями, превосходящими m, и, следовательно, не меньшим, чем p/2. В результате найдется некоторая вершина, скажем vp, степени по крайней мере p/2, не смежная с v1. Так как v1 и vp не смежны, то существует остовная простая цепь v1vp. Как и выше, обозначим через vi1,…,vim вершины графа G, смежные с v1, и заметим, что вершина vp не может быть смежной ни с одной из m вершин vij−1 для 1 < j ≤ m. Но поскольку v1 и vp не смежны, а vp имеет степень не меньше p/2, то, как было показано в первой части доказательства, m должно быть меньше чем (p-1)/2. Так как по предположению число вершин, со степенями, не превосходящими m, меньше чем m, то хотя бы одна из m вершин vij-1, скажем u, должна иметь степень не меньше p/2. Итак, мы установили, что степени двух несмежных вершин vp и u не меньше p/2. Полученное противоречие завершает доказательство теоремы. ♦

Приведенное достаточное условие не является необходимым. Кубический граф, изображенный на рисунке, гамильтонов, хотя ясно, что он не удовлетворяет условиям теоремы. Однако условия теоремы неулучшаемы, поскольку при их ослаблении новое условие уже не будет достаточным для гамильтоновости графа.


Ограничивая условия теоремы Поша, получаем более простые, но менее сильные достаточные условия, найденные Оре и Дираком соответственно:

Следствие 1

Если p ≥ 3 и degu + degvp для любой пары u и v несмежных вершин графа G, то G — гамильтонов граф.

Следствие 2

Если p > 3 и degvp / 2 для любой вершины v графа G, то G — гамильтонов граф.

Теорема 2

В полном графе G(VE) всегда существует гамильтонов путь.

Доказательство. Пусть m = a1a2ap — путь длины p−1, причем все вершины в m различны. x — вершина ∉ m. Покажем, что можно составить путь вида

mk = a1akxak+1ap

Пусть не существует такого целого числа k, заключенного между 1 и p, что

(akx) ∈ E, (xak+1) ∈ E.

Имеем, следовательно, для 1 ≤ k ≤ p:

(akx) ∈ E ⇒ (xak+1) ∉ E ⇒ (ak+1x) ∈ E.

Если не существует пути m0 = xa1ap, то (a1x) ∈ E ⇒ (a2x) ∈ E, (apx) ∈ E, и путь mp = a1apx существует, вопреки допущению. Таким образом, можно шаг за шагом построить путь, содержащий все вершины графа. ♦

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

Задача о шахматном коне

Поставим задачу обойти конем шахматную доску так, что побывать в каждой клетке ровно по одному разу. Эта задача интересовала многих математиков, особенно Эйлера (Euler L.), де Муавра (de Moivres), Вандермонда (Vandermonde) и др.

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

Другой способ состоит в нахождении маршрута по половинке доски, симметричном дублировании его и соединении обоих маршрутов.

Факторы

Фактором графа (VE) называется частичный граф (VE0), в котором каждая вершина обладает полустепенями исхода и захода, равными 1. Всякий гамильтонов контур является фактором, но обратное неверно, ибо фактор может состоять из нескольких контуров без общих вершин.

Введем обозначения:

Eu = {v: (uv) ∈ E},
E−1u = {v: (vu) ∈ E},
EA = ∪uA Eu,

т.е. EA является образом множества вершин A.

Определим простой граф (VV*E), соответствующий данному произвольному графу (VE), следующим образом: V* есть дубликат множества V, a v*k ∈ Evi в (VV*E) тогда и только тогда, когда vk ∈ Evi в (VE).

Теорема 3 (Кенига-Холла (Konig D., Hall P.))

Паросочетание, отображающие V в U, существует тогда и только тогда, когда |EW| ≥ |W| для любого множества W ⊂ V.

Следствие

Пусть (VUE) — простой граф, a

m = max {|Ev|, |E−1u|: v ∈ V, u ∈ U),

тогда всегда существует паросочетание, использующее все те вершины v, для которых |Ev| = m, и все те вершины u, для которых |E−1u| = m.

Теорема 4

Необходимое и достаточное условие существования фактора у графа (VE) состоит в том, чтобы |EW| ≥ |W| при всех W ⊂ V.

Доказательство. Действительно, в силу теоремы 3 это условие выражает тот факт, что в простом графе (VV*E), существует паросочетание, отображающее V на V*. ♦

Следствие

Если граф (VE) таков, что |Ev| = |E−1v| = m для любой вершины v, то дуги этого графа можно распределить по m непересекающимся множествам W1, W2, …, Wm, каждое из которых образует фактор.

Доказательство. Простой граф (VV*E) обладает свойством |Ev| = m, |E−1v*| = m. В силу следствия из теоремы 3, можно отобразить V на V* и тем самым определить W1. В частичном графе, остающимся после удаления дуг W1, можно отобразить V на V* и тем самым определить W2 и т.д. ♦

Отыскание фактора является несложным делом, поскольку это есть задача о наибольшем потоке. Метод нахождения гамильтонова контура состоит в нахождении всех факторов графа и сохранении только тех из них, которые состоят из единственного контура.

Так же можно «склеивать» различные контуры фактора. Рассмотрим вновь задачу о шахматном коне. Благодаря симметрии шахматной доски получается фактор, указанный на рисунке. Клетки, помеченные одинаковыми буквами, образуют контур. Два контура можно объединить тогда и только тогда, когда две последовательные вершины одного соответственно смежны с двумя последовательными вершинами другого. Различные соединения показаны при помощи вспомогательного графа. Вспомогательный граф имеет очевидный гамильтонов путь aDbCdAcB.

Алгоритм нахождения гамильтонова цикла

Рассмотрим рекурсивную функцию searchHamiltonianCycle, которая возвращает true, если граф является гамильтоновым, и false в противном случае.


  searchHamiltonianCycle(0, 0, numberOfVertices);
  bool searchHamiltonianCycle(int v, int w, int d) {
1   if (d == 1 && w ∈ Adj[v]) return true;
2   visited[v] = true;
3   for (для) всех вершин t ∈ Adj[v]
4     if (!visited[t])
5       if (searchHamiltonianCycle(t, w, d-1))
6         return true;
7   visited[v] = false;
8   return false; 
  }
  • numberOfVertices — число вершин в графе
  • v — последняя найденная вершина
  • w — начальная вершина (с нее начинается поиск)
  • d — оставшаяся длина гамильтонова цикла

Данный алгоритм напоминает алгоритм поиска в глубину (DFS). Основные отличия отмечены красным цветом:

  • функция принимает начальную вершину w и длину гамильтонова цикла в качестве второго и третьего параметров соответственно;
  • в строке 1, функция проверяет, все ли вершины были посещены (d == 1), и если это так, то существует ли ребро, соединяющее начальную вершину с конечной. Если оба условия выполнены, то гамильтонов цикл найден;
  • в строке 7, функция переустанавливает значение маркера visited, прежде чем возвратит значение, означающие неуспех.

Свойство

Рекурсивный поиск гамильтонова цикла может потребовать экспоненциального времени.

Доказательство. Рассмотрим граф, у которого одна вершина изолирована, а ребра, связывающие остальные |V|−1 вершин, образуют полный граф. Функция searchHamiltonianCycle никогда не найдет гамильтонова цикла, но она исследует все (|V|−2)! путей, начинающихся в выбранной начальной вершине, каждый из которых использует |V|−1 рекурсивных вызовов. Следовательно, общее число рекурсивных вызовов равно (V−1)!. ♦

Список литературы

  1. Берж К. Теория графов и ее применения. — М.: Издательство иностранной литературы, 1962.
  2. Седжвик Р. Фундаментальные алгоритмы на C++. Алгоритмы на графах. — СПб: ООО «ДиаСофтЮП», 2002.
  3. Харари Ф. Теория графов. — М.: Мир, 1973.

Визуализаторы

  1. Ситников А. Гамильтоновы циклы и цепи. Метод Робертса и Флореса. (2002)
  2. Киракозов А. Поиск гамильтонова цикла. (2005)

Александр Киракозов


Ваше имя
Email
Текущий день недели (строчными буквами)
Комментарий