Дискретная математика (998286), страница 47
Текст из файла (страница 47)
Эйлеров цикл содержит не только все ребра (по одному разу), но и все вершины графа (возможно, по несколько раз). Ясно, что эйлеровым может быть только связный граф. ТЕОРЕМА Если граф ск связе~ и нетривиален, то следующие утверждения эквивалентны: 1. С вЂ” эйлеров граф; 2. каждая вершина ск имеет четную степень; 3. множество ребер С можно разбить на простые циклы. Доказательство 1 ~ 2 Пусть Я вЂ” эйлеров цикл.
Двигаясь по Я, будем подсчитывать степени вершин, полагая их до начала прохождения нулевыми. Прохождение каждой вершины вносит 2 в степень этой вершины. Поскольку Я содержит все ребра, то когда обход Я будет закончен, будут учтены все Ребра а степени всех вершин — четные. 2 =ь 3 сг — связный и нетривиальный граф, следовательно, Ч и Н(е) > О. Степени вершин четные, следовательно, Чи д(и) > 2. Имеем: 2в=~ Ы(е) >2р=ьв>р=~д>р-1.
Следовательно, граф сг — не дерево, а значит, граф С содержит (хотя бы один) простой цикл Еь (Яг — множество ребер.) Тогда ск — Яг— остовный подграф, в котором опять все степени вершин четные. Исключим из рассмотрения изолированные вершины. Таким образом, ск — Яг тоже удовлетворяет условию 2, следовательно, существует простой цикл г з с (С вЂ” Яг). Далее выделяем циклы Яо пока граф не будет пуст.
Имеем: Е = () Яг и П 2'г = а. 2Е4 Глава 10. Циклы З =ь 1 Возьмем какой-либо цикл Ят из данного разбиения. Если Вг = Е, то теорема доказана. Если нет, то существует цикл Вг, такой что 3 о~ (иг й Я~ Й ог й Уг), так как С свЯзен. МаРшРУт Вг Г1 Яг ЯвлЯетсЯ Циклом и соДеРжит все свои ребра по одному разу. Если Я, 11Ег = Е, то теорема доказана. Если нет, то существует цикл Яз, такой что Лог (ог П Ыг с1 Яг Йог й Яз). Далее будем наращивать эйлеров цикл, пока он не исчерпает разбиения.
П 10.2.2. Алгоритм построения ейлерова цикла в зйлеровом графе В предыдущем разделе был установлен эффективный способ проверки наличия эйлерова цикла в графе. А именно, для этого необходимо и достаточно убедиться, что степени всех вершин четные, что нетрудно сделать при любом представлении графа. Следующий алгоритм находит эйлеров цикл в графе, если известно, что граф эйлеров. Алгоритм 10.1. Алгоритм построения зйлерова цикла Вход: эйлеров граф С(Ъ', Е), заданный списками смежности (Г[в] — список вершин, смежных с вершиной в). Выход: последовательность вершин эйлерова цикла. о: = а ( стек для хранения вершин ) ве1ест е е Ъ ( произвольная вершина ) и — + Я ( положить е в стек Я ) ттЫе Я ф о оо е ~ — Я; е -+ Я ( э — верхний элемент стека ) 1Г Г[и] = й сйеп е + — Я; у1еЫ е е1ве ве!ес1 и е Г[и] ( взять первую вершину нз списка смежностн ) и -+ Я ( положить и в стек ) Г[е]: = Г[е] ~ (и); Г[и]: = Г[и] '1 [е) ( удалять ребро (э, и) ) епо' 1г епп чрй!е ОБОСНОВАНИЕ Принцип действия этого алгоритма заключается в следующем.
Начиная с произвольной вершины, строим путь, удаляя ребра и запоминая вершины в стеке, до тех пор пока множество смежности очередной вершины не окажется пустым, что означает, что путь удлинить нельзя. Заметим, что при этом мы с необходимостью придем в ту вершину, с которой начали. В противном случае это означало бы, что вершина и имеет нечетную степень, что невозможно по условию. Таким образом, из графа были удалены ребра цикла, а вершины цикла были сохранены в стеке Я. Заметим, что при этом степени всех вершин остались четными.
далее вершина о выводится в качестве первой вершины эйлерова цикла, а процесс продолжается, начиная с вершины, стоящей на вершине стека. П 265 1О.З. Гамильтоиоеы циклы 10.2.3. Оценка числа зйлеровых графов ЛЕММА В любом графе число вершин нечетной степени четно. Доказательство По теореме Эйлера ~ а(о) = 2д, то есть сумма степеней всех вершин — четное число. Сумма степеней вершин четной степени четна, значит, сумма степеней вершин нечетной степени также четна, значит, их четное число. Е1 Пусть Яр) — множество всех графов с р вершинами, а Е(р) — множество эйле- ровых графов с р вершинами. ТЕОРЕМА Эйлеровых графов почти нет, то есть йш — = О. !Е(.)! !Яр)! Доказатвльство Пусть Е'(р) — множество графов с р вершинами и четными степенями. Тогда по предыдущей теореме Е(р) с Е'(р) и !Е(р)! < !Е'(р)!. В любом графе число вершин нечетной степени четно, следовательно, любой граф из Е'(р) можно получить из некоторого графа Яр — 1), если добавить новую вершину и соединить ее со всеми старыми вершинами нечетной степени.
Следовательно, !Е'(р)! < (9(р — 1)!. Но )Яр)! = 2с!в з!. Заметим, что Ы (/с — 1)! 2!((г — 2)! 2!(й — 3)! 'н(И вЂ” 1) (!г — 1)((т — 2) (!к — 1)((а — Е + 2) 2 2 2 Далее имеем: (Е(р)! < /Е'(р)! < /о(р 1)! 2с!р-1д! 2с!рз)-!р-т! 5~ )!2 !р л и — < —, откуда 1пп Е(р) 1 . !Е(р)! = О. 9(р) 2 -' !9(р) ! 10.3. Гамильтоновы циклы Название ягамильтонов цикл» произошло от задачи «Кругосветное путешествие», придуманной Гамильтоном' в прошлом веке: нужно обойти все вершины графа, диаграмма которого показана на рис.
10.1 (в исходной формулировке это были названия столиц различных стран), по одному разу и вернуться в исходную точку. Этот граф представляет собой укладку додекаэдра. т Вильям Гамильтон (1805-!856) Глава 10. Цикпи Рис. 10.1. Задача «Крэтосветное путешествие» 10.3.1.
Гамильтоновы графы Если граф имеет простой цикл, содержащий все вершины графа (по одному разу), то такой цикл называется гамнльтоновым циклом, а граф называется гамильтоновым графом. Гамильтонов цикл не обязательно содержит все ребра графа. Ясно, что гамильтоновым может быть только связный граф. 3 АМ ЕЧАН И Е Любой граф С можно превратить в гамильтонов, добавив достаточное количество вершин. Для этого, например, достаточно к вершинам ш,..., эр графа С добавить вершины иы...,ир и множество ребер ((сои;)) ш ((иот+ь)). ТЕОРЕМА (Дирак) Если в графе С(У, Е) Чи Е У гг(и) > р/2, то граф С является гамильтоновым. Доклзлтвльство От противного.
Пусть С вЂ” не гамильтонов. Добавим к С минимальное количество новых вершин им...,и„, соединяя их со всеми вершинами С так, чтобы С':=С+ и1 + + и„был гамильтоновым. Пусть и,и„ю,...,и — гамильтонов цикл в графе С', причем и Е С, иг Е С', иг )г С. Такая пара вершин и и и, в гамильтоновом цикле обязательно найдется, иначе граф С был бы гамильтоновым. Тогда ю е С, ю )г 1иш...,и„), иначе вершина иг была бы не нужна. Более того, вершина и несмежна с вершиной ю, иначе вершина иг была бы не нужна. Далее, если в цикле и, иш ю,..., и', ю',..., и есть вершина ю', смежная с вершиной ю, то вершина и' несмежна с вершиной и, так как иначе можно было бы построить гамильтонов цикл и,и',...,ю,ю'... и без вершины ип взяв последовательность вершин ю,..., и' в обратном порядке.
Отсюда следует, что число вершин графа С', не смежных с и, не менее числа вершин, смежных с ю. Но для любой !0.3. Гамипьтоиовы циклы вершины щ графа С И(гп) > р/2+ ц по построению, в том числе с!(о) > р/2+ п Общее число вершин (смежных и не смежных с о) составляет п+ р — 1. Таким образом, имеем: п + р — 1 = 3(о) + г!()г) > И(щ) + г((е) > — + п + — + п = 2п + р, 2 2 Следовательно, 0 > п+ 1, что нротнворечит тому, что п > О.
П 10.3.2. Задача коммивояжера Рассмотрим следующую задачу, известную как задача коммивояжера. Имеется р городов, расстояния между которыми известны. Коммивояжер должен посетить все р городов по одному разу, вернувшись в тот, с которого начал, Требуется найти такой маршрутдвиження, при котором суммарное пройденное расстояние будет минимальным. Очевидно, что задача коммивояжера — это задача отыскания кратчайшего гамильтонова цикла в полном графе. Можно предложить следующую простую схему решения задачи коммивояжера: сгенерировать все р! возможных перестановок вершин полного графа, подсчитать для каждой перестановки длину маршрута и выбрать из них кратчайший.
Очевидно, такое вычисление потребует О(р!) шагов. Как известно, р! с ростом р растет быстрее, чем любой полипом от р, и даже быстрее, чем 2э (см. раздел 5.2). Таким образом, решение 'задачи коммивояжера описанным методом полного перебора оказывается практически неосуществимым даже для сравнительно небольших р. Более того, известно, что задача коммивояжера принадлежит к числу так называемых АР-полиъи задач, подробное обсуждение которых выходит за рамки этого учебника. Вкратце суть проблемы ХР-полноты сводитсн следующему. В различных областях дискретной математики, комбинаторики, логики и т.
п. известно множество задач, принадлежащих к числу наиболее фундаментальных, для которых, несмотря на все усилия, не удалось найти алгоритмов решения, имеющих полиномиальную трудоемкость. Более того, если бы удалось отыскать эффективный алгоритм решения хотя бы одной из этих задач, то из этого немедленно следовало бы существование эффективных алгоритмов для всех остальных задач данного класса. На этом основано общепринятое мнение, что таких алгоритмов не существует. ОТСТУПЛЕНИЕ Полезно сопоставить задачи отыскания эйлеровых и гамильтоновых циклов, рассмотренные в этом и предыдущем разделах.
Внешне формулировки этих задач очень похожи, однако опи оказываются принципиально различнымн с точки зрения практического применении. Уже давно Эйлером получено просто проверяемое необходимое и достаточное условие существования в графе эйлерова цикла. Что касается гамильтоновых графов, то для них не известно необходимых и достаточных условий. На основе необходимого и досточного условия существования эйлерова цикла можно построить эффективные алгоритмы отыскания такого цикла. В то же время задача проверки существования гамильтонова 268 Глава 10. Циклы цикла оказывается )ЧР-полной (также как и задача коммивояжера). Далее, известно, что почти нет эйлеровых графов, и эффективный алгоритм отыскания эйлеровых циклов редко оказывается применимым на практике. С другой стороны, можно показать, что почти все графы гамильтоиовы, то есть !!ш — = 1, !Н(р)! — (с(р)! где Н(р) — множество гамильтоновых графов с р вершинами, а С(р) — множество всех графов с р вершинами.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
