Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 107
Текст из файла (страница 107)
Додекаэдр на плоскости изображается так, как показано на рис. 14.69. Рис. 14.б9 Проблема в таком случае сводится к нахождению цикла в графе, проходящего через каждую вершину, исключая начальную, только один раз. Отсюда любой цикл графа, обладающий таким свойством, назывется гамильтоновым циклом. Этот цикл в некотором смысле противоположен эйлерову циклу, который проходит через все ребра только один раз. До определенного момента оба цикла могут показаться похожими, но дальнейшее изучение покажет, что цикл Гамильтона намного сложнее. Формально путь Гамильтона и цикл Гамильтона (гамильтонов цикл) описы- ваются следующим образом. РА311ЕЛ 14.4. Пути и циклы Гамильтона 601 ОПРЕДЕЛЕНИЕ 14.68.
Пусть С вЂ” граф. Гамильтонов путь — это простой путь, который проходит через каждую вершину графа С. Гамильтонов цикл — это простой цикл, который проходит через каждую вершину графа С. Убедимся, что граф для игры Гамильтона действительно имеет гамильтонов цикл, оправдывающий свое название. Один из таких циклов изображен на рис.
14.70. е 4 Рис. И.70 ПРИМЕР 14.69. Граф на рис. 14.71 имеет гамильтонов цикл, изображенный на рис. 14.72. Ь с Ы Рис. 14.71 Рис. 14.72 ПРИМЕР 14.70. Гиперкуб порядка и при и > 3 имеет гамильтонов цикл. Его описывет код Грея для п (см. раздел 6.7). Таким образом, гамильтонов цикл для 602 ГЛАВА 14. Некоторые специальные вопросы теории графов гиперкуба порядка 4 имеет вид 1 1 1 1 1 1 1 О 1 1 О О 1 1 О 1 1 О О 1 1 О О О 1 О 1 О 1 О 1 1 О О 1 1 О О 1 О О О О О О О О 1 О 1 О 1 О ! О О О 1 1 О О 1 1 1 1 1 1 1 ПРИМЕР 14.71. Полный граф К„при п > 3 имеет гамильтонов цикл. Пусть иы из, из,...,и„— вершины графа К„.
Поскольку между двумя любыми вершинами имеется ребро, то всегда существует ребро из и, в и;+г и, наконец, существует ребро из последней вершины и„обратно в иы П Для следующего примера необходима теорема, приведенная ниже. ТЕОРЕМА 14.72. Для любой вершины из цикла Гамильтона существует ровно два ребра из этого цикла, инцидентные данной вершине. ДОКАЗАТЕЛЬСТВО. По ходу цикла для каждой вершины 1г имеется ребро к циклу и ребро из цикла. Если бы существовало еще одно ребро цикла, инцидентное вершине й, то цикл вернулся бы в вершину И, и она опять появилась бы в цикле, что противоречит определению гамильтонова цикла. Следовательно, существует ровно два ребра, которые инцидентны вершине Ъ' из цикла Гамильтона. Заметим, что граф, у которого есть гамильтонов цикл, называют гамильтоновым графом.
И как следствие приведенной выше теоремы, получаем, что любой граф, содержащий вершину степени 1, не может быть гамильтоновым. ПРИМЕР 14.73. Граф Петерсена, изображенный на рис. !4.73, имеет гамильтонов путь, но не имеет гамильтонова цикла. Путь показан на рис. !4.?4.
РАЗДЕЛ 44,4. Пути и циклы Гамилыпона 603 Рис. И.7З Рис. 74.74 Доказательство, что граф Петерсена не имеет гамильтонова цикла, потребует некоторого количества проб и ошибок. Попытаемся построить гамильтонов цикл. Всякий раз мы будем попадать в тупик. Для начала припомним, что звезда в центре должна соединяться с внешним пятиугольником, поэтому, не нарушая общности, можно предположить, что (а, 7) — ребро в цикле. Из вершины 7 цикл должен идти к вершине 1 или вершине Ь, но, в силу симметрии, это не имеет значения, поэтому предположим, что (7,1) — ребро из цикла. Согласно предыдущей теореме ребро (7", Ь) не может входить в цикл, поскольку тогда будут три ребра, инцидентных вершине 7.
Значит, ребра (д, Ь) и (Ь,с) должны входить в цикл, поскольку это единственно возможные ребра, инцидентные вершине Ь. Если ребро (г,д) принадлежит циклу и ребро (7,1) входит в цикл, получаем, что ребро (г,д) не может принадлежать циклу, поскольку согласно предыдущей теореме только два ребра могут быть инцидентными вершине 1. Поэтому ребра (7,д) и (Ь,д) должны находится в цикле, поскольку только два ребра могут быть инцидентными вершине д.
Поскольку ребра (д, Ь) и (д,д) принадлежат циклу, ребро (д,е) не может находиться в цикле, поскольку тогда будут три ребра, инцидентных вершине 7'. Поэтому ребра (Ы,е) и (е,а) должны входить в цикл, поэтому имеется два ребра, инцидентных вершине е. В результате имеем части цикла, изображенные на рис.
14.75. е Ь Н Рис. 74.75 Поскольку ребра (г, Н) и (И,е) находятся в цикле, то ребро (д,с) не может входить в цикл, т.к. в противном случае было бы три ребра, инцидентных вершине д, поэтому ребро (с, Ь) должно быть в цикле, чтобы было два ребра, инцидентных вершине с. Поскольку ребра (Ь, д) и (с, Ь) находятся в цикле, то ребро (а, Ь) не может входить в цикл, и в результате получаем граф, изображенный на рис. 14.76, в котором больше нет ребер, чтобы добавить в цикл.
Таким образом, этот путь не может породить гамильтонов цикл. Если вернуться к рассуждениям, согласно которым ребра (а, 7'), (У, г), (7', Ь) и (Ь, с) входят в цикл, а ребро (7, Ь) не входит в цикл, поскольку (е, е1) не может быть в цикле, ребро (е',д) должно быть в цикле, поэтому имеется два ребра, инцидентных вершине г. Ребра (е, И) и (И, с) должны быть в цикле, так что имеется 604 ГЛЯВЯ 14. Некоторые специальные вопросы теории графов два ребра, инцидентных вершине г(. Поскольку ребра (Ь,с) и (с(,с) принадлежат циклу, ребро (Ь,с) не может входить в цикл, поскольку тогда будут три ребра, инцидентные вершине с. Поэтому ребра (а, Ь) и (д, Ь) должны быть в цикле, чтобы было два ребра, инцидентных вершине Ь.
Учитывая, что ребра (1,д) и (д, Ь) должны быть в цикле, ребро (г',д) не может входить в цикл, поскольку тогда будут три ребра, инцидентные вершине д. На этом этапе имеем граф, изображенный на рис. 14.77. Рис. 14.78 Рис. 44.77 Рис. 14.7б Ребро (е,г') должно входить в цикл, чтобы было два ребра, инцидентных вершине 7'. Поскольку ребра (е,г() и (е,() должны входить в цикл, то ребро (е,а) не может входить в цикл.
В результате получаем граф, изображенный на рис. !4.78, в котором не осталось свободных ребер и который не является гамильтоновым циклом. Поскольку исчерпаны все возможности построения, приходим к выводу, что граф Петерсона не имеет цикла Гамильтона. П Рассуждения, приведенные выше, убеждают в следующем: чтобы граф имел гамильтонов цикл, степень каждой вершины должна быть не меньше двух. Очевидно также, что граф должен быть связным, чтобы иметь гамильтонов цикл. Приведенная ниже теорема содержит дополнительную информацию по этому вопросу.
Доказательство теоремы предоставляется читателю. ТЕОРЕМА 14.74. Если граф С имеет разрезающее ребро, то он не может иметь гамильтонов цикл. Если компоненты графа, полученные путем удаления разрезающего ребра, имеют гамильтонов цикл, то граф С имеет гамильтонов путь, Ранее нами были найдены весьма изящные критерии существования у графа эйлерова цикла. К сожалению, никому не удалось установить необходимые и достаточные условия существования у графа гамильтонова цикла. Тем не менее, в следующей теореме приводятся некоторые условия существования у графа гамильтонова цикла. Очевидно, чем больше ребер при фиксированном числе вершин имеет граф, тем выше степень вершин и более вероятно, что имеется цикл, проходящий через все вершины, без повторения вершин. На интуитивном уровне понятно, что если одна вершина имеет более низкую степень, то это компенсируется более высокой степенью другой вершины, что отображено в приведенной ниже теореме.
ТЕОРЕМА 14.75. Если С(17, Е) — связный граф с п вершинами, где и > 3, и для каждой пары различных несмежных вершин и,о Е 17, бек(и) + дед(о) > и, тогда граф С имеет гамильтонов цикл. РД377ЕЛ 14.4. Пути и циклы Гамильтона 605 ДОКАЗАТЕЛЬСТВО. Пусть и1изиз...
и — максимальный простой путь в графе сг. Пусть а = г)ей(и1) и Ь = бей(и ). Сначала покажем, что перестановка вершин, входящих в путь, предоставляет возможность формирования простого цикла. Если вершины и1 и и — смежные, то и1игиз...и и1 — цикл, и искомый цикл найден. Если и1 и и,„смежными не являются, то а+ Ь ) п. Мы хотим показать, что в данном случае существуют вершины и, и и;.ь1, входящие в путь при условии, что вершина и1 является смежной с и,.ь1, а вершина и является смежной к и,.
Если это сделано, то начинаем путь с и1изиз... О,и,.ь1...и . Удаляем ребРо междУ и, и иыь1. Затем начинаем новый пУть с веРшины и,.ь1, пРодолжаем его до вершины и1, поскольку вершины и1.ь1 и и1 являются смежными. Продолжаем далее и, поскольку вершины и, и и являются смежными, получаем путь и,.ь1и1изиз... и,и , как показано на рис. 14.79. ч ч ° ° ° ч ч ч ч ч 1 г "' г ьи ыг г+г'" т Рис. 14.79 Движемся в обратном направлении вдоль пути и и 1и 2...и,.ьги,„1 и ПОЛУЧаЕМ ИСКОМЫЙ ЦИКЛ ига1и1О2иЗ ° ° игитит — 1ит — 2 иа-Ь2иьь1.
Теперь требуется показать, что существуют вершины и, и и11.1, входящие в путь такие, что вершина и1 — смежная с вершиной иг ь1, а вершина и смежная с вершиной и,. Предположим обратное. В таком случае вершина и1 не является смежной ни к одной из вершин, которые не входят в путь, поскольку если существует вершина ги, не входящая в путь и смежная с вершиной и1, то гии1изиз...и — простой путь, а это противоречит предположению о том, что и1игиз... и — максимальный простой путь в графе С, и тогда существует а вершин, входящих в путь и1игиз...и, смежных с вершиной и1. Аналогично, существует Ь вершин, входящих в путь и1игиз...и, смежных с вершиной и Если включить вершину и1, то путь и1игиз...и будет содержать а+1 вершин, совпадающих с вершиной и1 или смежных с ней.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
