В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич - Лекции по теории графов (1083735), страница 37
Текст из файла (страница 37)
е. ~ /„(й — 2) = и — 2. з)з Объединив два последних равенства, получим (1). Установление негамильтоковости графа путем перебора всех разбиений чисел 1, и последующей проверки выполнения равенства (1) едва ли проще полного перебора перестановок, о котором упоминалось выше, Польза теоремы 44.7 в другом — иногда удается, проанализировав числа 1„сразу сделать вывод об отсутствии подходящего разбиения, т. е.
вывод о негамильтоновости графа. Рассмотрим в качестве примера граф, изображенный Раз. 44.8 на рис. 44.8. Для этого графа (4= 1, (з = 18, (э= 4, а остальные 1з равны О. Поэтому соотношение (1) должно иметь вид 27з + 37з + 6/з — — 214+ 31з + 61з~ откуда следует, что )з= — 1,(шод3). Это, однако, невоз- Р можно, посколькУ 7з + ~з = 1з = 1. Таким обРазом, 203 нужного разбиения чисел /, не существует, и значит, граф пегамильтонов. Рассмотрим еще один класс теорем о гамильтоновых графах. В этих теоремах утверждается, что если граф С удовлетворяет определенным условиям, то граф, получаемый из С с поьшщью некоторой операции, гамильтонов. Т е о р е м а 44.8 (Ф.
Харари, С. Нзш-Вильямс, 1965 г.). Рсберный граф Л(С) галшльтонов тогда и только тогда, когда в графе С имеется цикл, содержащий хотя оы по одной вершине иг калсдого его ребра. Из этой теоремы, приводимой адесь без доказательства, вытекает, в частности, что если граф С является эйлеровым или гамильтоновым, то реберный граф 1 (С) гамильтонов. Интуитивно лспо, что если граф С порядка п - 3 связен, то при достаточно больпюм к граф С' гамильтонов (определение графа С" см. в з 8).
Кроме того, пз гамильтоповости графа С' очевидно следуе~ гамильтоповость графа С'+'. В связи с этим представляет интерес наименьшее й, при котором граф 6" гамильтонов. Теорема 44.9 (Д. Карагапис, 1968 г.). Если граф С пор~дна и ~ 3 связен, то Сз — гамильтонов граф. Ь Теорему достаточно доказать для случая, когда С вЂ” дерево. Будем доказывать слодующее, несколько более сильное утверждение: для любого фиксированного ребра аЬ дерева С граф Сз содержит галшльтонов цикл, проходящий через аЬ.
Это утверждение легко проверить непосредственно для деревьев с числом вершин не более четырех. Предположим, что существуют деревья с ббльшим числом вершин, для которых оно не верно. Выберем из пих дерево Сь с минимальным числом вершин. Пусть аЬ вЂ” некоторое ребро дерева Сь. При удалении этого ребра Сс распадается на два дерева С~ и Сг таких, что а ш ГСь Ь ш ГСг. По крайней мере одно пз них, например Сь содержит пе менее трех вершин. Выберем верппшу и ~ ГС1 так, чтобы ребро иа принадлежало ЕСь Поскольку ~ГС~! ( 1ГС„~, то С," со ~ержит гамильтонов цикл Пь проходящий через ребро оа.
Теперь рассмотрим дерево Сг. Сначала допустим, что 1ГСг! ~ 3, и пусть Ьх — ребро графа См иппидептпое вершние Ь. Поскольку ~ ГСг! ( ~ ГСь!, то С', сотержпт гампльтопов ппкл Нг. про;одящпй через ребро Ьх. Использун циклы Н~ и Нз, легко построить цикл Н в графе 204 Сг, проходящий через аЬ. Для этого достаточно удалить ребра ао и Ьх из 111 н Нг соответственно и добавить ребра аЬ и хо, т.
е. положить Н = (Н1 — оа) 0 (Нг — Ьх) + хо+ аЬ. Пусть теперь !УСз~ =2, т. е. Сг состоит из одного ребра Ьс. Тогда положим Н = (Н~ — оа)+ аЬ + Ьс+ ос. Пакопец, если 6г содержит единственнуго вершину Ь, то Н =(Н1 — оа)+ аЬ+ Ьо. Итак, во всех случаях граф Сг гсодержит гамильтонов цикл Н, проходящий через ребро аЬ дерева Св, что противоречит выбору 6г. 'З Легко указать граф, квадрат которого негамильтонов. Таков, например, граф, получающийся из звезды К~г подразбиением каждого ребра. Следующая теорема, приводимая без доказательства, является наиболее значительным результатом среди всех, касающихся гамильтоновых циклов в степенях графов.
Теорема 44.$0 (Г. Флейшнер, 497( г.). Нели 6— двусвягный граф порядка п ~ 3, то Сг — гамильтонов граф. Во многих прикладных задачах требуется строить гамильтопову цепь, а не цикл. Граф, содержащий такую цепь, называется трассируемым. Задачи о гамильтоновой цепи и гамильтоновом цикле эквивалеятны в том смысле, что, умея решать одну из них, мы смогли бы решить и другую. Эту эквивалентность можно установить с помощью очень простых конструкций.
Вместе с исходным графом С, для которого надо решать обсуждаемые задачи, рассмотрим новые графы 6' и С" (аЬ). Граф С' получается добавлением к графу 6 новой доминирующей вершины, а 6" (аЬ) — добавлением к С двух вершин г и у и пары ребер га и уЬ (а, Ьш РС). Теперь легко видеть, что граф 6 является трассируемым тогда и только тогда, когда граф С' гамильтонов.
С другой стороны, очевидно, что гамильтоновость графа 6 эквивалентна существованию гамильтоновой цепи хотя бы в одном иа графов С" (оЬ), оЬ ж ЕС. Приведеппгяо конструкции иллюстрируются на рнс. 44.9. Практические применения только что рассмотренного раздела теории графов связаны прежде всего с широко 205 известной задачей коммивояжера. Она состоит в следующем: коммивояжер доляген посетить каждый из заданных п городов по одному разу, выехав из некоторого из этих городов и вернувшись в него же. Требуется найти кратчайший маршрут, зная расстояния между каждой парой городов.
Математическая постановка этой задачи выглядит так: в полном взвешенном графе требуется найти гамильтонов цикл (или цепь) минимального веса. Под весом цикла понимается сумма весов составляющих его ребер. Например, при производстве печатных плат сверлильный станок с числовым программным управлением должен сделать большое количество отверстий в заданных е о' Рис. 44, 9 е 8'7ае! точках платы, переходя от одной точки к другой. Время работы такого станка складывается из суммарного времени сверления, которое не зависит от порядка обхода точек, и из суммарного времени переходов от одной точки к другой. Требуется задать такую последовательность обхода точек, чтобы общее время работы станка было минимально.
Легко видеть, что это — задача коммивояжера. Представление о непосредственных применениях гамильтоновых цепей дает следующая ситуация: имеется машина (станок, компьютер) и и заданий, калсдое из которых она способна выполнить после соответствутощей настройки. При этом необходимо затратить на переналадку ~о единиц времени для того, чтобы после выполнения е-го задания выполнить )-е.
В предположении, что Ге= 1„, требуется найти последовательность выполнения заданий, прн которой время канадой перепаладки пе превосходит величины й Если построить граф С, у которого Ю = (1, 2, ..., и), Еб=(е): 4о~4), то паша задача сведется к отысканию гамнльтоповой цепи в этом графе. В заключенно отметим без доказательства теорему, отражающую типичный случай. Теорема 44.11 (В. А. Перепелпца, 1969 г.). Почти все графы гамильтоновьг. У П Р Л?Н Н Н Н И Я 1.
Дока)ггкте, что граф является энлеровым тогда и только тог- да, когда каждый его блок эйлеров. 2 Докажите, что айлеров граф является объединением ребер- но-непересекающихся простых циклов, 3. Пусть 6 — дерево. Когда граф 6' эйлеров? 4. Какии должен быть граф С, чтобы ребериый граф й(6) был эйлеровым? 5. Покалгкте, что граф Петерсена пегамильтонов. 6, Найдите связный граф 6 с минимальным числом вер- шин, большим 2, для которого граф С' негамильтопоз. 7. Приведите пример такого реберно-2-связного графа 6, что граф 6' кегамильтонов. 8.
Граф называется гамильтопове-связным, если любые две его вершины соединены гамильтоновой цепью. Является ли трех- мерный куб Сз гамильтопово-связным? 9. Негамильтонов граф 6 пазывается гипогамильтеновым, если граф С вЂ” х гамильтонов для любой вершины х. Покавгите, что граф Петерсена гипогамильтонов. 10. Докажите, что всякий гамильтоново-связный граф порядка и ) 3 является З-связньш. 11. Пусть т и и — натуральные числа, С вЂ” граф решетки, т. е. УС = ((х, у); х = 1, ю, у = 1, и) и аЬ ш ЕС тогда и только тогда, когда а=(х, у), Ь=(ц г) и ]х — з]=1 или ]у — г]=1. При каких т и п граф С гамильтонов? 12. Пусть в плоеном 3-связном графе С существует грань, име- ющая с любой другой его гранью хотя бы одно общее ребро.
По- кажите, что граф 6 гамильтонов. 13, Покал<ите, что связный граф являетсл гамильтоновым, ес- ли его группа автоморфизмов содержит полный цикл. 14. Покажите, что регулярный граф степени 4, окружение каждой вершины которого связно, является гамнльтоповым, 15. Для каждого и ) 4 приведите пример пегамильтопоза ([а/2] — 1)-связного п-вершинного графа.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
