В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич - Лекции по теории графов (1083735), страница 36
Текст из файла (страница 36)
В этом графе для каждой вершины уж ИС имеется (о, у)-цепь. Выберем из этих цепей кратчайшую (о, уа)- цепь Р*. Учитывая, что С вЂ” макспмалыгый цикл, имеем у*о'--' а, у* т-- Ь. Кроме того, Р" не содержит вершин цикла С, отличных от у*, так как иначе можно было бы построить более короткую цепь. Объединив цикл С и цепь Р", получим искомый тэта-подграф. < Несмотря на внешнее сходство постановок, задачи распознавания эйлеровости и гамильтоновости графа принципиально различны, Используя теорему 43.1, легко узнать, является ли граф эйлеровым. В случае положительного ответа алгоритм Флери позволяет достаточно быстро построить одни иа эйлеровых циклов. Что касается гамнльтоновости, то ситуация здесь существенно иная.
Ответить па вопрос, является лн данный граф гамильтоновым, как правило, очень трудно. Очевидно, что проблема распознавания гамнльтоповостп графа есть частный случай проблемы нзоморфпого подграфа. Изучение условий гамильтоновости графов — одно нз весьма популярных направлений теории графов.
Основ- 197 ная масса доказанных адесь теорем утверждает, что при выполнении определенных условий граф содержит гамильтонов цикл, причем метод доказательства таких теорем обычно дает и эффективный алгоритм построения самого гамильтонова цикла. В этом параграфе мы рассмотрим несколько теорем такого рода (достаточных условий гамильтоповости). Интуитивно ясно, что если граф содержит много ребер и эти ребра к тому же достаточно равномерно распределены, то граф «предрасположен» быть гамильтоновым.
В трех приводимых ниже теоремах можно усмотреть подтверждение этому. Напомним, что степенной последовательностью графа называется список степеней его вершин. Теорем а 44.2 (В. Хватал, 1972 г.). Граф со степенной последовательностью д1 < аг «... а"„является гамильтоновым, если для всякого й, удовлетворяющего неравенствам 1 < к < и!2, истиш»а импликаиия (И»< Й)~(с(»~ и — к). ь" Теорему докажем от противного. Пусть существует негамильтопов граф, последовательность степеней вершин которого удовлетворяет условиям теоремы. Соединив две несмежные вершины такого графа ребром, получим, как легко видеть, граф со степенной последовательностью, снова удовлетворяющей условиям теоремы.
Так как полный граф гамильтонов, то отсюда следует, что существует максимальный негамильтонов граф, степенная последовательность которого обладает таким же свойством. Этот граф будем обозначать через 6. Таким образом, добавление любого нового ребра к графу 6 приводит к появлению в нем гамильтонова цикла. Поэтому любые две его несмежные вершины соединены гамнльтоновой цепью. Выберем в графе 6 пару несмежных вершин о1 и и„ так, чтобы величина деао1+с)еао была максимальной. Пусть оп ом ..., о — гамильтонова цепь, соединяющая эти вершины.
Если в графе 6 вершины о1 и о, смежны, то вершина о„не может быть смежной с о,-н поскольку в противном случае граф 6 содержал бы гамильтонов цикл (уп ом ..., щ — и у, Р— и ур-2, ..., у»»п пп у1) (рис. 44.4) . Таким образом, вершина о„не смежна по крайней мере с дел о1 вершинами, и поэтому дед о < $98 < и — 1 — дел оь Отсюда получаем йец о~+ деа о„< и — 1 < и.
Для определенности будем предполагать, что деа о~ < < йеи о„. Это вместе с предыдущим неравенством дает бек о~ < и/2. Поскольку величина деи о1+ дел о„максимальна, то степень каждой вершины, не смежной с о„, не о,„ь„го,, о, Ряс. 44.4 превосходит дедок При этом таких вершин, как уже отмечалось, не менее чем бе~ оь Поэтому выбрав й = дел он получим с/, < й < и/2. Следовательно, по условию теоремы д „~ п — /с. Последнее означает, что имеется по крайней мере й+ 1 вершин степени не меньше чем и — й. Такими вершинами являются, например, вершины со степенями с/„, д„н, д„„.
Поскольку Йеио|=/г, то о1 не может быть смежной со всеми этими вершинами, и, значит, найдется такая вершина оь не смежная с он что Йеио,~ ) и — й, Но тогда дел о1+ Йеа о, ~ /г + (и — й) ) дед о1+ Йеи о., что противоречит выбору вершин о1 и о„. '1 С помощью только что доказанной теоремы можно получить ряд других достаточных условий гамильтоновости. Эти условия проще и, естественно, слабее теоремы 44.2. Теорема 44.3 (О. Оре, 1960 г.). Если для любой пары и и о нссмслсных вершин графа 6 порядка п > 3 выполняется неравенство ахеи и+ дед о > и, то Г' — гамильтонов граф.
~> Пусть )т6=Ьн ою ..., о„), А=дедов 1=1, и, и А < г/г «... д„— степенная последовательность графа О. Согласно теореме 44.2 достаточно показать, что условие нашей теоремы обеспечивает выполнение неравенств дг ~ й, й = 1, [и/2 — 1] . Доказательство проведем от противного. Пусть для некоторого 1ш(1, ..., 1н/2 — 1)) выполняется неравенство д, - й Сущоствовапие индексов 1 и 1 таких, что 1, 1 -1 и о,о, Ф ЕС, привело бы к неравенствам д;+д,< 2д,(21(п, противоречащим условию теоремы. Следовательно, вершины оп ог, ..., о, попарно смежны, Это вместе с неравенствамэг 4 (1 (1= 1, 1) означает, что каждая вершина и, (1= 1, 1) смежна пе более чем с одной вершиной и, 1+ 1-= и -- п.
Далее, поскольку г ( п!2, то п — г ) й Поэтому пайдетси верпшна оь г+ 1 -у (и, не смежная пи с одной пз вершин и, (1= 1, 1). Следовательно, дед с,- -- и — т — 1. 11о тогда для пары несмежных вершин о, и о; пмоем неравенство дед о, + дед о, ( п, которое противоречит условп1о теоромы. < Из этой теоремы непосредственно вытекает следуюгдан Теорема 4гь4 (Г.
Дирак, 1052 г ). Ьсли !С! = и ~ 3 и для любой вершины о графа С выполняется неравенство дед о ) и~2, то С вЂ” гамильтонов граф. Нетрудно заметить, что во всяком и-вершинном графе, удовлетворяющем условиям любой из рассмотренных вылив теорем 44.2 — 14.4, число ребер пе меньше чем (и — 1)г(4, С другой стороны, и-воршинныи плапарный граф, как мы знаем, содержит не более Зп — 6 ребер.
Поэтому рассъштреппые выше достаточные условия заведомо неприменимы к плапарпым графам. Легко укэаать 2-связный негамильтопов планарпый граф. Таким графом является, например, тэта-граф. Привести пример 3-связного планарного графа без гампльтопова цикла уже не столь просто. Такой граф, оказывается, должен содерв ать не менее 11 вершин. Этот факт балл установлен Д. Барнеттом и К. Юковичеьг (1970 г.). 11айдепный ими пегамильтонов планарный 3-свизный граф с Рве. 44.5 минимальным числом вершин изо- бршкен на рпс. 44.5. Б том, что этот граф пе содержит гампльтопова цикла, можно убедиться, проделав не слппгком болыпой в данном случае перебор вариантов. Проще, однако, заметптгэ что он — двудольпый и, следовательно, пе содержит циклов нечетной длины, в частности, гампльтоновых циклов.
Следу|ощая теорема — один пз наиболее сильных результатов, касающихся гамильтоповых графов. 200 Теорема 44.5 (У. Татт, 1946 г.). Всякий 4-связный нланврлый граф является гаянльто~овызь Весьма сложное доказательство этой теоремы здесь опускается. Следствие 44.6 (Х. Уитни, 1932 г.). Если в максимально.и плоском графе С «галса«ай Звцикл является гранвцей некоторой грани, то С вЂ” гвл»вльтонов граф, Г 1(ак и:шест«то (следствие 39.2), всякий макси»«а,п,— шай плоский граф 3-связок.
Если же такой граф пе является 4-связным, то оп необходимо содержит З-цикл, не являющийся границей пикакой грани (см. упр. 12 гл. У1). З а с Пример максимального планарного пегамильтопова графа С с 11 вершинами приведен па рис. 44.6. От- рав. 4ть6 сутствие гамильтопова цикла следует нз того, что шесть вершин графа С, помеченных знаком «+», попарно пе смежны, а на цикле длины 11 могут лежать пе более пяти таких вершин. Согласно следствию 44.6, этот граф должен содоржать З-цикл, не являющийся границей никакой грани. Такими 3-циклами являются, например, (а, Ь, с) н (а, с, а).
Если в п-вершинном графе С фиксировать одну вершину и обход всогда начинать с поо, то всякому гамильтонову циклу очевидным образом будет соответствовать перестановка элементов множества )тС. Тем самым найти гамильтонов цикл либо убедиться в отсутствии такого цикла можно путем перебора (и — 1)! перостановок. Если граф С гамильтонов, то проделать этот поребор в полном объеме придется тол«ко в случае край««его повезенил — когда нужная, т.
е. отвеча»ощая гаиильтопову циклу порестановка встретится последней в этом процессе. Если же С вЂ” ногаиильтопов граф, то дойствуя подобным образом, придется в любо»«случае проверить все (и — 1)! перестановок. 11а практике пе пользуются столь бесхитростныи способом распознавания гамильтоповости, а применяют различные алгоритмы частичного перебора. Однако и там наблюдается такой жо эффект — т. е.
негамильтоновость 201 устаповитгч как правило, труднее, чем гамильтоновость. В этой ситуации были бы полезны необходимые условия гамильтоновостн. Такие условия нужны и для построения примеров негамильтоновых графов с заданными свойствами. К сожалению, для графов общего вида необходимые условия гамильтоновости неизвестны, за исклнзчеппем уже упомипавгпегося банального факта, что гамильтонов граф должен быть 2-связным. Иначе обстоит дело с планарпыми графами. Всякую грань плоского графа, граница которой содержит ровно й ребер, назовем й-гранью. Теор ем а 44.7 (Э.
Я. Гринберг, 1968 г.). Пусть 7'„— число 7с-граней плоского графа 6. Если 6 — гамильтонов граф, то для каждого й > 3 существуют такие целые неотРиЦательные числа тз, )з, что тз+ 1з=Ло Х Дз(к — 2) = ~ Л,(й — 2). з>з з>з с Пусть граф С содерягит гамильтонов цикл С. Этот цикл делит плоскость па две часта — ограпичепную— Р~ и неограниченную — Рг.
Тем самым граф 6 представляется в виде объединения двух графов 61 и Сг, содержащихся в Р~ и Рг соответствешю. Ясно, что Р1 — грань 3 сз з си Рис. 44.7 графа Сг, Рг — грань графа С~ и Е61 О ЕСг=ЕС. Пусть 7з — число й-граней графа Си отличных от Рг, а Л,— число й-граней графа Сг, отличных от Рь Очевидно, что В графе С, изображенном па рис.
44.7, ребра гамильтопова цикла С обведены жирными линиями. Граф 6~ включает, помимо цикла С, ребра оьог, огиз, изин изот, азиз, а граф Сг — ребра огиз н изо,з. В этом примере Ь=5,)4=2,~в=~в=1 (з=4 /з — — 2,ге=аз=5=1, а остальные /з, 7„,7з Равны О. 202 Возвращаясь к доказательству, установим теперь справедливость равенства (1). С этой целью заметим, что удвоенное число ребер графа 61 равно Х ~ай + и, а чис- з>з Р ло всех его граней — ~„' /з + 1. Поэтому, согласно фор- а>з муле Эйлера, можем написать ~~.", 1зй+ и — 2( ~ (з+ 1) = 2(п — 2). з~)з Мз После очевидных упрощений имеем ,,"~ 7з(й — 2) = п — 2. з>з Аналогичное соотношение верно и для графа с'з, т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
