Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 108
Текст из файла (страница 108)
Существует также Ь вершин, входящих в путь и1игиз... и и смежных с вершиной и . Если для каждой вер- ШИНЫ О„ВХОдящЕй В ПутЬ, СМЕЖНОЙ С ВЕрШИНОй и, ВЕрШИНа иьь1 НЕ яВЛяЕтСя смежной с вершиной и1, то путь содержит а+ 1 вершин, совпадающих с вершиной и1 или смежных с ней, и Ь вершин, входящих в путь, которые не совпадают с вершиной и1 и не смежные с ней. Таким образом, путь и1игиз... и содержит а+ 6++1 различных вершин, что невозможно.
Следовательно, сделанное предположение было неверным, и существуют вершины иг и иьь1, входящие в путь и такие, что вершина и1 — смежная с вершиной иьь1, а вершина и — смежная с вершиной и,. Таким образом, искомый цикл получен. Предположим для простоты, что вершины переобозначены, так что цикл имеет вид и1изиз...и и1.
Покажем теперь, что этот цикл содержит все вершины множества Ъ'. Если это не выполняется и вершина и' не совпадает ни с одной из вершин и,, то, поскольку граф С связный, существует путь из вершины и' в одну из вершин ип и существует вершина ги, которая не входит в путь и1игиз...и и является смежной с одной из вершин и.. Но тогда гииуига1иуь2 Ьти1и2иа - ° иг-1 606 ГллВА 14. некоторые специальные вопросы теории графов простой путь, который длиннее, чем путь егозив...о, что является противоречием.
Следовательно, цикл огозоз...и ог является гамильтоновым циклом. ° Нз теоремы непосредственно вытекает следствие, которое получено раньше и является более известным, чем сама теорема. СЛЕДСТВИЕ 14.76. Если С(1; Е) — связный граф, имеющий и вершин, где п > 3, и если для каждой вершины о 6 Ъ' выполняется г1ея(о) > -", то граф С имеет гамильтонов цикл. При доказательстве теоремы 14.75 был использован только тот факт, что сумма степеней вершин ог и о максимального пути огозоз...о больше, чем число вершин.
Поэтому получаем такое развитие теоремы 14.75. ТЕОРЕМА 14.77. Пусть С(1г, Е) — связный граф с и > 3 вершинами и пусть и и о — несмежные вершины графа С такие, что с1ея(и) + деа(и) > п. Отсюда граф С', состоящий из графа С с присоединенным ребром е = (и,о), имеет гамильтонов цикл тогда и только тогда, когда граф С имеет гамильтонов цикл.
ДОКАЗАТЕЛЬСТВО. Если граф С имеет гамильтонов цикл, то и граф С' имеет гамильтонов цикл, т.к. для него используется тот же самый цикл. Обратно, предположим, что граф С' имеет гамильтонов цикл. Если ребро е не входит в цикл, то вполне очевидно, что граф С имеет гамильтонов цикл.
Если ребро е не принадлежит циклу, то гамильтонов цикл в графе С' записывается в виде ио~изоз и ои. Но в этом случае ио,гаоз . о о — гамильтонов путь в графе С и, следовательно, является максимальным путем, и, кроме того, г1е8(и)+г1еК(о) > п. Согласно доказательству предыдущей теоремы вершины этого пути можно переставить так, что они образуют цикл в графе С.
Поскольку этот цикл содержит все вершины графа С, то это гамильтонов цикл. Пусть имеется граф С с п вершинами. Добавляем ребра к несмежным вершинам и и и графа С, для которых г1ея(и) + с1ея(о) > п, до тех пор, пока это возможно. По завершении процесса полученный граф назовем замыканием графа С. ОПРЕДЕЛЕНИЕ 14.78. Пусть С вЂ” граф с п вершинами. Замыканием графа С, обозначаемым с!(С), называется граф, полученный из графа С рекурсивным добавлением ребер к несмежным вершинам и и о графа С, для которых Йе8(и)+де6(о) > п до тех пор, пока это возможно.
Таким образом, с1(С) обладает свойством, что если в графе с1(С) есть две несмежные вершины и и о, для которых Йе8(и)+Йе8(о) > п, то между этими вершинами существует ребро. Необходимо показать, что с1(С) определено корректно. Это означает, что если получить граф С' из графа С путем рекурсивного добавления ребер к несмежным вершинам и и о графа С, для которых де8(и)+бе8(и) > п, пока это возможно, и граф Сн из графа С путем рекурсивного добавления ребер РЛЗДЕ// 14.4. Пути и циклы Гамильтона 607 к несмежным вершинам и и и графа С, для которых Йей(и)+де8(и) > п, пока это возможно, но другим рекурсивным способом, то С' = С".
Для доказательства данного утверждения предположим, что е',, ез, ез,..., е/ — ребра, рекурсивно добавленные к графу С для построения графа С', а е~', е~з, ез',..., е,"„— ребра, рекурсивно добавленные к графу С для построения Си Если ребра не совпадают, то сушествует, например, ребро в графе С', которое не принадлежит графу С". Пусть е' — первое ребро, рекурсивно добавленное для получения графа С', которое не принадлежит графу С", и пусть е' = (и,и). Тогда с ребрами е',,ез,ез,...,е' добавленными к графу С, де8(и)+йе8(и) ) п. Но поскольку е' — первое ребро, рекурсивно добавленное для получения графа С', которое не входит в граф С", то РебРа е'„ ез,ез,...,е' , входЯт в гРаф С".
Следовательно, с/е8(и)+с/е8(и) > и в графе С", но между вершинами и и и не сушествует ребро, что и приводит к противоречию. Следовательно, С' = С", поэтому замыкание с1(С) определено однозначно. Отметим, что для произвольного графа С с1(с1(С)) = с1(С) ПРИМЕР 14.79. Если С вЂ” граф, изображенный на рис. 14.80, то с1(С) — граф, изображенный на рис. 14.81.
Ь с Ь с Рис. 14.81 Рис. 14.80 ПРИМЕР 14.80. Если С вЂ” граф, изображенный на рис. 14.82, то с1(С) — граф, изображенный на рис. !4.83. а Ь а Ь с Ы е Рис. /4.82 Рис. 14.83 ПРИМЕР 14.61. Если С вЂ” полный двудольный граф К при гп ) 1, то с1(С)— полный граф К П Предлагаем читателю доказать приведенную ниже теорему, используя метод индукции и теорему 14.77. ТЕОРЕМА 14.82. Граф С имеет гамильтонов цикл тогда и только тогда, когда граф с1(С) имеет гамильтонов цикл. 608 ГЛА8А 14. Некоторые специальные вопросы теории графов На основе теоремы и примера, приведенных выше, получаем, что при т ) 1 полный двудольный граф К имеет гамильтонов цикл.
° УПРАЖНБНИЯ 1. Найдите гамильтонов цикл, если он существует, для каждого из приведенных ниже графов. а) б) г) в) ь д) 2. Найдите гамильтонов цикл, если он существует, для каждого из приведенных ниже графов. а) б) в) г) а Ь с д) б) Ь г) с Ь 3. Найдите гамильтонов путь, если ных ниже графов.
а) РКЗДЕП 14.4. Пути и циклы Гамильтона 609 он существует, для каждого из приведен- От 0 ГЛАВА т4. Некоторые специальные вопросы теории графов 4. Найдите гамильтонов путь, если он сушествует, для каждого из приведенных ниже графов. а) б) а Ь с г) в) а Ь с ь Я д) а Ь с И с 7' Я Ь 1 У 8. Докажите теорему 14.74. Если граф С имеет разрезающее ребро, то граф С не может иметь гамильтонов цикл. Если компоненты графа, полученные при удалении разрезающего ребра, имеют гамильтоновы циклы, то граф С имеет гамильтонов путь. 6.
Нарисуйте граф с шестью вершинами, который имеет гамильтонов цикл, но не имеет эйлерова цикла. 7. Нарисуйте граф с шестью вершинами, который имеет эйлеров цикл, но не имеет гамильтонова цикла. 8. Используя теорему 14.77 и метод индукции, докажите теорему 14.82. Граф С имеет гамильтонов цикл тогда и только тогда, когда его замыкание с11С) имеет эйлеров цикл. рлздсп э4.5. Вэеешенные графы и алгоритмы поиска кретчеишего пути 611 14.5.
ВЗВЕШЕННЫЕ ГРАФЫ И АЛГОРИТМЫ ПОИСКА КРАТЧАЙШЕГО ПУТИ До сих пор при рассмотрении графов нас интересовали вершины и ребра, по которым можно перемещаться. Теперь нас интересует не только перемещение из точки А в точку В, но и то, как это сделать наилучшим способом. Первый вопрос состоит, конечно, в том, что означает "наилучшим способом". Это может быть самый дешевый путь, самый безопасный путь, кратчайший путь или тот, который требует минимум энергии, или путь, выбранный в соответствии с каким-то иным критерием.
Для определения наилучшего пути присвоим каждому ребру вес или меру. Если пытаться найти кратчайшее расстояние между двумя городами, то их необходимо представить в виде вершин, а вес, присвоенный ребрам, — это расстояние между городами. Если пытаться найти самый дешевый способ перелета нз одного города в другой, то вес ребер между вершинами, представляющими города, будет стоимостью перелета из города в город. Если прямого перелета между городами нет, то не будет ребра между соответствующими вершинами.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
