В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич - Лекции по теории графов (1083735), страница 35
Текст из файла (страница 35)
192 Д о с т а т о ч н о с т ь. Предположим теперь, что степени вершин графа С четны. Начнем цепь Р, из произвольной вершины щ и будем продолжать ее, насколько возможно, выбирая каждый раз новое ребро. Так как степени всех вершин четпы, то попав в очередну|о отличную от щ вершину, мы всегда будем иметь в распоряжении еще не пройденное ребро. Поэтому цепь Р1 можно продоляеить путем добавления этого ребра. Таким образом, построение цепи Р1 закончится в веригине гп т. е. Р1 непременно будет циклом. Если окажется, что Р~ содержит все ребра графа С, то это будет требуемый эйлеров цикл. В противном случае, удалив из С все ребра цикла Рь рассмотрим граф Сп полученный в результате такой операции.
Поскольку Р1 и С имели вершины только четных степеней, то, очевидно, н С~ будет обладать тем же свойством. Кроме того, в силу связности графа 6 графы Р1 и С1 должны иметь хотя бы одну общую вершину вг. Теперь, начиная с вершины вг, построим цикл Рг в графе С1 подобно тому, как строили цикл Рь Обозначим через Р, и Р, части цикла Р, от щ до вг и от вг до щ соответственно. Получим новый цикл е Рз — — Р,ОРе0Рге который, начиная с вп проходит но ребрам цепи Р, до им затем обходит все ребра цикла Рг и, наконец, возвращается в щ по ребрам цепи Рг (рис. 43.5). Если цикл Рг не эйлеров, то проделав аналогичные построения, получим еще большой цикл и т.
д. Этот процесс закончится построением эйлерова цикла. 0 Будем говорить, что набор ребер- по непересекающихся цепей (не обязательно простых) покрывает граф С, "2 если каждое ребро графа 6 входит в одну из этих цепей. Пусть связный граф С содержит Й вергпин нечетной Р,е степени. По лемме о рукопожатиях й четко. Рассмотрим граф С, полученный добавлением к С новон вершины в и ребер, соединяющих в с вершинами графа 6 нечетной степени. Поскольку степени всох вершин графа С четны, то С' содержит эйлеров цикл. Гслп теперь выбросить в из этого цикла, то получится й!2 цепей, содержащих все ребра графа С, т.
е. покрывающих С. 13 в, л, виеличее и лв. 193 С другой стороны, граф, являющийся объединением т реберно-непересекающихся цепей, имеет самое большое 2т вершин нечетной степени, 1!оэтому меньшим числом цепей граф 6 покрыть нельзя. Тем самым доказано Следствие 43.2. Если связный граф содержит ровно Й вершин нечетной степени, то минимальное число покрывающих его реберно-непересекающихся цепей равно й!2. В частности, когда й = 2, граф имеет цепь, которая соединяет вершины нечетной степени и содержит все ребра графа. Цепь, содержащую все ребра графа, называют зйлеровой.
Из доказательства теоремы 43.1 видно, что эйлеров граф содержит, как правило, несколько эйлеровых циклов. Зная одпн такой цикл, получить новый можно следующим простым приемом. Пусть С вЂ” исходный эйлеров цикл, и вершина о проходится в эгон цикле более одного раза. Рассмотрим часть (подцнкл) цикла С, состоящую из ребер и вершин, проходимых между й-м и йм (Й(() посещениями вершипы о.
Это будет некоторый цикл Сь Цикл С, кан и всякий эйлеров цикл, задает некоторый порядок обхода ребер графа и индуцирует порядок прохождения ребер цикла Сь Если теперь порядок обхода ребер С~ изменить па обратный, а на остальных ребрах оставить его таким, каким он был в С, то, очевидно, получим новый эйлеров цикл С'. Например, в графе, изображенном на рис. 43.3, можно получить новый цикл С' =(1, 2, 6, 5, 4, 3, 2, 4, 6, 1), полагая С = (1, 2, 3, 4, 5, 6, 2, 4, 6, 1) и С~ = (2, 3, 4, 5, 6, 2).
В этом примере цикл С~ составлен из ребер, проходимых в С между первым и вторым посещениями вершины 2. Итак, изменив указанным способом эйлеров цикл, получаем новый эйлеров цикл. Следующая теорема, приводимая здесь без доказательства, утверждает, что последовательности таких изменений достаточно для получения всех эйлеровых циклов из данного. Теорема 43.3 (Л. Коциг, 1980 г.). Если С и С'— зйлеровы циклы графа 6, то в 6 существует такая последовательность зйлеровых циклов С = Си Сз, ..., С, = =С', что С,.„~ получается из С< путем изменения порядка обхода ребер некоторого подцикла на обратный.
Естественно возникает вопрос: как найти хотя бы одпн эйлеров цикл в эйлеровом графе 6, т. е. как запумеровать ребра графа числами 1, 2, ..., (Е6~ с том, чтобы номер, присвоенный ребру, указывал, каким по счету 194 это ребро проходится в эйлеровом цикле? Оказывается, это можно сделать, если нумеровать ребра, придерживаясь следующих двух правил: 1. Начиная с произвольной вершины и, присваиваем произвольному ребру ио помер 1. Затем вычеркиваем ребро ии и переходим в вершину ш 2. Пусть и> — вершина, в которую мы пришли в результате выполнения предыдущего пгага, и Й вЂ” помер, присвоенный некоторому ребру на атом шаге. Выбираем любое ребро, инцидентное вершине и, причем мост выбираем только в том случае, когда нет других возмон<- ностеи; присваиваем выбранному ребру помер й + 1 и вычеркиваем его.
Зтот процесс, называемый алгоритмом Флери, заканчивается, когда все ребра графа вычеркнуты, т. е. занумерованы. Дадим теперь обоснование алгоритма. Прежде всего заметим, что поскольку степень каждой вершины графа 6 четна, то алгоритм может закончить работу только в той вершине, с которой начал.
Поэтому он строит некоторый цикл С, и надо только доказать, что этот цикт включает все ребра графа 6. Предположим, что это не так, и пусть 6' — связная компонента графа 6 — ЕС, не являющаяся изолированной вершиной. Рассмотрим множество А ребер цикла С, инцидентных вершинам, вошедшим в 6'. Ясно, что А»ь О. Пусть а — ребро из А, получившее в процессе работы алгоритма наибольший номер, т. е. вычеркнутое последним среди ребер А. Тогда, как легко видеть, ребро а к моменту вычеркивания было мостом в графе.
Однако это противоречит правилу выбора очередного ребра. 0 Заметим, что эйлеровы графы достаточно редки, Верна следующая Теорема 43.4 (Р. Рейд, 1962 г.). Почти нет ойлеровыа графов. г Пусть У,(п) — множество всех зйлеровых графов иа У(п) (см. э 12), а Уг(п) — множество всех графов из У(п), степени всех вершин которых четны. Согласно теореме 43А имеем У1(и)шУг(л). Очевидно, что все графы из Уг(п) можно получить, добавляя к некоторому графу из У(п — 1) новую вершину и соединяя ее со всеми вершинами нечетной степени. 13» 1»5 Так как (и-г) (У(п — 1)) ='2 то )У,(п))(2 ' = 2 ' =а(2 ' ) = а()У(п))). (".') (.")--+ ( (")~ 11оэтому на основании (!) имеем )У1(п)! =о(1У(п))), что н доказывает теорему.
«) 3 а м е ч а п и е. Запись )(и) = о(д(п) ) означает, что 1!ш — = О. 1(и) в (и) 9 44. Гамильтоновы графы Граф называется гамильтоиавым, если в нем имеется простой цикл, содержащий каждую вершину этого графа. Сам этот цикл также называется гамильтоповым, Гамильтаповой называют н простую цепь, содержащую каждую вершину графа. Слово «гамильтонов» в этих определениях связано с именем известного ирландского математика У. Гамильтона, которым в 1859 году предложена следующая игра «Кругосветное путешествие».
Каждой из двадцати вершин додекаэдра приписано название одного из крупных городов мира. Требуется, переходя от одного города к другому по ребрам додскаэдра, посетить ка»кдый город в точности один раз и вернуться в исходный город. Рзс. 44.2 Рис. 44Л Эта аадача, очевидно, сводится к отысканию в графе додекаэдра (рис. 44.1) простого цикла, проходящего через кажду|о вершину этого графа.
11е все связные графы гамильтоновы хотя бы потому, что такой граф должен быть двусвязным. Однако пример графа, представленный на рис. 44.2, показывает, что для гамильтоновости графа двусвязности недостаточно. 196 Любой граф, содержащий две вершины степени 3, соединенные тремя простыми попарно непересекающимися цепями длины не менее двух, называется тэта-графом (рис. 44.2). Т е о р е м а 44.1. Ераэхдый пегамильтоиог двусвяэиый граф содержит тэта-подграф. > Пусть С вЂ” вегампльтопов двусвязный граф и С— простой цикл максимальпоп длины в этом графе. По условию теоремы ьпгоягество Ь'= т'С~)тС непусто.
Как подтверждает прямая проверка, среди двусвязных графов порядка меньше пяти нет негамильтоновых, поэтому ~ С ~ > 5. Из двусвязности графа С и теоремы 34.1 следует, что ~)тС! ~ 4. 11усть хо — такое реб- 5 -, ' т э,э' ро графа 6, что хш т'С, о ш Ь', а и Ь вЂ” вершины цикла С, смежные с х г (рис. 44.3) . Носкольку С вЂ” максимальный цикл, то вершина о пе смежна нн с а, ни с Ь (иначе можно было бы построить больший цикл). Рассмотрим теперь граф С вЂ” х, который, очевидно, свяаен.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
