Лекция 6. Гамильтоновы пути и циклы. Теорема Поша (Лекции 2016 года)

Методы дискретной оптимизацииГамильтоновы пути и циклы. Пути, имеющиетип цикла и достаточные условиясуществования гамильтоновых путей ициклов в неориентированном графе. ТеоремаПоша1 / 11Основные понятияОпределение.Цикл, проходящий через каждую вершину графа ровно один раз,называется гамильтоновым. Граф называется гамильтоновым, если в немсуществует гамильтонов цикл.Следствие 1 из определения.

Гамильтонов граф двусвязен, т.е.удаление любого ребра графа не влечет потери связности графа. Отсюдаследует альтернативное определение: гамильтонов граф – связный графбез шарниров.Определение.Тэта-граф – граф, все вершины которого за исключением двухнесмежных, имеют степень 2, а указанные 2 вершины имеют степень 3.Следствие 2 из определения. Каждый негамильтонов двусвязныйграф содержит тэта-подграф – задача для зачета!2 / 11Теорема ОреТеорема 1 (Оре)Пусть G – обыкновенный связный граф, содержащий n вершин, где n > 2.Если сумма степеней d(v) + d(w) ≥ n для любых двух различныхнесмежных вершин v и w графа G, то граф G гамильтонов.Доказательство.1. Прежде всего необходимо отметить: добавление любого ребра кграфу, удовлетворяющему условиям теоремы, не может нарушитьэтих условий.

Далее доказательство методом от противного.2. Предположим, что теорема неверна, т.е. существует не гамильтоновграф, удовлетворяющий условиям теоремы. Последовательноедобавление ребер к такому графу на каком-то шаге обязательноприведет к ситуации, когда добавление любого ребра делает графгамильтоновым, поскольку таковым является полный граф. Поэтомудалее будем предполагать, что G – критический, или максимальныйдля исходного графа по условиям теоремы граф: добавление любогоребра делает его гамильтоновым.3 / 11Теорема ОреПродолжение.2. В таком графе в силу связности для любой пары несмежных вершинu,v добавление ребра (u, v) означает появление гамильтонова циклаu = v1 , v2 , ..., vn = v, u, которому ребро (u, v) должно принадлежать,поскольку его обратное удаление лишает граф свойствагамильтоновости.

Это означает: в критическом графе любаяпара его несмежных вершин соединима гамильтоновойцепью, в которой эти вершины являются концевыми.4 / 11Теорема ОреЗавершение доказательства.3. Возьмем произвольные несмежные вершины u и v графа G. Поопределению графа G, если к нему добавить ребро (u, v), появитсягамильтонов цикл, содержащий это ребро. Значит, в G0 есть(u, v)-цепь, содержащая все n вершин графа. Рассмотрим множествоS = {i|u смежна с vi+1 } и множество T = {i|v смежна с vi }. В Sимеется d(u) элементов, а в T − d(v) элементов, что в сумме даетd(u) + d(v) > n элементов по условию теоремы.

Все элементымножеств S и T являются числами 1 до n − 1, а значит, S и T имеютобщий элемент (пусть это элемент i). Таким образом, в графе G0имеются ребра (u, vi+1 ) и (vi , v). Таким образом, в графе G0 есть циклu → v2 → · · · → vi → v → vn−1 → · · · → vi+1 → u, проходящий по всемвершинам по одному разу, т. е.

гамильтонов цикл (см. рисунок).5 / 11Теорема Дирака. Теорема ПошаИз теоремы Оре вытекает следующее, несколько более слабое, но оченьпростое для проверки достаточное условие гамильтоновости.Теорема ДиракаПусть G – обыкновенный связный граф, содержащий n вершин, где n > 2.Если степень d(v) ≥ n2 для всякой v – вершины графа G, то граф Gгамильтонов.Обозначим через dk (G) число вершин степени k в графе G.Теорема ПошаПусть связный граф G = (V, E), |V | = n ≥ 3. При выполнении условийXn = 2m, k < m ⇒dl (G) < kl≤kn = 2m + 1, k < m ⇒Xl≤kdl (G) < k,Xdl (G) ≤ ml≤mграф G гамильтонов.6 / 11Теорема ПошаДоказательство.1. Прежде всего необходимо отметить: добавление любого ребра кграфу, удовлетворяющему условиям теоремы, не может нарушитьэтих условий. Далее доказательство методом от противного.2.

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

Поэтомудалее будем предполагать, что G – критический, или максимальныйдля исходного графа по условиям теоремы граф: добавление любогоребра делает его гамильтоновым. В таком графе в силу связности длялюбой пары несмежных вершин u, v добавление ребра (u, v) означаетпоявление гамильтонова цикла u = v1, v2, . . . , vn = v, u, которомуребро (u, v) должно принадлежать, поскольку его обратное удалениелишает граф свойства гамильтоновости. Это означает: вкритическом графе любая пара его несмежных вершинсоединима гамильтоновой цепью, в которой эти вершиныявляются концевыми.7 / 11Теорема ПошаДоказательство.3.

Из п. 2 следует: если для пары вершин u, v справедливы неравенстваn−1d(u) ≥ n−12 , d(v) > 2 , то вершины u, v являются смежными.Непосредственно из данных неравенств следует, чтоd(u) + d(v) ≥ n − 1 и если эти вершины не смежные, то добавлениепроизвольного ребра в граф сделает вершины u, v смежными, а граф– гамильтоновым. Далее, для случая n = 2m + 1 рассмотримситуацию d(u) > m, d(v) > m + 1, а при n = 2m соответственноd(u) ≥ m, d(v) ≥ m.

Если вершины u, v не смежны, то существуетгамильтонова цепь = {u = v1 , v2 , . . . , vn = v}, соединяющая вершиныu, v, для которыхm + 1, n = 2m + 1d(u) = k ≥ m, d(v) = p ≥m, n = 2m8 / 11Теорема ПошаПродолжение.3.1 Обозначим через S(a) множество вершин, смежных с вершиной a, ичерез Spr (a) – множество вершин, предшествующих вершинам из S(a)в цепи C: vi ∈ S(u) ⇔ vi−1 ∈ Spr (u). Для любой вершины цепи Cпредшествующая ей вершина vi−1 ∈ Spr (u) не может принадлежатьS(v), поскольку в таком случае циклH = {u = v1 , v2 , . . . , vi−2 , vi−1 , vn = v, vn−1 , vn−2 , . .

. vi , v1 = u}гамильтонов, что противоречит предположению критичности G.Значит, вершина v не может быть смежной ни с одной из вершинмножества Spr (u), в котором число элементов не менее k ≥ n−12 . Изпредположения о степенях вершин u, v следуетn−1n−12 < d(v) ≤ n − 1 − k ⇒ k < 2 . С другой стороны, значениеn−1k ≥ 2 . Полученное противоречие означает: любая пары вершин u, v,n−1для которой d(u) ≥ n−12 , d(v) > 2 является смежной. Посколькуграф G – не гамильтонов, то отсюда следует, что в графе Gk ≤ m, n = 2m + 1nсуществует вершина v : d(v) = k ≤ n−12 < 2 ⇔k < m, n = 2m9 / 11Теорема ПошаПродолжение.4.

Обозначим множество вершин степени не более n−12 через A,B = V \A. Это означает, что степень вершины из множества не менееm + 1 при n = 2m + 1 и не менее m при n = 2m, т.е. не менее n2 .5. Обозначим через q максимальную степень среди таких вершин. Поусловию теоремы значение dq (G) не более m при q = m и менее m приq < m, поэтому вершин степени большей q не менее m + 1 как вслучае n = 2m + 1, так и в случае n = 2m. Из условий теоремы этоозначает, что любая вершина множества A смежна с не более чем mдругими вершинами в случае n = 2m + 1 и с не более чем m − 1вершиной в случае n = 2m + 1, т.е.

степень вершины множества Aменьше числа вершин в B. Поэтому для любой вершины u множестваA существует вершина v из множества B, которая не смежна с u.10 / 11Теорема ПошаОкончание доказательства. Рассмотрим любую пару несмежныхвершинd(vn ) ≥ m + 1, n = 2m + 1v1 ∈ A, vn ∈ B : d(v1 ) = q,d(vn ) ≥ m, n = 2mи гамильтонову цепь C = {v1 , v2 , ..., vn }, для которой указанные вершиныявляются концевыми. Повторение рассуждений п.3 приводит к выводу: вцепи существует q вершин, не смежных с последней вершиной vn .

Отсюдаследует двойное неравенство n2 ≤ d(vn ) ≤ n − 1 − q, значитq ≤ n2 − 1 ⇔ q ≤ m − 1. Поскольку число вершин со степенями q ≤ m − 1меньше q, то хотя бы одна из вершин, предшествующим вершинаммножества S(v1 ), имеет степень не менее n2 . Значит, существует паранесмежных вершин, степени которых не менее n2 .

Это означает возврат кпротиворечию в 3 и завершает доказательство.11 / 11.