Обходы графов

Лекция 12 § 3.5. Обходы графов Эйлеров цикл. Эйлеров граф. Эйлерова цепь. Гамильтонов цикл. Гамильтонов граф. Гамильтонова цепь. Базовые понятия и утверждения 1. Эйлеров цикл и эйлерова цепь. В 1736 г. Леонард Эйлер опубликовал решение широко известной в то время задачи о кенигсбергских мостах. Задача эта состояла в следующем. На реке Прегель в Кенигсберге было два острова, соединенных между собой и с берегами семью мостами, как показано на рис. 3.62. Спрашивалось, можно ли, начиная с некоторого места суши, обойти все мосты по одному разу и вернуться назад? Эмпирические попытки найти такой обход оканчиваются неудачей. Вклад Эйлера в решение задачи состоит в теоретическом обосновании невозможности такого обхода. Для доказательства того, что задача не имеет решения, Эйлер обозначил каждую часть суши точкой, а каждый мост - линией, соединяющей соответствующие точки. Получился рисунок, который мы называем диаграммой графа (рис. 3.63). Рис. 3.62. Рис. 3.63. Используя современную терминологию, можно сказать, что Эйлер свел задачу об обходе мостов к поиску на данном графе цикла, содержащего все вершины и все ребра графа. Отправляясь от этого частного случая, Эйлер обобщил постановку задачи и доказал, что критерием существования такого рода цикла на произвольном связном графе является четность степеней всех его вершин. Цикл на графе, содержащий все вершины и все ребра графа, стали называть эйлеровым циклом, а граф, на котором имеется эйлеровый цикл, - эйлеровым графом. Цепь на графе (как замкнутая, так и незамкнутая), содержащая все вершины и все ребра графа, называют эйлеровой цепью (замкнутая эйлерова цепь есть не что иное, как эйлеров цикл). Пример 1. Граф на рис. 3.64 - эйлеров, поскольку содержит эйлеров цикл . Пример 2. Граф на рис. 3.65 содержит эйлерову цепь . Пример 3. Граф на рис. 3.66, очевидно не содержит ни одну эйлерову цепь и, в частности, не содержит ни одного эйлерова цикла. Рис. 3.64. Рис. 3.65. Рис. 3.66. Следующие два утверждения являются критериями существования эйлерова цикла и эйлеровой цепи на связном графе: 1) связный граф содержит эйлеров цикл тогда и только тогда, когда каждая его вершина имеет четную степень; 2) связный граф содержит эйлерову цепь тогда и только тогда, когда он имеет не более двух вершин нечетной степени. Доказательство этих утверждений приведены во второй части параграфа. Опишем алгоритм построения эйлерова цикла на графе. Пусть - связный граф, все вершины которого имеют четную степень. 1-й шаг. Произвольно выбираем некоторую вершину и инцидентное ей ребро. Этому ребру присваиваем номер 1. Переходим по этому ребру в вершину , после чего ребро удаляем. -й шаг. Пусть к началу этого шага мы находимся в вершине . Выбираем инцидентное этой вершине ребро, соблюдая следующие правила: 1) находясь в вершине , не следует выбирать ребро, соединяющее с , если имеется возможность иного выбора; 2) находясь в вершине , не следует выбирать ребро, которое является перешейком, т.е. таким ребром, при удалении которого граф, образованный оставшимися ребрами, распадается на ненулевые компоненты связности. Выбранному ребру присваиваем номер , проходим по нему из вершины в смежную с ней вершину , после чего ребро с номером удаляем. Если после этого все ребра в графе оказались удаленными, то эйлеров цикл построен (порядок нумерации ребер соответствует последовательности их обхода в графе ). В противном случае удаляем ребро с номером , увеличиваем на единицу и повторяем -й шаг. Пример 4. На рис. 3.67 изображен связный граф, степени всех вершин которого четны. Ниже приводится эйлеров цикл, построенный изложенным выше алгоритмом: Пример 5. На рис. 3.68 изображен связный граф, у которого ровно две вершины и имеют нечетную степень (ребро графу не принадлежит). Соединим вершины и , имеющие нечетную степень, ребром и построим на полученном графе эйлеров цикл, начав его с этого ребра: . Рис. 3.67. Рис. 3.68. Удалив из построенного эйлерова цикла первую вершину и ребро (), получим на исходном графе эйлерову цепь: . 2. Гамильтонов цикл и гамильтонова цепь. Гамильтоновой цепью графа называется такая его простая цепь, которая проходит через каждую вершину ровно один раз. Замкнутая гамильтонова цепь называется гамильтоновым циклом. Граф называется гамильтоновым, если он обладает гамильтоновым циклом. Гамильтонов цикл не обязан проходить по всем ребрам графа. Простого и эффективного критерия существования гамильтонова цикла на графе не найдено. Однако известно несколько необходимых и достаточных условий существования гамильтоновых циклов [4]. Теоретические обоснования Теорема 3.8 (об эйлеровых циклах). Для неодноэлементного связного графа следующие условия эквивалентны: 1) - эйлеров граф; 2) каждая вершина графа имеет четную степень; 3) множество всех ребер графа можно разбить на циклы. Доказательство. Доказательство проведем по схеме: . . Пусть - эйлеров цикл на графе и - произвольная вершина графа. Поскольку цикл - эйлеров, то вершина встречается в цикле по меньшей мере один раз. Двигаясь по циклу , будем подсчитывать число ребер, идущих в цикле перед ней и после нее. Это число равно степени вершины , поскольку цикл содержит каждое ребро графа, причем в единственном числе. В общем случае вершина может совпадать как с внутренними, так и с концевыми вершинами цикла . Прохождение каждой совпадающей с внутренней вершины цикла вносит вклад, равный 2, в степень этой вершины. Если вершина совпадает с началом и концом цикла, то первое и последнее ребра цикла совместно вносят в ее степень вклад 2. Следовательно, степени всех вершин графа - четные. . Докажем, что если каждая вершина связного графа имеет четную степень, то множество всех ребер графа можно разбить на циклы. Доказательство проведем индукцией по числу ребер графа. Базис индукции. Пусть , т.е. граф имеет одно ребро (обозначим его ). Концы этого ребра имеют четную степень, только если это ребро - петля и совпадающие концы этого ребра - единственная вершина графа (обозначим ее ). Следовательно, цикл - искомое разбиение. Индуктивный переход. Предположим, что утверждение верно для любого связного графа с числом ребер, меньшим либо равным . Покажем, что оно остается в силе для графа , число ребер которого равно . Граф - не дерево (в противном случае у него было бы не менее двух висячих вершин, а это противоречит условию о четности степеней всех вершин графа). Следовательно, на графе имеется цикл; обозначим его . Если цикл проходит через все ребра графа , то множество его ребер есть искомое разбиение, и индуктивный переход доказан. В противном случае рассмотрим граф , полученный из удалением ребер цикла . Каждая компонента связности графа - либо изолированная вершина, либо связный ненулевой граф с вершинами четных степеней и числом ребер, меньшим либо равным . Значит, по предположению индукции на каждой ненулевой компоненте связности множество всех ребер можно разбить на циклы. Множества ребер этих циклов в совокупности с множеством ребер цикла дадут разбиение на циклы множества ребер исходного графа . . Разобьем множество всех ребер графа на наименьшее число циклов (такое разбиение существует в силу условия 3 и конечности множества ребер графа ) и докажем, что . Будем рассуждать от противного: предположим, что . В силу связности графа найдется такое , что циклы и имеют общую вершину. Поскольку и не имеют общих ребер, их можно объединить в один цикл, уменьшив таким образом общее число циклов. Получили противоречие с тем, что исходное разбиение наименьшее по числу циклов. Следовательно, все ребра графа принадлежат некоторому циклу, т.е. граф является эйлеровым. ■ Теорема 3.9 (об эйлеровых цепях). Связный граф содержит эйлерову цепь тогда и только тогда, когда он имеет не более двух вершин нечетной степени. Доказательство. Необходимость. Пусть на связном графе есть эйлерова цепь . Возможны два случая: а) цепь замкнута и б) цепь не замкнута. Рассмотрим их. а) Пусть цепь замкнута, тогда по теореме об эйлеровых циклах степени всех вершин графа четны и, следовательно, верно, что граф содержит не более двух вершин нечетной степени. б) Пусть цепь не замкнута и вершина - ее начало, вершина - конец. Добавим к графу новое ребро . Склеив с ребром , получим на связном неодноэлементном графе эйлеров цикл. Следовательно, граф - эйлеров и степени всех его вершин четны. Удаление из графа ребра уменьшает на единицу степени вершин и (они становятся нечетными) и не меняет степени остальных вершин. Значит, на графе две вершины ( и ) имеют нечетные степени, а остальные - четные. Достаточность. Пусть связный граф содержит не более двух вершин нечетной степени. Возможны два случая: а) число вершин нечетной степени графа равно нулю; б) число вершин нечетной степени графа равно двум. Рассмотрим их. а) Если на графе нет вершин нечетной степени, то граф - эйлеров, а значит, на нем есть эйлеров цикл, который и является эйлеровой цепью. б) Пусть граф имеет ровно две вершины нечетной степени и . Рассмотрим граф , полученный из добавлением нового ребра . Граф связен, неодноэлементен и степень каждой его вершины - четное число. Поэтому в существует эйлеров цикл . Удалив из ребро , получим на графе эйлерову цепь . ■ Задачи повышенной сложности 3.30. Можно ли прогуляться по парку и его окрестностям (план парка изображен на рис. 3.67) так, чтобы при этом перелезть через каждый его забор ровно один раз? 3.31. Есть ли гамильтонов цикл на графе ? Ответ обосновать. § 3.6. Раскраска графов Раскраска графа. -раскрашиваемый граф. -хроматический граф. Хроматическое число графа. Базовые понятия и утверждения Пусть - произвольный граф и - некоторое множество, элементы которого будем называть красками. Определение. Раскраской графа в цветов называется отображение такое, что для любых двух смежных вершин и выполняется условие . Если раскраска графа задана, то говорят, что вершина имеет цвет . Отметим, что здесь не предполагается, что отображает на все множество красок (т.е. какие-то краски могут оказаться неиспользованными). Граф называется -раскрашиваемым, если он может быть раскрашен в цветов. Если при этом его нельзя раскрасить в цвет, то он называется -хроматическим. Число в таком случае называют хроматическим числом графа и обозначают . Пример 1. Рассмотрим граф, изображенный на рис. 3.71. Поскольку в графе есть смежные вершины, то раскрасить его в один цвет нельзя. На рис. 3.71 дан пример раскраски графа в два цвета: вершины и красим в красный цвет, а вершины и - в оранжевый. Таким образом, для данного графа хроматическое число . Приведем ряд утверждений о хроматических числах графов: 1) 1-хроматические графы - это нулевые графы и только они; 2) 2-хроматические графы - это ненулевые двудольные графы и только они (заметим, что 2-хроматические графы также называют бихроматическими); 3) ненулевой обыкновенный граф является бихроматическим тогда и только тогда, когда не содержит циклов нечетной длины; 4) любой планарный граф можно раскрасить не более чем в четыре цвета. Заметим, что из утверждения 2 следует, что любое неодноэлементное дерево является бихроматическим графом. Упражнение 3.30. Построить обыкновенный плоский граф с минимальным числом вершин, хроматическое число которого равно 4. Упражнение 3.31. Для следующих графов найти хроматические числа и привести пример раскраски графов в соответствующее число цветов: а) ; б) ; в) ; г) ; д) граф Петерсена (см. рис. 3.55). Теоретические обоснования Теорема 3.10 (критерий бихроматичности). Пусть - ненулевой обыкновенный граф. Тогда следующие условия эквивалентны: 1. граф бихроматический; 2. граф не имеет циклов нечетной длины; 3. граф - двудольный. Доказательство. Доказательство проведем по следующей схеме: . . Будем рассуждать от противного. Предположим, что граф бихроматический и на нем имеется цикл нечетной длины: . Зафиксируем некоторую раскраску графа в два цвета. Так как концы каждого ребра графа имеют разный цвет, то вершины цикла , совпадающие с членами последовательности с нечетными номерами, окрашены в один цвет. Следовательно, вершины и , а значит и окрашены одинаково, что невозможно, поскольку эти вершины смежные. Пришли к противоречию, следовательно, наше предположение было неверным. . Вначале докажем справедливость этого утверждения для связного графа. Пусть - ненулевой обыкновенный связный граф, не имеющий циклов нечетной длины. Зафиксируем некоторую вершину графа и разобьем множество вершин графа на два непересекающихся подмножества и : в множество соберем все вершины , для которых длина любой кратчайшей цепи, идущей из в четна, а в - вершины, для которых эта длина нечетна. Вершину поместим в . Для удобства подмножества и будем далее называть долями. Покажем, что концы любого ребра графа лежат в разных долях. Будем рассуждать от противного: предположим, найдется ребро , концы и которого лежат одновременно в или в . Тогда , (поскольку вершины, смежные с , лежат с ней в разных долях). Пусть - кратчайшая цепь, идущая из в , - кратчайшая цепь, идущая из в , и - последняя вершина цепи , принадлежащая цепи : , . Вершины и лежат в одной доле, следовательно, длины цепей и имеют одинаковую четность. А поскольку цепи и - кратчайшие, то их фрагменты и имеют одинаковую длину. Делаем вывод: длины фрагментов и имеют одинаковую четность. Заметим, что по фрагменты и цепей и не имеют одинаковых ребер. Кроме того, они не содержат ребра (ребро не может быть внутренним ребром ни одной из этих цепей, так как в этом случае цепи и не могут быть кратчайшими; ребро не может быть последним ребром ни одной из цепей, так как в этом случае длины цепей отличаются на единицу и, значит, не могут иметь одну четность). Поэтому, склеивая инвертированный фрагмент , фрагмент и цепь , получаем цикл нечетной длины, что противоречит условию. Таким образом, мы разбили множество вершин графа на два непустых, непересекающихся подмножества (доли) так, что концы любого ребра принадлежат разным долям. Следовательно, граф - двудольный. Пусть теперь граф - ненулевой обыкновенный несвязный граф, не имеющий циклов нечетной длины. Так как граф ненулевой, то среди его компонент связности есть неодноэлементные, причем, как показано выше, каждая неодноэлементная компонента - двудольный граф. Разобьем множество вершин графа на два подмножества. В одно подмножество включим вершины одной из долей каждой двудольной компоненты связности, в другое - все остальные вершины графа (включая вершины одноэлементных компонент связности). Тем самым множество вершин графа окажется разбитым на два непустых, непересекающихся подмножества (доли) так, что концы любого ребра принадлежат разным долям. Следовательно, граф - двудольный. . Пусть - ненулевой двудольный граф. Покрасим вершины одной доли одним цветом, а вершины другой - другим. Получим раскраску графа в два цвета. Поскольку граф ненулевой, т.е. имеет хотя бы одно ребро, то он не может быть раскрашен в один цвет. Таким образом, граф бихроматический. ■ § 3.7. Фундаментальная система циклов графа Абстрактный цикл. Обобщенный цикл. Пространство циклов. Фундаментальная система циклов (базис пространства циклов). Базовые понятия и утверждения Пусть - произвольный граф. На множестве циклов графа введем бинарное отношение, которое назовем отношением равенства и определим следующим условием: будем считать, что два цикла равны, если множества их ребер совпадают. Это бинарное отношение, будучи отношением эквивалентности, разбивает множество циклов данного графа на классы эквивалентности. Далее в этом параграфе, говоря о циклах графа, будем иметь в виду, если не оговорено противное, классы эквивалентности, а не отдельных их представителей. Эти классы эквивалентности назовем абстрактными циклами. Любой абстрактный цикл задается множеством своих ребер. Пример 1. Граф , представленный диаграммой на рис. 3.72, имеет следующие абстрактные циклы: , , , , , . Обобщенным циклом будем называть абстрактный цикл или объединение непересекающихся абстрактных циклов. В число обобщенных циклов включим также цикл без ребер; назовем его пустым циклом и обозначим символом . На множестве всех обобщенных циклов графа введем две операции: а) операцию сложения по модулю 2: суммой обобщенных циклов и назовем обобщенный цикл с множеством ребер (здесь и - множества ребер обобщенных циклов и соответственно); б) операцию умножения на 0 и 1: ; . Например, для обобщенных циклов графа из примера 1 имеем: , , . Множество всех обобщенных циклов графа с операциями сложения по модулю 2 и умножения на 0 и 1 образуют линейное пространство (убедиться в выполнении восьми аксиом линейного пространства несложно). Операция естественным образом распространяется на любое конечное число обобщенных циклов. Линейной комбинацией обобщенных циклов назовем выражение , где . Говорят, что система обобщенных циклов зависима, если найдется набор чисел , не все из которых равны 0, такой, что . В противном случае систему обобщенных циклов называют независимой. Система обобщенных циклов графа образует базис линейного пространства циклов, если она удовлетворяет двум условиям: 1) линейно независима; 2) любой обобщенный цикл графа может быть представлен в виде линейной комбинации обобщенных циклов . Базис линейного пространства циклов называют фундаментальной системой циклов. Из курса линейной алгебры нам известно, что в линейном пространстве может быть несколько базисов, но все они состоят из одного числа векторов линейного пространства (напомним, что это число называют размерностью линейного пространства). Представляют интерес два вопроса: 1) из скольких циклов состоит фундаментальная система циклов произвольного графа и 2) как найти фундаментальную систему циклов графа? Ответ на первый вопрос дает следующее утверждение: число циклов в любой фундаментальной системе циклов графа равно его цикломатическому числу. Приведем алгоритм построения фундаментальной системы циклов произвольного графа . 1-й шаг. Находим в графе какой-либо обобщенный цикл и удаляем из него ребро («разрываем» цикл). Получаем граф . -й шаг. В графе , построенном на ()-м шаге, находим какой-либо обобщенный цикл и удаляем из него произвольное ребро . Получаем граф . Если в графе циклов нет, то - искомая фундаментальная система циклов. Если в графе обобщенные циклы остались, то повторяем -й шаг. Пример 2. Построим фундаментальную систему циклов графа из примера 1. 1-й шаг. Возьмем цикл и удалим из него одно ребро, пусть это будет ребро . Получим граф (рис. 3.73). 2-й шаг. В графе возьмем цикл и удалим из него одно ребро, пусть это будет ребро . Получим граф (см. рис. 3.73). 3-й шаг. В графе возьмем цикл и удалим из него одно ребро, пусть это будет ребро . Получим граф (рис. 3.73), в котором нет циклов. Рис. 3.73. Следовательно, - фундаментальная система циклов (или, что то же самое, базис пространства циклов) графа . Все остальные обобщенные циклы графа - линейные комбинации базисных циклов. Например, . Заметим, что действия по алгоритму не строго детерминированы: на каждом шаге мы имели несколько вариантов выбираемого цикла и удаляемого из него ребра. Если бы наш выбор был иным, то мы нашли бы другую фундаментальную систему циклов. Однако число циклов в этой другой фундаментальной системе тоже было бы равно трем. Например, также является фундаментальной системой циклов графа .