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

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

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

Указанные названия цепей и циклов связаны с именем Уильяма Гамильтона (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. Допустим (не теряя общности), что degv₁ ≥ (p−1)/2 и degv_p ≥ p/2, но вершины v₁ и v_p не смежны. Тогда существует простая остовная цепь v₁v₂…v_p, соединяющая v₁ и v_p.

 

Обозначим вершины, смежные с v₁, через v_i1,…,v_in, где n = degv₁ и 2 = i₁ < i₂ <…< i_n. Ясно, что вершина v_p не может быть смежной ни с одной вершиной из G вида v_ij−1, поскольку тогда в G был бы гамильтонов цикл
v₁v₂…v_ij−1v_pv_p−1…v_ijv₁.

 

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

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

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

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

 

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

Следствие 1

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

Следствие 2

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

Теорема 2

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

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

m_k = a₁…a_kxa_k+1…a_p

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

(a_k, x) ∈ E, (x, a_k+1) ∈ E.

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

(a_k, x) ∈ E ⇒ (x, a_k+1) ∉ E ⇒ (a_k+1, x) ∈ E.

Если не существует пути m₀ = xa₁…a_p, то (a₁, x) ∈ E ⇒ (a₂, x) ∈ E, (a_p, x) ∈ E, и путь m_p = a₁…a_px существует, вопреки допущению. Таким образом, можно шаг за шагом построить путь, содержащий все вершины графа. ♦

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

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

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

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

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

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

Указанные названия цепей и циклов связаны с именем Уильяма Гамильтона (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. Допустим (не теряя общности), что degv₁ ≥ (p−1)/2 и degv_p ≥ p/2, но вершины v₁ и v_p не смежны. Тогда существует простая остовная цепь v₁v₂…v_p, соединяющая v₁ и v_p.

Обозначим вершины, смежные с v₁, через v_i1,…,v_in, где n = degv₁ и 2 = i₁ < i₂ <…< i_n. Ясно, что вершина v_p не может быть смежной ни с одной вершиной из G вида v_ij−1, поскольку тогда в G был бы гамильтонов цикл
v₁v₂…v_ij−1v_pv_p−1…v_ijv₁.

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

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

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

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

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

Следствие 1

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

Следствие 2

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

Теорема 2

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

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

m_k = a₁…a_kxa_k+1…a_p

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

(a_k, x) ∈ E, (x, a_k+1) ∈ E.

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

(a_k, x) ∈ E ⇒ (x, a_k+1) ∉ E ⇒ (a_k+1, x) ∈ E.

Если не существует пути m₀ = xa₁…a_p, то (a₁, x) ∈ E ⇒ (a₂, x) ∈ E, (a_p, x) ∈ E, и путь m_p = a₁…a_px существует, вопреки допущению. Таким образом, можно шаг за шагом построить путь, содержащий все вершины графа. ♦

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