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

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Методы дискретной оптимизацииГамильтоновы пути и циклы. Пути, имеющиетип цикла и достаточные условиясуществования гамильтоновых путей ициклов в неориентированном графе. ТеоремаПоша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.

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов лекций