Полная версия

Главная arrow Математика, химия, физика arrow Дискретная математика

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ   >>

Основные понятия и определения

Графом (7 называется любая пара (V, Ц), где К= |У|, у2, ...} — множество элементов любой природы, а ?/= {и,, и2,...} — семейство пар элементов из V, причем допускаются пары вида (у,-, у,) и одинаковые пары.

Если пары в и рассматриваются как неупорядоченные, то граф называется неориентированным; если как упорядоченные, то граф называется ориентированным {орграфом).

Элементы множества V называются вершинами графа, пары из и в неориентированном графе называются ребрами, а в орграфе — ориентированными ребрами или чаще дугами.

Графы можно условно изображать следующим образом. Вершины будем изображать точками, а каждое ребро (дугу) (у,-, у ) — линией, соединяющей точки, соответствующие вершинам у,- и у-. Если (у„ у ) — дуга, то на этой линии будем указывать стрелку от у,- к у-.

Пара вида (у,-, у,) называется петлей в вершине у,-. Если пара (у,-, у-) встречается в [/ более одного раза, то говорят, что (у,-, уу) — кратное ребро.

Говорят, что вершины у, и Vj смежны в графе С = (К, Ц), если в и входит пара (у„ у) или (у, у,). Говорят, что ребро (дуга) (у,-, у-) инцидентно вершинам у,- и у. В этом смысле граф можно задать как совокупность двух множеств: вершин Vи ребер (7, между которыми определено отношение инцидентности. Каждое ребро и из и инцидентно ровно двум вершинам у,, у-, которые оно соединяет. При этом вершина у,- и ребро и называются инцидентными друг другу, а вершины у, и уусмежными. Два различных ребра графа называются смежными, если они имеют по крайней мере одну общую вершину.

Степенью вершины у неориентированного графа (7 называется число ребер, инцидентных у, при этом степень вершины будем обозначать через Ду). Вершина степени 0 называется изолированной. Вершина степени 1 называется висячей, или концевой.

Пусть (7 = (V, Ц) — «-вершинный граф, а^, $2, •••? — степени его

вершин, выписанные в порядке неубывания: ^ < 52 < ... < V Упорядоченную систему ($!, 52, ..., $„) будем называть вектором степеней графа (7 и кратко обозначать я((7).

Одним из самых простых, но в то же время очень важных утверждений в теории графов является следующий факт. Пусть в графе (7 п вершин и т ребер. Пусть 5(у,) — степень вершины у,-. Тогда суммарная степень всех вершин равна удвоенному числу ребер графа. Это объясняется тем, что, когда мы считаем степень одной вершины, считаем все ребра, выходящие из нее. Вычисляя сумму всех степеней, получаем, что каждое ребро считается дважды, так как оно инцидентно двум вершинам (петли по определению степени также посчитаются дважды). Поэтому общая сумма будет равна удвоенному числу ребер. По этой причине суммарная степень всех вершин графа всегда является четным числом.

Иными словами, количество вершин с нечетной степенью в графе всегда четное. Это один из критериев, который помогает иногда доказать невозможность построения некоторых графов.

Ориентированным графом (7 называется пара (К((7), ?/((7)), где К(<7) — непустое конечное множество элементов, называемых вершинами, а ?/((?) конечное множество упорядоченных пар элемен-

тов из К((7), называемых дугами (или ориентированными ребрами). Дуга, у которой вершина является первым элементом, а вершина у2 — вторым, называется дугой из V] в у2: (у1? у2). Заметим, что дуги (У(, у4) и (у4, У() различны (рис. 2.1, а). Иногда при изображении графа пара таких дуг заменяется двунаправленной дугой (рис. 2.1, в), эти представления эквивалентны.

Ориентированный (а), неориентированный (б)

Рис. 2.1. Ориентированный (а), неориентированный (б)

и смешанный (в) графы

Неориентированным графом (7 называется пара (К((7), ^/(С7)), где К((?) — непустое конечное множество элементов, называемых вершинами, а ЩИ) — конечное множество неупорядоченных пар элементов из К((7), называемых ребрами. Будем называть К((7) множеством вершин, а и(Є) — множеством ребер графа (7. О каждом ребре вида (У[, у3) говорят, что оно соединяет вершины У] и у3 (рис. 2.1, б). При изображении графов на рисунках или схемах отрезки, изображающие ребра или дуги, могут быть прямо- или криволинейными, длины этих отрезков и расположение точек (вершин) произвольны.

В литературе и при решении прикладных задач иногда встречаются понятия смешанных, взвешенных и мультиграфов.

Смешанным называется граф, содержащий как ориентированные, так и неориентированные ребра (см. рис. 2.1, в).

Ориентированные мультиграфы (а), псевдографы (б)

Рис. 2.2. Ориентированные мультиграфы (а), псевдографы (б),

мультипсевдографы (в)

Мультиграф — граф, в котором имеется несколько парных ребер или однонаправленных дуг (рис. 2.2, а): их =1? у4), и2 = (у4, уД

Псевдограф — граф, содержащий петли. Петлей в неориентированном (ориентированном) графе называется ребро (дуга) вида (у,-, у,), которое соединяет вершину у, саму с собой (рис. 2.2, б).

Мультипсевдограф — граф, в котором имеются петли и парные ребра (рис. 2.2, в).

Приведем краткое описание некоторых специальных типов графов.

Простым называется граф, который не содержит кратных ребер и не содержит петель. Пустым называется граф, у которого множество ребер пусто. Будем обозначать пустой граф с п вершинами через Рп.

Простой граф называется полным, если каждые две различные вершины его соединены одним и только одним ребром. Полный граф с п вершинами обычно обозначается через Кп. Заметим, что

п -1

”Т~

ребер.

граф Кп имеет ровно п ?

Граф, у которого все п вершин имеют одну и ту же степень, называется регулярным. Если степень каждой вершины равна г, то граф называется регулярным степени г. Заметим, что регулярный граф

степени г на п вершинах имеет ровно п ? — ребер.

Двудольным называется граф (7(Е, (/) такой, что множество вершин Уразбито на два непересекающихся подмножества Г, и У2, причем всякое ребро и инцидентно вершине из Г, и вершине из У2 (т.е. соединяет вершину из Ух с вершиной из У2). Множества У1 и У2 называются долями двудольного графа.

Двудольный граф называется полным, если любые две вершины из У1 и У2 являются смежными. Если У = п[2 = п2, то полный двудольный граф обозначается К . Заметим, что граф К имеет ровно п{ + п2 вершин и Л7| ? п2 ребер.

Способы задания графов

Графический способ задания является самым наглядным и наиболее удобным для человеческого восприятия. Однако для практического использования в прикладных целях, когда с помощью теории графов решаются прикладные задачи с помощью вычислительной техники и специально разработанных алгоритмов, требуется специальное, ориентированное на автоматизированную обработку представление данных.

Один из наиболее распространенных матричных способов задания графов — это матрица смежности 5( Ух V):

s(i, Л

Г1, если 3 ребро или дуга (у/5 уу); [О — в противном случае.

Матрицы смежности однозначно задают как неориентированные (в этом случае матрица симметрична относительно главной диагонали), так и ориентированные графы. Ниже (табл. 2.1) приведена матрица смежности для графа на рис. 2.1, <7.

Таблица 2.1

Матрица смежности для графа на рис. 2.1, а

V

V|

v2

v3

v4

v5

Vl

0

0

1

1

0

0

0

1

0

0

0

0

0

1

0

^4

1

0

0

0

0

v5

0

0

0

0

0

Никаких проблем не возникает и с псевдографами (петле соответствует единица на главной диагонали), тогда как мультиграфы заданы быть не могут. Ниже приведены матрицы смежности для графа на рис. 2.1, б (табл. 2.2) и графа на рис 2.2, б (табл. 2.3).

Также применяется способ задания при помощи функционального представления Г1 и Г-1:

Г1 (у,) = {vj}: 3 дуга (v,-, vy);

Г“‘(у,) = {vy}: 3 дуга (vy, v().

При помощи функционального представления однозначно задаются как неориентированные (в этом случае Г1 = Г-1), так и ориентированные и смешанные графы. Как и в случае с матрицей смежности, для смешанных графов эквивалентно выглядит задание ребра и пары разнонаправленных дуг. Никаких проблем не возникает с псевдографами (если вершина у, имеет петлю, то и в Г^у,), и в Г_1(у,) войдет вершина у,). Мультиграфы заданы быть не могут. В качестве примера зададим граф (см. рис. 2.2, б) при помощи функционального представления:

r'(vi) = {v3,v4}; Г-'(у,) = 0;

r'(v2) = (v3|; Г"'(у2) = 0;

Таблица 2.3

Матрица смежности для графа на рис. 2.2, б

V

VI

у2

V4

V5

VI

0

0

1

1

0

^2

0

0

1

0

0

^3

0

0

1

1

0

^4

0

0

0

0

0

^5

0

0

0

0

0

Г'(і’з) = {V,, у4}; Г ‘(у3) = {V,, у2, у3};

Г‘(у4) = 0; Г-,4) = {у„у3К

Г‘(у5) = 0; Г-‘(у5) = 0.

Графы с большим количеством вершин и относительно небольшим количеством ребер более эффективно можно задать при помощи матрицы инциденцийЛ (IIх V). Матрица инциденций для ориентированных графов:

1, если Vj исток дуги м,-; а(1,Л = <{ -1, если Vj сток дуги и, ;

О, если Vj не инцидентна дуге щ.

Матрица инциденций для неориентированных графов:

а(і, Л

Матрица смежности для графа на рис. 2.1, б

V

у1

у2

^4

^5

VI

0

0

1

1

0

^2

0

0

1

0

0

^3

1

1

0

1

0

^4

1

0

1

0

0

^5

0

0

0

0

0

{1, если Уу инцидентна ребру «(;

О, если Vj не инцидентна ребру щ.

Матрицы инциденций однозначно задают как неориентированные, так и ориентированные графы. В принципе нет никаких препятствий для задания смешанных графов — в отличие от матрицы

смежности в этом случае задание ребра и пары разнонаправленных дуг будет отличаться. Никаких проблем не возникает с мультиграфами (и в ориентированном, и в неориентированном случае), а также с неориентированными псевдографами. Неоднозначность возникает при задании ориентированных псевдографов: на пересечении строки, помеченной петлей, и столбца, помеченного вершиной, на которой эта петли присутствует, по правилу должны одновременно находиться как 1 так и -1. Из этой ситуации имеется выход: вместо одной матрицы А (II х V) граф задается двумя матрицами — истоков А+ (?Ух V) и стоков А~ (їїх V):

а+(і,Л

а~(і,Л

П, если уу исток дуги и,; [О —иначе.

[1, если VI сток дуги и{ [О — иначе.

Ниже приведены матрицы инциденций для графа на рис. 2.1, а (табл. 2.4) и графа на рис. 2.2, б (табл. 2.5).

Таблица 2.4

Матрица инциденций для графа на рис. 2.1, а

V

^1

у2

у3

^4

^5

«23

0

1

-1

0

0

«із

1

0

-1

0

0

и 14

1

0

0

-1

0

«41

-1

0

0

1

0

«34

0

0

1

-1

0

Таблица 2.5

Матрица инциденций для графа на рис. 2.2, б

V

VI

у2

V4

V5

«13

1

0

1

0

0

«23

0

1

1

0

0

«33

0

0

1

0

0

«41

1

0

0

1

0

«34

0

0

1

1

0

Задача 2.1. Дан неориентированный граф, заданный своим функциональным представлением:

го^) = {у1? у2, у3, У4, ^5}; Г(у2) = {у,, у3};

Г(у3) = {уь у2, у3, у5}; Г(у4) = {уь у5};

г(у5) = {у!, у3, у4}; г(у6) = 0.

Задать этот граф тремя другими способами:

  • а) графически;
  • б) с помощью матрицы инциденций;
  • в) с помощью матрицы смежности.

Решение.

Подобные задачи на построение графа необходимо начинать с определения всех вершин, входящих в множество V. Для функционального представления множество вершин графа совпадает с областью определения функции Г. В нашем случае получаем, что V- 1? у2, у3, у4, у5, у6}. Также необходимо заметить, что множество V может и не совпадать с объединением множеств Г(у,). Это очень хорошо видно в данном примере: вершина у6 не входит ни в одно из множеств, порождаемых функцией Г.

а) Задание графа графическим способом.

Графический способ изображения графов является самым наглядным и наиболее удобным для человеческого восприятия, потому и решение любой задачи в теории графов лучше всего начинать с построения графического представления.

Сначала изобразим в виде кружков с написанным названием внутри все вершины, входящие в множество V. Они могут находиться совершенно в произвольных местах и не обязаны каким-либо образом быть упорядочены.

Выберем вершину У[ и с помощью линий соединим ее со всеми вершинами, входящими в множество Г(у,), т.е. с вершинами у,, у2, у3, у4, у5. Сама же вершина у( соединяется сама с собой с помощью петли. Далее рассмотрим вершину у2, она смежна с вершинам и у3, но ребро 1? у2) уже построено, а в случае неориентированного графа, значит, и ребро 2, У|) тоже построено. Таким образом, необходимо построить ребро только между вершинами у2 и у3. Повторив этот шаг для оставшихся вершин множества V, получим требуемое графическое задание графа. Результат построения приведен на рис. 2.3.

б) Построение матрицы инциденций.

Для построения матрицы инциденций необходимо определиться с нумерацией ребер в исходном графе. Поэтому каждому ребру графа в его графическом представлении припишем название, например так, как показано на рис. 2.3.

Графическое представление для задачи 2.1

Рис. 2.3. Графическое представление для задачи 2.1

Далее необходимо построить матрицу размерности 9x6, перечислив ребра иі в первом столбце, а вершины V,- — в первой строке. Рассмотрим заполнение строки, соответствующей ребру их. Как видно из рис. 2.3, ребро их инцидентно вершинам у2 и у3, а значит, в соответствующих им ячейках строки и! ставим единицы. Повторяем тот же алгоритм для ребер и2, и3, иА, и5 и и6

В случае же ребер и1 и г/8 единица оказывается только в ячейке, соответствующей вершине, с которой данное ребро непосредственно соединено (таким образом, для петель в строке матрицы инциденций стоит одна единица). Получившаяся в результате матрица инциденций представлена в табл. 2.6.

Таблица 2.6

Матрица инциденций для графа из задачи 2.1

V

^1

у2

^3

^4

^5

^6

«1

0

1

1

0

0

0

и2

0

0

1

0

1

0

“з

0

0

0

1

1

0

и4

1

0

0

0

1

0

«5

1

0

0

1

0

0

«6

1

1

0

0

0

0

и7

1

0

0

0

0

0

«8

0

0

1

0

0

0

в) Построение матрицы смежности.

Построение матрицы смежности легче производить по графическому заданию графа. Для этого сначала необходимо построить матрицу размерности 6 х 6, по вертикали и горизонтали пере-числив вершины у,. Рассмотрим построение строки, соответствующей вершине у,-. Данная вершина смежна вершинам у2, у3, у4, и у5, а значит, в соответствующих им ячейках матрицы проставляем единицы. То же повторяем для вершин у2, у3, у4 и у5. Вершина у6 не связана ребром ни с одной другой вершиной графа, а потому матрица смежности содержит соответствующую ей нулевую строку и нулевой столбец. Полученная матрица смежности представлена в табл. 2.7.

Таблица 2.7

Матрица смежности для графа из задачи 2.1

V

у2

У3

У4

^5

^6

1

1

1

1

1

0

^2

1

0

1

0

0

0

^3

1

1

1

0

1

0

^4

1

0

0

0

1

0

^5

1

0

1

1

0

0

^6

0

0

0

0

0

0

Как и следовало ожидать, матрица смежности для неориентированного графа оказалась симметричной.

При решении этой задачи при построении графического представления у разных обучающихся могут получиться отличающиеся друг от друга изображения одного и того же графа. Это связано с важнейшим понятием теории графов, называемым изоморфизмом. Изоморфными называются графы, которые имеют одинаковое число вершин и одинаковое число ребер, причем для вершин графов можно ввести одинаковые обозначения таким образом, что неупорядоченные пары вершин, обозначающие ребра, у изоморфных графов будут одинаковы.

Дадим более строгое определение. Граф (7 называется изоморфным графу Я, если существует биекция / из множества вершин графа (7 в множество вершин графа Я, обладающая следующим свойством: если в графе (7 есть ребро из вершины у, в вершину Уу, то в графе Я должно быть ребро из вершины /(у,-) в вершину /(у), и наоборот — если в графе Я есть ребро из вершины у, в вершину у-, то в графе (7 должно быть ребро из вершины/'(у,) в вершину/_|(у). В случае ориентированного графа эта биекция также должна сохранять ориентацию ребра. В случае взвешенного графа биекция также должна сохранять вес ребра.

Можно показать, что отношение изоморфизма между графами является отношением эквивалентности. Следовательно, оно разбивает класс всех графов на непустые и попарно не пересекающиеся подклассы, называемые классами изоморфизма (классами изоморфных графов, называемых также абстрактными графами). Два произвольных графа принадлежат одному и тому же классу изоморфизма тогда и только тогда, когда они изоморфны друг другу.

Ясно, что необходимым условием изоморфизма является совпадение количества вершин и количества ребер.

Изоморфные графы естественно отождествлять, т.е. считать совпадающими. Они могли бы различаться конкретной природой своих элементов, но именно это игнорируется при введении понятия «граф». Математическая теория графов интересуется такими свойствами графов, которые инвариантны относительно изоморфизма. В предыдущих параграфах были рассмотрены три самых простых инварианта: количество вершин «(С), количество ребер т((7) и вектор степеней Д(7) = (5,, б21 ..., 5Я). В дальнейших параграфах мы рассмотрим еще несколько инвариантов.

Не будучи идеальным средством распознавания изоморфизма, вектор степеней может, тем не менее, во многих случаях оказать существенную помощь. Во-первых, если ДО?) Ф ДбД, то отсюда сразу следует неизоморфность графов (7 и С. Во-вторых, если Д(7) = ДбД, то для проверки графов (/ и С' на изоморфизм требуется перебор не всех п соответствий между вершинами, а лишь тех, при которых сопоставляются вершины одинаковой степени.

Однако имеются случаи, когда при выяснении изоморфизма графов их векторы степеней практически бесполезны: речь идет о регулярных (однородных) графах, в которых степень всех вершин одна и та же. Пример изоморфизма приведен на рис. 2.4. Читатель может попробовать найти искомое отображение вершин этих двух графов.

Вопрос о том, изоморфны ли два данных графа, в общем случае оказывается сложным. Для изоморфизма двух «-вершинных графов само определение этого отношения дает теоретически безукоризненный способ проверки: надо просмотреть все п взаимно однозначных соответствий между множествами вершин и установить, совмещаются ли полностью ребра графа хотя бы при одном соответствии. Однако даже весьма грубая оценка показывает, что такое решение задачи «в лоб» практически непригодно в силу слишком большого объема вычислений уже при п больше 20. Подобная ситуация, естественно, толкнула многих математиков на классический путь: попытаться найти такой инвариант (число или систему чисел), кото-

Изоморфные графы

Рис. 2.4. Изоморфные графы

рый бы, с одной стороны, легко вычислялся по заданному графу (и по возможности имел наглядный смысл), а с другой — обладал свойством полноты, т.е. определял граф однозначно с точностью до изоморфизма.

Операции над графами

Над графами, как и над другими математическими объектами (множествами, отношениями, числами), можно производить ряд операций. Рассмотрим основные из них.

Удаление вершины. Пусть б = (V, б) — граф и у є V. Удалить вершину V из графа б значит построить новый граф б7 = (V', б7), в котором V' = У {г} и и' получается из будалением всех ребер, инцидентных вершине х. На рис. 2.5, а, 6 приведен пример удаления вершины у из графа.

Удаление ребра. Пусть б = (V, б) — граф и и є и. Удалить ребро и — значит построить новый граф б7 = (Г7, б7), в котором V' = V и и' = и {и}. На рис. 2.5, в, г дан пример удаления ребра графа.

Граф б] = (Г1? б,) называется подграфом графа б= (V, б), если Г, является подмножеством Гиб, является подмножеством б.

Дополнением графа б называется граф б с теми же вершинами, что и граф б, и с теми и только теми ребрами, которые необходимо добавить к графу б, чтобы получился полный граф (рис. 2.6).

Например, дополнением полного графа на п вершинах будет пустой граф на п вершинах, и наоборот.

Особую внимательность необходимо проявлять при построении дополнения двудольных графов. В этом случае добавлять следует не только те ребра, которые нужны исходному графу б, чтобы стать полным двудольным графом, но еще и те ребра, которые соединяют

Операция удаления вершины V

Рис. 2.5. Операция удаления вершины V: до удаления (а); после удаления (б); операция удаления ребра и: до удаления (в) после удаления (г)

Операция дополнения для графа

Рис. 2.6. Операция дополнения для графа <7

вершины в своих долях, т.е. дополняют исходный граф до полного вообще (рис. 2.7).

Например, если исходный граф является полным двудольным графом К45, то его дополнение будет представлять собой несвязный граф, состоящий из двух отдельных фрагментов, являющихся К4 и К5 (рис. 2.8).

Объединение графов. Пусть даны два графа б] = (К(б,), (7(6,)), б2 = (К(б2), б(б2)), причем множества К(б|), К(б2) не пересекаются. Пусть | ^(6,)! = «!,! Г(б2)| = п2, |б(б| )| = т 1, |б(б2)| = т2. Объединением б = и б2 графов б,, б2 называется граф с множеством вершин У(Сг{) и К(б2) и семейством ребер б(б|) и б(б2).

При графической интерпретации операции объединения объединяемые графы просто изображаются рядом, и у полученного в итоге

б

Операция дополнения для двудольных графов

Рис. 2.7. Операция дополнения для двудольных графов

Операция дополнения для полных двудольных графов

Рис. 2.8. Операция дополнения для полных двудольных графов

графа количество вершин равно сумме вершин исходных графов, а количество ребер — сумме ребер исходных графов (рис. 2.9).

я = /7]+я2 = 4 + 3 = 7

Рис. 2.9. Операция объединения (графы не имеют общих вершин)

В случае если множества К(С|), Г(б2) пересекаются, т.е. исходные графы имеют общие вершины, операция объединения осуществляется так же, за исключением того, что общие вершины склеиваются или сливаются в одну единую вершину. Если общие вершины в двух исходных графах соединены ребром, то эти ребра тоже склеиваются.

Сложение графов. Пусть даны два графа б) = (Е(б,), (/(б,)), б2 = (К(б2), б(б2)), причем множества Е(б|), Е(б2) не пересекаются. Тогда суммой графов б,, б2, обозначаемой б = б, + б2, называется граф, полученный как их объединение, при этом каждая вершина графа С?! соединяется ребром с каждой вершиной графа С2.

При графической интерпретации операции сложения складываемые графы просто изображаются рядом (как при операции объединения), а затем проводятся ребра от каждой вершины первого графа к каждой вершине второго графа. Полученный в итоге граф будет иметь количество вершин, равное сумме вершин исходных графов: п = пх + п2, а количество ребер — сумме ребер исходных графов плюс количество новых ребер, равное произведению количеств вершин исходных графов: т = тх + т2 + пх ? п2 (рис. 2.10).

(7 = <7, + (^2 п-пх+п2 = 4 + 3 = 7

Рис. 2.10. Операция сложения (графы не имеют общих вершин)

В случае если множества К(С|), Е((72) пересекаются, т.е. исходные графы имеют общие вершины, операция сложения осуществляется так же, за исключением того, что общие вершины склеиваются или сливаются в одну единую вершину. Если общие вершины в двух исходных графах соединены ребром, то эти ребра тоже склеиваются. При этом важно отметить, что общие (склеенные) вершины не участвуют в построении новых ребер. Подробнее вопрос выполнения операций при наличии общих вершин изложен в [10, 11].

В ряде случаев важно знать, что в результате операции сложения если исходные графы были полные, то и полученный граф обязательно будет полным. Интересно также, что суммой двух пустых графов на Л71 и п2 вершинах при отсутствии общих вершин является полный двудольный граф К„ „ .

Существуют и другие операции над графами, с описанием которых можно ознакомиться в специальной литературе [5—8].

Связность графов

Маршрутом в данном графе С называется конечная последовательность ребер вида 0, V]}, {у1? у2}, {г_1, V,"}, обозначаемая также

(2.1)

Каждому маршруту соответствует последовательность вершин у0, У], у2, •••, у- В этом случае у0 называется начальной вершиной, а Утконечной вершиной маршрута, а сам маршрут называется маршрутом из у0 в у,„. Длиной маршрута называется число ребер в нем. В ориентированном графе маршрут называется путем. Маршрут (путь) называется цепью, если все его ребра различны.

Маршрут (путь) называется простой незамкнутой цепью, если все вершины у0, у|? у2, ..., ут различны.

Иными словами, цепь — маршрут (путь) без повторяющихся ребер, простая цепь — маршрут (путь) без повторяющихся вершин.

Маршрут (путь) называется простой замкнутой цепью, или простым циклом, если все вершины У0, У|, у2, ..., у,„ различны, кроме у0 = у,„.

Неориентированный граф (7 называется связным, если для любых двух различных вершин у, и у2 существует простая незамкнутая цепь из у, в у2.

На этих определениях основаны некоторые важные численные характеристики графов.

Расстоянием г между вершинами у, и уу- называется длина минимального пути между этими вершинами.

Диаметром с1 связного графа (7 называется максимально возможное расстояние между любыми двумя его вершинами. Для несвязных графов диаметр полагается равным бесконечности.

Центром графа С называется такая вершина у, для которой максимальное расстояние между у и любой другой вершиной является наименьшим из всех возможных. Это расстояние называется радиусом Я. Таким образом,

(2.2)

Я = тіп(тах/*(У|, у2)),

V, У2

где г(у1? у2) — расстояние между у, и у2.

Задача 2.2. Найти диаметр графа на рис. 2.11.

Решение.

Процесс нахождения диаметра графа представляет собой, по сути, полный перебор. Сначала необходимо по всем парам вершин вычислить расстояние, а затем наити максимум из этого множества чисел. Соответствующие расстояния представлены в табл. 2.8.

Таблица 2.8

Расстояние между вершинами в графе на рис. 2.11

Вершины

1

2

3

4

5

6

7

8

9

10

1

0

1

2

2

3

3

2

3

2

1

2

1

0

1

2

3

2

1

2

3

2

3

2

1

0

1

2

3

2

3

3

2

4

2

2

1

0

1

2

3

3

2

1

5

3

3

2

1

0

1

2

3

3

2

6

3

2

3

2

1

0

1

2

3

3

7

2

1

2

3

2

1

0

1

2

3

8

3

2

3

3

3

2

1

0

1

2

9

2

3

3

2

3

3

2

1

0

1

10

1

3

2

1

2

3

3

2

1

0

Необходимо быть аккуратным при вычислении расстояний, например расстояние между 1-й и 4-й вершинами равно двум, так как помимо пути (1—2—3—4), имеющего длину 3, также существует путь (1 — 10—4), имеющий длину 2. Среди всех значений согласно определению диаметра выбирается наибольшее, в данном случае диаметр равен трем.

Ответ. Диаметр равен 3.

Любой граф можно разбить на непересекающиеся связные графы, называемые компонентами, или компонентами связности графа С. Внутри каждой компоненты будет выполняться определение связности графа. Таким образом, несвязный граф имеет более одной (две или больше) компоненты. Связный граф всегда, по определению, состоит из одной компоненты (рис. 2.12).

Очевидно, что связный граф представляет собой простой цикл тогда и только тогда, когда каждая вершина имеет степень 2.

Можно также доказать такую теорему.

Графы, состоящие из одной (а), двух (б), грех (в) компонент

Рис. 2.12. Графы, состоящие из одной (а), двух (б), грех (в) компонент

Теорема 2.1

Пусть в графе С = (V, (/) п вершин и т ребер. Тогда в нем не менее (п - т) связных компонент.

Если при этом в (7 нет циклов, то граф состоит ровно из (п - т) связных компонент. Из этого следует, что если т < п - 2, то любой граф с п вершинами и т ребрами несвязен.

При операциях над графами иногда значение диаметра проще найти, рассматривая по отдельности участвующие в операциях графы.

При этом всегда надо помнить, что диаметр любого несвязного графа равен бесконечности.

При операции объединения по этой причине в случае отсутствия общих вершин диаметр всегда равен бесконечности. При наличии одной общей вершины значение диаметра вычисляется как сумма диаметров двух участвующих в объединении графов. В более сложных случаях необходимо рисовать полученный граф и анализировать его. Важно помнить, что если в задаче не указано, сколько общих вершин имеют объединяемые графы, то необходимо рассматривать все случаи.

Задача 2.3. Найти значение диаметра графа, полученного в результате объединения простого цикла на семи вершинах и полного графа на пяти вершинах, если известно, что они имеют одну общую вершину.

Решение.

Диаметр простого цикла на семи вершинах равен [7/2] = 3, а диаметр полного графа всегда равен единице. Значит, диаметр полученного в результате объединения графа на рис. 2.13 равен 3+1=4.

Ответ. 6 = 4.

При операции сложения двух графов в случае отсутствия общих вершин диаметр всегда будет не более двух. Это связано с тем, что при сложении графов из каждой вершины первого графа тянется ребро к каждой вершине второго графа. Значит, если рассматривать вершины из разных графов, между ними расстояние всегда равно единице. Если рассматривать две вершины из одного графа,

1

Объединение двух графов с одной общей вершиной

Рис. 2.13. Объединение двух графов с одной общей вершиной

з

то всегда можно за один шаг перебраться в соседний граф, а потом за один шаг вернуться обратно. Единице диаметр двух складываемых графов может быть равен только в том случае, если оба исходных графа были полные, в этом случае при сложении также получается полный граф.

При операции дополнения никаких предварительных оценок сделать нельзя, необходимо рассматривать полученную конфигурацию и следить за связностью.

Вершинной связностью к («каппа») связного графа (7 называется наименьшее число вершин, которое нужно удалить, чтобы граф перестал быть связным.

Для несвязного графа вершинная связность равна нулю. Для полного графа на п вершинах вершинная связность полагается равной п - 1.

Множество ? вершин разделяет вершины у, и у, если при удалении этих вершин из графа вершины у, и у- оказываются в разных компонентах связности.

Ясно, что для всех графов, кроме полного, вершинная связность графа равна минимуму из всех наименьших чисел вершин, разделяющих две вершины у, и Уу, взятому по всевозможным парам (у„ у-). Кроме того, можно заметить, что пары смежных вершин можно не рассматривать — они все равно не смогут изменить ответ.

Алгоритм нахождения величины вершинной связности основан на теореме Менгера.

Теорема 2.2. Теорема Менгера

Для любых двух вершин наибольшее число вершинно-непересека-ющихся простых цепей, соединяющих их, равно наименьшему числу вершин, разделяющих эти вершины.

Граф (7, представленный на рис. 2.14, связен, но он перестает быть связным, если удалить вершину 4. Поэтому к = 1.

Граф с вершинной связностью к = 1

Рис. 2.14. Граф с вершинной связностью к = 1

Можно нарушить связность графа, удаляя некоторые его ребра. У графа (7 (см. рис. 2.14) для этого придется удалить не менее трех ребер. Например, граф распадается на две компоненты после удаления ребер (4, 5), (4, 6), (4, 7).

Реберной связностью X («лямбда») связного графа (7 называется наименьшее число ребер, которое нужно удалить, чтобы граф перестал быть связным. Для несвязного графа реберная связность равна нулю. Число реберной связности одновершинного графа также полагается равным нулю.

Вершина V графа (7 называется точкой сочленения (разделяющей вершиной), если граф (7-у, полученный после операции удаления у графа (7 вершины у, имеет больше компонент связности, чем сам граф (7. В частности, если (7 связен и у — точка сочленения, то (7 - у несвязен.

Ребро и графа <7 называется мостом, если его удаление увеличивает число компонент связности графа.

Таким образом, точки сочленения и мосты — это своего рода «узкие места» графа. Граф на рис. 2.15 имеет три точки сочленения — вершины а, Ь, с и один мост — ребро (а, Ь).

Граф с реберной связностью X = 1

Рис. 2.15. Граф с реберной связностью X = 1

Для любого графа справедливо соотношение Уитни между реберной связностью X, вершинной связностью к и наименьшей из степеней вершин 5:

к < X < 5. (2.3)

На основании этого соотношения иногда удается показать невозможность построения некоторых графов, как, например, в следующей задаче.

Задача 2.4. Построить или обосновать невозможность построения графа на 11 вершинах, у которого наименьшая степень вершин равна семи, а вершинная связность равна восьми.

Решение.

Наименьшей из степеней вершин является степень 7. По условию вершинная связность равна восьми. По соотношению Уитни это означает, что графа не существует. Получим, что 8 < X < 7.

Ответ. Графа не существует.

Деревья и сети

Ациклическим называется граф, не содержащий циклов. Деревом называется связный ациклический граф. Несвязный граф, состоящий из нескольких деревьев, иногда называют лесом.

Вершина в графе называется висячей, если ее степень равна единице. Дерево должно обязательно иметь висячую вершину, так как если бы степень всех вершин в дереве была бы больше или равна двум, то граф должен иметь цикл, что противоречит определению дерева. Можно доказать следующее утверждение.

Теорема 2.3

Если граф <7 является деревом, то число его ребер (т) и число его вершин (п) связаны соотношением т = п - 1.

На самом деле верно и обратное утверждение, которое является частью общей теоремы, отражающей простейшие свойства дерева.

Теорема 2.4

Следующие четыре условия равносильны.

  • граф (7является деревом',
  • для числа ребер (т) и числа вершин в графе (л) всегда верно т = п-;
  • любые две вершины в графе могут быть связаны простым путем, и этот путь единствен',
  • граф (7 связен и не содержит циклов.

По этой причине в качестве определения понятия «дерево» можно также использовать другую формулировку. Дерево — связный граф, в котором существует одна и только одна простая цепь, соединяющая каждую пару вершин. Удобно считать, что граф, состоящий из одной изолированной вершины, тоже является деревом. На рис. 2.16 изображен лес, состоящий из четырех компонент, каждая из которых является деревом.

Лес, состоящий из четырех деревьев

Рис. 2.16. Лес, состоящий из четырех деревьев

В зависимости от сферы применения деревья удобно графически изображать по-разному. Если семантический смысл таков, что определенная висячая вершина является начальной (или конечной) для всей структуры, то может оказаться удобным расположить остальные вершины дерева (узлы) по ярусам. Так как для каждой пары вершин дерева существует единственный маршрут, то вершины удобно классифицировать по степени удаленности от корневой вершины. При этом ветвям, попавшим в один ярус, соответствует одинаковая длина пути исходного графа. Число путей в каждом дереве соответствует числу висячих вершин (листьев). При описании деревьев такого типа принято использовать термины: отец/сын или предок/потомок.

Классическим применением этих структур являются генеалогические деревья, отражающие связи между представителями определенного семейства. Графы такого рода также подходят для иллюстрации классификаций в различных областях знаний при построении иерархических структур сложных систем. Примером является структура выпускной квалификационной работы, которая состоит из глав, главы — из пунктов, некоторые пункты — из нескольких подпунктов. Аналогично может быть представлена структура управления в большой организации, подчиненность воинских формирований и т.д.

Упорядоченным деревом называется дерево, в котором поддеревья каждого узла образуют упорядоченное подмножество. Для упорядоченных деревьев принята терминология: старший и младший сын для обозначения соответственно первого и последнего сыновей некоторого узла (рис. 2.17).

Первый ярус

Предок

Потомок

Старший сын

Младший сын

Рис. 2.17. Упорядоченное дерево

Второй ярус Третий ярус

В информатике принято использовать подмножество множества деревьев, когда каждый узел либо является листом, либо образует два поддерева: левое и правое. Такой вид деревьев называется бинарными деревьями и используется при делении множества на два взаимоисключающих подмножества по какому-то признаку (так называемое дихотомическое деление). Бинарное дерево уровня п называется полным, если каждый его узел уровня п является листом, а каждый узел уровня меньше п имеет непустые левое и правое поддеревья. Примером полного бинарного дерева служит турнирная таблица по системе «плей-офф» (рис. 2.18).

Полуфинал

Финал

Победитель

Рис. 2.18. Бинарное дерево, отражающее результаты соревнований

'/, финала

Некоторые задачи требуют другого подхода, который позволит учитывать не только иерархические зависимости типа «родитель-потомок», но и более сложные связи между объектами, а также конкретные численные параметры, характеризующие эти связи. Для таких задач используются взвешенные ориентированные графы, называемые сетями.

Взвешенным называется граф, дугам или ребрам которого сопоставляются (приписываются) числа, называемые весом, или длиной, или стоимостью (ценой) дуги или ребра. В этом случае граф называется графом со взвешенными дугами (ребрами). Иногда веса приписываются вершинам графа, и тогда получается граф со взвешенными вершинами. Если в графе веса приписаны и дугам, и вершинам, то он называется просто взвешенным.

Сетью называется ориентированный граф со взвешенными дугами, т.е. граф, в котором каждой связи сопоставлено определенное число (вес). Обычно этими числами оценивается «стоимость» пути вдоль этой связи или длина связи, как на карте дорог. В каждом конкретном случае применения графа как формального средства описания проблемы эти числа могут трактоваться по-своему. Подробнее о сетевых моделях и их применении можно прочитать в [9].

Ориентированные графы

Полустепеныо исхода $“(у) вершины V в ориентированном графе называется число дуг, выходящих из данной вершины.

Полустепеныо захода 5+(у) вершины у в ориентированном графе называется число дуг, входящих в данную вершину.

В любом ориентированном графе выполняется равенство

Х*"(у,) = Х5+(уЛ (2-4)

/= 1 ;'=1

поскольку в обеих частях равенства каждая дуга учитывается ровно один раз.

Изолированной называется вершина, у которой и полустепень захода, и полустепень исхода равны нулю.

Истоком называется вершина, полустепень исхода которой положительна, а полустепень захода равна нулю.

Стоком называется вершина, полустепень захода которой положительна, а полустепень исхода равна нулю.

Путем в ориентированном графе Сот у, до у/?! называется последовательность ориентированных дуг (ребер) {у,, у2|, {у2, у3}, ..., {у,„_!, у„г} такая, что конец каждой предыдущей дуги (ребра) совпадает с началом следующей и ни одна дуга (ребро) не встречается более одного раза. Если в ориентированном графе С нашелся путь от уя до уь, то обратного пути от уь к уа может и не быть.

Простым в ориентированном графе называется путь, в котором ни одна вершина не содержится более одного раза.

Замкнутый путь в ориентированном графе называется ориентированным циклом.

Длиной пути называется число дуг (ребер) в этом пути. Расстоянием от до уь в ориентированном графе называется длина наикратчайшего пути от до уь. Если пути от уа до уь не существует, то расстояние от уй до уь считается бесконечным. Оно обозначается Расстояние от у„ до уь будем обозначать г{уа, уь).

Полным ориентированным называется граф, каждая пара вершин которого соединена в точности одной ориентированной дугой.

Компонентой сильной связности (КСС) ориентированного графа называется такое максимальное по включению подмножество его вершин, что между любыми двумя вершинами существует путь.

Соответственно, задача поиска компонент сильной связности в орграфе сводится к поиску такого разбиения множества вершин графа на набор подмножеств, что в рамках каждого подмножества любые две вершины взаимно достижимы друг из друга.

Эту задачу можно решать двумя различными способами.

Первый способ построен на классическом алгоритме нахождения пересечения положительной и отрицательной окрестностей каждой из вершин. Он характеризуется значительной надежностью, но довольно объемными временными затратами. При необходимости найти решение за более короткое время можно воспользоваться эмпирическим методом, разобрав граф на ключевые элементы: стоки, истоки и циклы. Детализированный алгоритм выглядит так.

Шаг 1. Поиск стоков и истоков. Каждый найденный сток или исток в любом случае является отдельной компонентой, так как по своему определению не может входить в состав других компонент.

Шаг 2. Поиск циклов. Вершины, входящие в цикл, всегда образуют общую компоненту. Возможно, это множество вершин не максимально по включению, но наличие цикла, как минимум, гарантирует, что входящие в этот цикл вершины входят также в общую компоненту. Это связано с тем, что по циклу всегда возможно из любой отдельно взятой вершины добраться до любой из вершин этого же цикла, что в полной мере согласуется с определением компоненты сильной связности.

Шаг 3. Склейка циклов. Если на предыдущем шаге были найдены циклы, имеющие хотя бы одну общую вершину, то такие циклы необходимо объединить в единую компоненту. Это связано с тем, что общие вершины являются узловыми в том смысле, что при операции объединения они связывают за счет склейки исходные циклы и с их помощью возможно добраться из любой вершины первого цикла в любую вершину второго.

Шаг 4. Проверка. Необходимо проверить, что в результате шагов 1—3 полученные компоненты сильной связности включают в себя все вершины исходного графа, причем ровно по одному разу. Иными словами, ни одна из вершин не должна быть включена более чем в одну компоненту и в результате процедуры все вершины должны быть распределены по компонентам. Если суммарное число вершин по всем компонентам меньше, чем общее количество вершин в исходном графе, то необходимо выявить те вершины, которые не вошли в список найденных компонент сильной связности и с особой внимательностью их рассмотреть. Причин обычно две. Первая: не слишком внимательно был произведен поиск циклов и на самом деле «забытые» вершины входят в один из пропущенных циклов. Вторая: эти «забытые» вершины действительно представляют собой отдельные компоненты, так как, не входя ни в один из циклов и не являясь в чистом виде ни стоками, ни истоками, образуют, по сути, шлюзы или мосты между какой-то частью графа и его стоком или истоком.

Задача 2.5. Найты все компоненты сильной связности в данном графе (рис. 2.19). Компоненты задать перечислением вершин.

Решение.

Шаг 1. Стоки: вершина 15. Значит, КСС1 = {15}. Истоки: вершина 1. Значит, КСС2 = {1}.

Шаг 2. Циклы. Ц1={3,4}; Ц2 = {11,9, 12, 16};ЦЗ = {6, 7}; Ц4 = {6, 14, 17, 13}; Ц5 = {3, 9, 5,4}.

Шаг 3. Склейка. Циклы Ц1 и Ц5 склеиваются по двум общим вершинам так, что Ц5 полностью поглощает Ц1. Обозначим полученный цикл как Ц15: Ц15 = {3, 9, 5, 4}. Далее циклы Ц15 и Ц2 склеиваются по вершине 9, образуя цикл Ц152 = {3, 9, 5, 4, 11, 12, 16}. Кроме того, можно склеить циклы ЦЗ и Ц4, образовав в результате цикл Ц34 = {6, 7, 14, 17, 13}. Таким образом, в результате применения операции склейки циклов получено два цикла, дальнейшая склейка которых невозможна: Ц152 = {3, 9, 5, 4, 11, 12, 16} и Ц34 = {6, 7, 14, 17, 13}. Значит, КССЗ = {3, 9, 5, 4, 11, 12, 16} и КСС4 = {6, 7, 14, 17, 13}.

Шаг 4. Проверка. В найденных четырех КСС совокупно участвуют 14 вершин. Всего в исходном графе 17 вершин. Оставшиеся три не вошли в списки истоков, стоков и циклов. Это вершины 2, 10, 8. Рассмотрим их подробнее. Вершины 2 и 10 являются типичными шлюзами между истоком (вершиной 1) и остальной частью графа. В них можно попасть только из истока (вершины 1), а значит, выйдя из этих вершин, обратно уже не вернемся. Таким образом, это отдельные компоненты: КСС5 = {2} и КСС6 = {10}. Что касается вершины 8, то она, на первый взгляд, кажется похожей на шлюз между основной частью графа и стоком, вершиной 15. В реальности, если посмотреть более внимательно, можно увидеть, что из вершины 8 можно также попасть в вершину 14, которая является составной частью цикла {6, 14, 17, 13}, а оттуда с помощью цикла {6, 7} снова вернуться в вершину 8. Значит, ситуация тут в корне другая и на этот раз вершина 8 пропущена ошибочно. И действительно, при более внимательном рассмотрении можно заметить, что в графе есть еще один цикл: Ц6 = {6, 7, 8, 14, 17, 13}, который как раз подтверждает включение вершины 8 в КСС4.

Ответ. В данном графе шесть компонент сильной связности: КСС1 = {15}; КСС2 = {1}; КССЗ = {3, 9, 5, 4, 11, 12, 16}; КСС4 = {6, 7, 8, 14, 17, 13}; КСС5 = {2} и КСС6 = {10}.

При визуальном подходе к решению задачи данный способ обычно дает результат значительно быстрее, чем классическое пересечение окрестностей. Недостатком можно считать то обстоятельство, что при некоторой невнимательности можно пропустить какой-либо цикл, например для графа на рис. 2.20 можно не заметить большой цикл, связывающий несколько маленьких.

Большинство обучающихся сразу видят два цикла: {1, 2, 3} и {4, 5, 6, 7}, ошибочно предполагая, что в графе две компоненты сильной связности. На самом деле есть и общий цикл {1, 2, 3, 4, 5, 6, 7}; таким образом, данный граф сильносвязный и состоит из единственной компоненты, в которую входят все вершины. Аналогичная ситуация

Большой цикл графа, связывающий несколько маленьких циклов

Рис. 2.20. Большой цикл графа, связывающий несколько маленьких циклов

и с графом на рис. 2.19 — при более внимательном рассмотрении мог быть найден большой цикл {6, 7, 8, 14, 17, 13}, что сэкономило бы время и позволило не разбираться отдельно с вершиной 8.

Существует довольно простой способ проверки результата решения задачи на нахождение компонент сильной связи в ориентированных графах независимо от того, какой способ применялся для поиска этого решения. Он состоит в построении конденсата графа.

Конденсат графа представляет собой ориентированный граф, в котором вершины соответствуют компонентам сильной связности, а дуги отражают достижимость компонент друг из друга.

Процесс построения конденсата состоит из двух шагов. Сначала рисуются вершины, соответствующие компонентам сильной связности, каждую такую укрупненную вершину удобно назвать перечислением входящих в данную компоненту вершин. Затем строятся дуги по очень простому принципу: если из /-й компоненты в исходном графе достижимау-я компонента, то в конденсате строится дуга (/,У) (рис. 2.21).

Построенный конденсат полезно проанализировать на предмет нахождения циклов — их там быть ни в коем случае не должно. Если обнаружился цикл, значит, есть множество взаимодостижимых укрупненных вершин, и следовательно, входящие в наименование

этих укрупненных вершин конденсата вершины исходного графа должны были войти в одну компоненту. Например, если была допущена ошибка при решении задачи на рис. 2.20 и найдены только два цикла {1, 2, 3} и {4, 5, 6, 7}, то конденсат выглядел бы так (рис. 2.22, а) как видно, в нем присутствует цикл, чего быть не должно. Это сигнал ошибки. При правильном решении конденсат выглядит иначе (рис. 2.22, б).

  • б)
  • а)

Рис. 2.22. Конденсат графа, изображенного на рис. 2.20, при ошибочном (а)

и при правильном (б) нахождении КСС

Базисные циклы и разрезы

В связном графе б удаление одного ребра, принадлежащего некоторому выбранному циклу, не нарушает связности оставшегося графа. Применим эту процедуру к одному из оставшихся циклов, и так до тех пор, пока не останется ни одного цикла. В результате получим дерево, связывающее все вершины графа (7, оно называется остовным деревом, или остовом, или каркасом графа б.

Строго говоря, подграф = (К,, II {) графа (7= (V, б) называется остовным деревом, если б] — дерево и У1 = V. У произвольных связных графов существует не единственный способ выделения остова. Единственным образом выделить остов можно только у дерева. На рис. 2.23 изображен исходный граф и два возможных способа выделения остова. Какой из них выбрать, зависит от личных предпочтений или от планируемых в дальнейшем действий.

Варианты выделения остова в графе

Рис. 2.23. Варианты выделения остова в графе: а — исходный граф; б — остов, вариант 1; в — остов, вариант 2

Как видно, выделенные остовы, если их рассматривать отдельно от остальных ребер, представляют собой деревья, в которые вошли все вершины графа. Те ребра, которые не вошли в остов, называются свободными хордами или просто хордами. Если построить цикл, состоящий только из одной свободной хорды и каких-либо ребер остова, то такой цикл будет называться базисным.

В общем случае обозначим через (7 произвольный граф с п вершинами, т ребрами и к компонентами. Применяя описанную в начале параграфа процедуру к каждой компоненте (7, получим в результате граф, называемый остовным лесом. Число удаленных в этой процедуре ребер называется цикломатическим числом графа С и обозначается через у(С).

Поскольку для каждой /-й компоненты на п, вершинах число ребер в соответствующем остовном дереве равно П/ — 1, то на к компонентах с общим количеством вершин, равным п (п — сумма всех «,), сумма ребер в остовном лесе составит (п - к). Значит, из имеющихся т ребер нужно будет удалить т-(п-к) = т-п + к ребер. Количество удаленных ребер равно количеству свободных хорд, следовательно, так как каждый базисный цикл строится на одной хорде, для произвольного графа цикломатическое число определяется по формуле

у (Є) = т - п + к (2.5)

и является неотрицательным целым числом.

Таким образом, цикломатическое число дает меру связности графа. Цикломатическое число дерева равно нулю, а цикломатическое число простого цикла равно единице.

Кроме того, цикломатическое число, в силу того что оно равно числу удаленных ребер при построении остова, равно также и количеству базисных циклов. Для конкретного выделенного остова можно найти все базисные циклы, это удобно делать с помощью так называемой матрицы базисных циклов.

Задача 2.6. Построить матрицу базисных циклов для графа на рис. 2.23, а при условии, что выбранный остов показан на рис. 2.23, б.

Решение.

Столбцам матрицы будут соответствовать ребра исходного графа, причем для удобства построения выпишем сначала свободные хорды, а затем ребра выделенного остова. Строки будут содержать искомые базисные циклы; при этом ребра, вошедшие в соответствующий цикл, помечаются в матрице единичками, пустые клетки по умолчанию содержат нули (табл. 2.9).

Матрица базисных циклов для графа на рис. 2.23, б

Базисные

Хорды

Ребра остова

ЦИКЛЫ

3,8

2,8

7,8

5,8

2,3

1,2

1,7

1,8

8,4

7,6

6,5

БЦ1

1

1

1

1

БЦ2

1

1

1

БЦЗ

1

1

1

БЦ4

1

1

1

1

1

Удобно также определить коциклический ранг или просто ранг графа (7 как число ребер в его остовном лесе. Ранг определяется по формуле

Х(0) = п-к (2.6)

и является неотрицательным целым числом. Это число равно количеству базисных разрезов графа. В отличие от базисных циклов базисные разрезы строятся на одном ребре остова и на необходимом количестве ребер остова.

Базисный разрез составляет совокупность ребер, состоящая из одного ребра остова и нескольких хорд, удаление которых делает исходный связный граф несвязным (а для произвольного графа в общем случае увеличивает количество компонент связности).

Правило построения базисных разрезов. Возьмем одно из ребер остова и мысленно его удалим. Поскольку остов является деревом (или в общем случае лесом), то удаление одного ребра в обязательном порядке приведет к увеличению количества компонент связности. Иными словами, какая-то вершина или набор вершин будет откалываться («отваливаться») от основной части графа. Далее если посмотреть на исходный граф, то после «разрезания» «толстого» ребра остова окончательному откалыванию данной вершины (набора вершин) чаще всего препятствуют некоторые «тонкие» ребра (хорды). Совокупность таких хорд вместе с исходным ребром остова и составляет базисный разрез.

Чтобы не ошибиться в построении базисного разреза, можно отдельно нарисовать остов графа и именно на основе его определять, какие вершины собираются отделяться после удаления одного из ребер остова. По картинке остова это видно графически, и затем «откалывающийся» фрагмент графа на исходной картинке можно обвести замкнутой линией. Тогда те ребра, которые будут пересекаться этой линией, как раз и составят базисный разрез на основе этого остовного ребра.

Таким образом, для конкретного выделенного остова можно найти все базисные разрезы, это удобно делать с помощью так называемой матрицы базисных разрезов.

Задача 2.7. Построить матрицу базисных разрезов для графа на рис. 2.23, а при условии, что выбранный остов показан на рис. 2.23, б.

Решение.

Столбцам матрицы будут соответствовать ребра исходного графа, причем для удобства построения выпишем сначала ребра выделенного остова, а затем свободные хорды. Строки будут содержать искомые базисные разрезы; при этом ребра, вошедшие в соответствующий разрез, помечаются в матрице единичками, пустые клетки по умолчанию содержат нули.

Например, возьмем ребро остова (2, 3) (рис. 2.24, б). При его удалении из остова собирается «отколоться» от остального графа вершина 3. В исходном графе вершина 3 будет удерживаться еще и хордой (3, 8) (рис. 2.24, а).

Определение ребер, входящих в базисный разрез

Рис. 2.24. Определение ребер, входящих в базисный разрез

при удалении ребра (2, 3): а — исходный граф; б — остов

При удалении из остова ребра (1,2) собираются «отколоться» от остального графа пара вершин: вершина 3 и вершина 2 — вместе с соединяющим их ребром (2, 3) (рис. 2.25, б). В исходном графе эта группа вершин будет удерживаться еще и хордами (3, 8) и (2, 8) (рис. 2.25, а).

Аналогично находим остальные разрезы. В результате получим матрицу базисных разрезов (табл. 2.10).

Ответ. Ответ представлен в табл. 2.10.

Определение ребер, входящих в базисный разрез

Рис. 2.25. Определение ребер, входящих в базисный разрез

при удаление ребра (1,2): а — исходный граф; 6 — остов

Таблица 2.10

Матрица базисных разрезов для графа на рис. 2.23, б

Базисные

Хорды

Ребра остова

разрезы

3,8

2,8

7,8

5,8

2,3

1,2

1,7

1,8

г*-

ОС

7,6

6,5

БР1

1

1

БР2

1

1

1

БРЗ

1

1

1

БР4

1

1

1

1

1

БР5

1

БР6

1

1

БР7

1

1

Эйлеровы и гамильтоновы графы

Эйлеровым путем в графе называется путь, содержащий все ребра графа ровно по одному разу. Эйлеровым циклом в графе называется цикл, содержащий все ребра графа ровно по одному разу.

Связный граф С называется эйлеровым, если в нем существует эйлеров цикл. Отметим, что в этом определении требуется, чтобы каждое ребро использовалось только один раз, при этом вершины могут использоваться неоднократно (рис. 2.26).

Теорема 2.5

Если граф С обладает эйлеровым циклом, то он является связным, а все его вершины — четными.

Верно и обратное утверждение, которое позволяет для произвольного графа точно определить наличие эйлерова цикла.

Эйлеров граф (а), граф, в котором есть незамкнутая эйлерова цепь (б), неэйлеров граф (в)

Рис. 2.26. Эйлеров граф (а), граф, в котором есть незамкнутая эйлерова цепь (б), неэйлеров граф (в)

Теорема 2.6

Если граф (7 — связный и все его вершины имеют четную степень, то он имеет эйлеров цикл.

В качестве примера практического применения эйлеровых графов можно привести план выставки, на которой необходимо так расставить указатели маршрута, чтобы посетитель смог пройти по каждому залу в точности по одному разу.

Иногда требуется не только определить эйлеровость графа, но и предложить наиболее эффективный способ превращения неэйлеровых графов в эйлеровые за счет удаления минимально возможного количества ребер.

Задача 2.8. Определить, является ли граф (рис. 2.27, а) эйлеровым, и если нетуказать с достаточным обоснованием, удаление какого минимального числа ребер делает граф эйлеровым. Указать, какие это ребра. Указать эйлеров цикл.

Решение.

Первое, что необходимо сделать, это проверить критерий эйле-ровости, а именно четность вершин графа. Как видно из рис. 2.27, б, в графе из п = 10 вершин восемь имеют нечетную степень.

Этапы решения задачи

Рис. 2.27. Этапы решения задачи:

а — исходный граф; б — в графе отмечены вершины нечетной степени;

в — граф после удаления ребер

Удобно при решении задач на рисунке заштриховать вершины, которые имеют нечетную степень. Поскольку удаление одного ребра может изменить степень двух вершин, то, если удалять попарно несмежные ребра, соединяющие только нечетные вершины, минимально возможное количество таких кандидатов на удаление будет 8/2 = 4. Нужно пробовать найти попарно несмежные ребра, соединяющие именно вершины нечетной степени. В данном случае это возможно — например, решением будут ребра (1, 2), (4, 5), (7, 8) и (6, 10).

Ответ. Исходный граф неэйлеров, так как в нем существует восемь вершин с нечетной степенью, а по теореме 2.5 в эйлеровом графе все вершины имеют четную степень. Чтобы граф стал эйлеровым, необходимо удалить как минимум четыре ребра. Такое решение есть: (1, 2), (4, 5), (7, 8), (6, 10). Тогда эйлеров цикл, например, выглядит таким образом: (1, 5, 6, 2, 3, 4, 6, 8, 9, 10, 5, 7, 1).

Рассмотрим вопрос существования простого цикла, проходящего ровно один раз через каждую вершину графа (7. Если такой цикл существует, то он называется гамильтоновым циклом, а (7 называется гамильтоновым графом (рис. 2.28).

Гамильтонов граф (а), граф, в котором есть незамкнутая гамильтонова цепь (б), негамильтонов граф (в)

Рис. 2.28. Гамильтонов граф (а), граф, в котором есть незамкнутая гамильтонова цепь (б), негамильтонов граф (в)

Эйлеровы и гамильтоновы циклы сходны по способу задания. Первые содержат все ребра, по одному разу каждое, вторые — все вершины, по одному разу каждую. Но, несмотря на внешнее сходство, задачи их поиска резко отличаются по степени трудности. Для решения вопроса о наличии эйлерова цикла в графе достаточно выяснить, все ли его вершины имеют четную степень.

Поиск необходимого и достаточного условия для того, чтобы граф был гамильтоновым, стал одной из главных нерешенных задач теории графов. О гамильтоновых графах, в сущности, известно очень мало. Общих и легко осуществляемых действий, с помощью которых можно было бы достоверно выяснить, является ли данный граф гамильтоновым, не существует. Однако имеются достаточные условия на гамильтоновость, которые довольно легко проверить.

Наиболее известными являются теоремы Дирака и Оре.

Теорема 2.7. Теорема Дирака

Если в простом графе с п вершинами, причем п > 3, выполняется условие 5(у) > я/2 для любой вершины у, то граф (7 является гамильтоновым.

Теорема 2.8. Теорема Оре

Пусть п — количество вершин в данном графе. Если для любой пары несмежных вершин/5 vJ) выполнено неравенство 5(у,) + 5(у) > п, то граф является гамильтоновым.

Нетрудно заметить, что всякий граф Дирака автоматически является графом Оре, но обратное неверно. На рис. 2.29 представлен пример графа Оре, не являющегося графом Дирака.

Недостаток обоих критериев состоит в том, что даже если ни одно из этих условий не выполняется, граф может оказаться гамильтоновым. Например, существуют гамильтоновы графы, не являющиеся графами Дирака и Оре (см. рис. 2.29).

Ф "О

а) б) в)

Рис. 2.29. Граф Оре, не являющийся графом Дирака (а), гамильтонов граф,

не являющийся графом Дирака (б), гамильтонов граф, не являющийся

графом Оре (в)

В некоторых задачах дополнительно используется условие Поша. В данном учебнике оно не рассматривается, однако заинтересованный читатель легко найдет соответствующий материал в [5—6].

Устойчивость графов

Внутренне устойчивое множество вершин (7 — множество вершин графа, никакие две вершины которого не инцидентны.

Пустой подграф — внутренне устойчивое множество вершин такое, что при добавлении к нему хотя бы одной вершины образуется хотя бы одно ребро.

Иными словами, пустой подграф — максимальное по включению внутренне устойчивое множество вершин. В данном определении «максимальность» означает «нерасширяемость». Граф может иметь несколько пустых подграфов различной мощности.

Вершинное число независимости графа (или число внутренней устойчивости графа) — мощность наибольшего пустого подграфа, обозначается как ?0((7).

Независимое множество ребер (или паросочетание) — множество ребер графа, никакие два ребра которого не инцидентны.

Реберное число независимости (или число паросочетания) графа — мощность наибольшего паросочетания (независимого множества ребер), обозначается как 8](С).

В общем случае число вершинной внутренней устойчивости изменяется от п (у пустых графов на п вершинах) до единицы (у полных графов на п вершинах).

Для нахождения числа внутренней устойчивости нужно определить мощность максимального пустого подграфа. Существует алгоритм, который позволяет найти все пустые подграфы. Из них впоследствии выбирается максимальный по мощности подграф.

Алгоритм поиска пустых подграфов

  • 1. Строим фиктивную вершину, ее пометка — множество всех вершин графа 1? у2,..., у,7}.
  • 2. Выбираем любую вершину из указанного в пометке множества, рисуем ее на уровень ниже (это потомок).
  • 3. Рядом с ней на этом же уровне рисуем все смежные с ней вершины из множества, указанного в пометке вершины-родителя.
  • 4. В качестве пометки каждой полученной вершины у, указываем множества вершин, входящих в ее неокрестность (т.е. несмежных С У,).
  • 5. Повторяем шаги 2—4 для всех получающихся веток дерева до тех пор, пока все пометки не будут пустые.
  • 6. На полученном дереве все пути от начальной фиктивной вершины до каждой концевой вершины будут представлять собой множества вершин, образующих пустые подграфы.

Задача 2.9. Для заданного графа (рис. 2.30) найти все пустые подграфы и число вершинной внутренней устойчивости.

Решение.

В соответствии с алгоритмом получим дерево (рис. 2.31). В этом дереве все пути от фиктивной вершины до каждого листа есть пустые подграфы или максимальные внутренне устойчивые множества (в данном случае — вершин). Повторные пути указываются единократно, например пути 1—4—6, 1—6—4 и 4—1—6 задаются единственный раз множеством {1,4, 6}.

Выбираем из них самое большое (с максимальной мощностью), это, например, {1,4, 6}, его мощность равна трем. Значит, е0 = 3.

1

Условие задачи 2.9

Рис. 2.30. Условие задачи 2.9

Дерево пустых подграфов для графа на рис. 2.30

Рис. 2.31. Дерево пустых подграфов для графа на рис. 2.30

Ответ. Пустые подграфы: {2, 6}; {2, 7}; {1, 5, 7}; {1,4, 6}; {3, 2, 7}; {3, 4}. в0 = 3.

Вершинное покрытие — такое множество вершин графа, что каждое ребро графа инцидентно хотя бы одной из этих вершин.

Число вершинного покрытия графа С — мощность наименьшего вершинного покрытия, обозначается как л:0((7).

Реберное покрытие — такое множество ребер связного графа, что каждая вершина графа инцидентна хотя бы одному из этих ребер.

Число реберного покрытия графа (7 — мощность наименьшего реберного покрытия, обозначается как 7і|(С).

На рис. 2.32 обозначены реберное покрытие графа (пунктиром), максимальное внутренне устойчивое множество вершин (белые вершины) и вершинное покрытие (серые вершины).

Величины є0(<7), 8]((7), 0((7), 7Г|((/) являются инвариантами графа. Между этими инвариантами существует связь.

о

Реберное и вершинное покрытия

Рис. 2.32. Реберное и вершинное покрытия

1. Для любого графа (7 = (V, Ц) сумма числа вершинного покрытия и вершинного числа независимости постоянна и равна количеству вершин (7:

0(= У{0). (2.7)

2. Если граф (7 = (V, (/) не имеет изолированных вершин, то сумма числа паросочетания и числа реберного покрытия постоянна и равна количеству вершин С7:

г;(С) + к1(С) = У(С). (2.8)

Прежде чем определить понятие внешней устойчивости, уточним правила покрытия.

Любая вершина покрывает:

  • • саму себя;
  • • смежные вершины;
  • • инцидентные ребра.

Любое ребро покрывает:

  • • самого себя;
  • • смежные ребра;
  • • инцидентные вершины.

Вершинное число внешней устойчивости графа (7 — минимальная мощность множества вершин, покрывающих все вершины графа, обозначается как (30.

Реберное число внешней устойчивости графа (7 — минимальная мощность множества ребер, покрывающих все ребра графа, обозначается как (3[.

В общем случае число вершинной внешней устойчивости изменяется от единицы (у полных графов на п вершинах) до п (у пустых графов на п вершинах).

Основная идея алгоритма поиска минимального покрытия заключается в построении модифицированной матрицы смежности (обычная матрица смежности, только по главной диагонали у нее единички), чтобы затем при помощи алгебры логики найти наименьшее число строк, покрывающих все столбцы этой матрицы (или столбцов, покрывающих строки, — разницы нет, матрица — симметричная).

Алгоритм нахождения минимального покрытия

  • 1. Построить матрицу смежности и заполнить все клетки главной диагонали единицами.
  • 2. Составить логическое выражение в виде произведения сумм логических переменных, соответствующих вершинам графа (или ребрам — если ищется реберное число внешней устойчивости). Каждая сумма представляет собой сложение переменных, которые в данной строке содержат единицу. Логическое сложение обозначается как «+», логическое умножение — как «•».
  • 3. Привести это выражение к ДНФ (дизъюнктивной нормальной форме), т.е. к сумме произведений переменных.
  • 4. Мощность максимального слагаемого и есть искомое число внешней устойчивости.

Задача 2.10. Для заданного графа (рис. 2.33) с достаточным обоснованием найти число внешней вершинной устойчивости.

Решение.

Построим покрытия (табл. 2.11).

Таблица 2.11

Матрица покрытий для графа на рис. 2.33

Вершины

1

2

3

4

5

6

1

1

1

1

0

0

0

2

1

1

1

1

1

0

3

1

1

1

0

1

1

4

0

1

0

1

1

0

5

0

1

1

1

1

1

6

0

0

1

0

1

1

Построим логическое выражение (идем по строчкам):

(1+2 + 3)-(1 + 2 + 3 + 4 + 5)-(1+2 + 3 + 5 + 6)-(2 + 4 + 5)х х (2 +3 + 4 +5+ 6)-(3 + 5+ 6). (2.9)

Упрощаем с учетом того, что по закону поглощения а ? (а + Ь) = а:

  • (1 + 2 + 3) • (1 + 2 + 3 + 4 + 5) = (1 +2 + 3):
  • (2 + 4 + 5) • (2 + 3 + 4 + 5 + 6) = (2 + 4 + 5):

П + 2 + 3 + 5 + 6) • (3 + 5 + 6) = (3 + 5 + 6). (2.10)

Покрытие, таким образом, равно (1 + 2 + 3) - (2 + 4 + 5) - (3 + 5 + 6). Далее раскрываем скобки:

(1 + 2 + 3)-(5 + 2- 3 + 2- 6 + 4- 3 + 4- 6) =

= 1- 5 + 1 - 2- 3 + 1- 2- 6+1 - 4- 3+1 - 4- 6 + 2- 5 +

+ 2- 2- 3 + 2- 2- 6 + 2- 4- 3 + 2- 4- 6 + 3- 5 + 3- 2- 3 +

+ 3- 2- 6 + 3- 4- 3 + 3- 4-6. (2.11)

Упрощаем по закону поглощения (х + х • у = х) и с учетом того, что х • х = х.

Получим

1 -5 + 1 -2-3+1 -2-6+1 43+1 -4-6 +

+ 2- 5 + 2- 2- 3 + 2- 2- 6 + 2- 4- 3 + 2- 4- 6 + 3- 5 + 3- 2- 3 +

+ 3- 2- 6 + 3- 4- 3 + 3- 4- 6 =

= 2- 6 + 2- 3 + 2- 3 + 4- 3+1-5 + 1- 4- 6 + 2- 5 + 3- 5 =

= 2*6 + 2- 3 + 4- 3+1 - 5 + 1 - 4- 6 + 2- 5 + 3- 5. (2.12)

Получили ДНФ, выбираем самое короткое слагаемое, например 2 • 6. Значит, искомое число внешней устойчивости равно двум, а пример внешне устойчивого множества вершин — {2, 6}.

Ответ. (30 = 2.

Раскраска графов

При рассмотрении произвольного неориентированного графа можно поставить следующую задачу. Пусть необходимо раскрасить вершины графа так, чтобы любые две смежные вершины были раскрашены в разные цвета, при этом число использованных цветов должно быть наименьшим.

Это число называется хроматическим числом графа 6, будем его обозначать /?(6). Если /?(6) = к, то граф называется к-раскрашива-емым.

Функцией Гранди называется функция на вершинах графа, отображающая вершины в множество {1,2, /?}, причем если вершина у,-

окрашена в цвет с номером к, то функция Гранди /?(у,) равна к.

Ясно, что для данного графа хроматическое число является единственным, но функций Гранди может быть очень много. Естественно, что найти хотя бы одну функцию Гранди — значит найти одну из возможных наилучших раскрасок (таких раскрасок может быть много).

Заметим, что если граф является полным, т.е. любые две вершины являются смежными, то хроматическое число такого графа равно п, где п — число вершин.

На рис. 2.34 изображен граф, у которого хроматическое число равно четырем (и следовательно, ^-раскрашиваемый граф при к > 4), цвета обозначены греческими буквами.

Граф, у которого хроматическое число равно четырем

Рис. 2.34. Граф, у которого хроматическое число равно четырем

Существует несколько алгоритмов нахождения точного значения хроматического числа.

Один из алгоритмов основан на теореме об оптимальной раскраске.

Теорема 2.9. Теорема об оптимальной раскраске

Если граф С является к-раскрашиваемым, то он может быть раскрашен с использованием к (или меньшего числа) красок с помощью следующей процедуры, сначала в один цвет окрашивается 5(С) — некоторый пустой подграф графа С, затем окрашивается в следующий цвет пустой подграф на множестве С ^(С) и т.д., до тех пор пока не будут раскрашены все вершины.

По своей сути алгоритм повторяет формулировку теоремы. Пусть имеем граф С, найдем в нем какой-либо пустой подграф, который обозначим ^ и все вершины, входящие в этот подграф, окрасим в цвет № 1. Далее удалим из данного графа все вершины, входящие в этот подграф (вместе с ребрами), и для нового графа снова найдем пустой подграф, который обозначим 52. Эти новые вершины окрасим в цвет № 2, затем удалим эти вершины из графа вместе с соответствующими ребрами и снова находим пустой подграф, который окрасим в цвет № 3, и т.д. Можно доказать, что при любом способе осуществления этой процедуры придем к наилучшей раскраске и найдем некоторую функцию Гранди и хроматическое число данного графа.

Задача 2.11. Найти с достаточным обоснованием точное значение хроматического числа графа (рис. 2.35, а) и предложить вариант раскраски.

Условие задачи 2.11 (а); этапы решения задачи 2.11 (б, в)

Рис. 2.35. Условие задачи 2.11 (а); этапы решения задачи 2.11 (б, в)

Решение.

Возьмем первый пустой подграф {2, 6}. Покрасим эти вершины в первый цвет (например, красный). Удалим вершины 2 и 6 вместе с инцидентными ребрами (рис. 2.35, б), затем в полученном графе снова выделим пустой подграф, пусть это будет {1,5, 7}.

Покрасим эти вершины во второй цвет (например, синий). Удалим вершины 1, 5, 7 вместе с инцидентными ребрами (рис. 2.35, в). В результате остались две несмежные вершины {3, 4}, которые покрасим в третий цвет (зеленый). Таким образом, получен несколько иной способ раскраски, но хроматическое число, как и следовало ожидать, равно трем.

Ответ. И = 3; раскраска: {2, 6} — красный цвет; {1,5,7} — синий; {3, 4} — зеленый.

В ряде случаев применяется классический алгоритм, основанный на первоначальном поиске всех пустых подграфов и последующем нахождении минимального покрытия.

Алгоритм на основе метода поиска наименьшего покрытия. Поскольку при любой допустимой раскраске графа (7 множество вершин, окрашиваемых в один и тот же цвет, должно быть независимым множеством, то всякую допустимую раскраску можно интерпретировать как разбиение всех вершин графа (7 на такие независимые множества. Далее если каждое независимое множество расширить до максимального (путем добавления к нему других вершин), то раскраска графа С может быть тогда истолкована как покрытие вершин графа (7 максимальными независимыми множествами вершин (пустыми подграфами). Очевидно, что в последнем случае некоторые вершины графа (7 могут принадлежать более чем одному максимальному независимому множеству (пустому подграфу). Это говорит о возможности существования различных допустимых раскрасок (использующих одно и то же число цветов), так как вершину, принадлежащую разным максимальным множествам, можно окрасить в любой из цветов, соответствующих тем максимальным независимым множествам, которым она принадлежит.

Итак, пусть построены все максимальные независимые множества графа (7 (пусть таких множеств /) и пусть задана (я х /^-матрица М= {ту}, у которой т^ = 1, если вершина V, принадлежиту'-му максимальному независимому множеству, и /л,у = 0 — в противном случае. Если теперь каждому максимальному независимому множеству сопоставить единичную стоимость, то задача раскраски сведется просто к задаче нахождения наименьшего числа столбцов в матрице М, покрывающих все ее строки V. Каждый столбец из решения этой задачи соответствует определенному цвету, который может быть использован для окраски всех вершин максимального независимого множества, представленного этим столбцом.

Задача 2.12. Найти с достаточным обоснованием точное значение хроматического числа графа (см. рис. 2.35, а) и предложить вариант раскраски.

Решение.

В соответствии с алгоритмом найдем все пустые подграфы: {2, 6}; {2, 7}; {1, 5}; {1, 4, 6}; {3, 2, 7}; {3, 4}; {5, 7}; {4, 3}. Составим матрицу покрытий (табл. 2.12).

Присвоим каждому пустому подграфу свой цвет. Запишем покрытие, используя логические операции (аналогично тому, как поступали при поиске внешне устойчивых множеств вершин). Для этого рассмотрим составленную матрицу по столбцам: 1-й столбец покрывается 3-й или 4-й строкой (это означает, что первую вершину можно окрасить в цвет с или б) 2-й столбец покрывается 1-й, 2-й или 5-й строкой (действительно, вторую вершину можно окрасить в цвет а, с или е) и т.д. Получим логическое выражение

  • + сі)(а + Ь + е) ? (е+/)(с!+/) • (с + $) • (я+ (Ь + е + §), (2.13) которое можно упростить, сначала перемножив соответственно 2-ю и 7-ю, 1-ю и 5-ю, 3-ю и 4-ю скобки:
  • + е + а ? g) ? (с + с! ? g) ? (/ + е ? с!) ? (а + сГ). (2.14)

Таблица 2.12

Матрица покрытий для графа на рис. 2.35, а

Вершины

1

2

3

4

5

6

7

Цвет

{2,6}

1

1

а

{2,7}

1

1

ь

{1,5}

1

1

С

{1,4,6}

1

1

1

СІ

{3,2,7}

1

1

1

е

{3,4}

1

1

/

{5,7}

1

1

?

Дальнейшее легкое упрощение невозможно и, строго говоря, если бы стояла задача найти все возможные способы покрытий, необходимо было бы раскрыть все скобки и провести окончательное упрощение. В нашем случае необходимо найти одно решение с минимальной мощностью. Например, в результате умножения получится слагаемое g? с1 ? е (из первой скобки е, из второй с1 ? g,ш третьей е ? с/, из четвертой с1), мощность которого равна трем. Это и есть точное значение хроматического числа. Соответствующая этому решению раскраска выглядит так: в цвет g (например, красный) красим вершины {5, 7}; в цвет с/ (синий) красим вершины {1, 4, 6}; в цвет е (зеленый), по идее, следует покрасить вершины {3, 2, 7}, но вершине 7 уже присвоен красный цвет, поэтому в множество зеленых вершин ее включать не будем.

Ответ. И = 3; раскраска: {5, 7} — красный цвет; {1,4,6} — синий; {3, 2} — зеленый.

Для больших графов точные алгоритмы точного поиска хроматического числа в силу своей трудоемкости (и, соответственно, медленной реализации на ЭВМ) могут оказаться неудобными. В этом случае применяются приближенные алгоритмы.

Введем понятие склеивания. Склеивание двух вершин У] и у2 с соответствующими множествами смежных вершин Г^) и Г(у2) состоит в устранении из графа вершин и у2 вместе с инцидентными им ребрами и добавлении новой вершины V и инцидентных ей ребер таким образом, чтобы Г(у) = Г(У]) и Г(у2). Результирующий граф б' имеет на одну вершину меньше, а также может иметь меньшее число ребер. Описанное преобразование графа позволяет построить эвристические алгоритмы раскраски. Вместо раскраски мы осуществляем последовательные преобразования графа (7, состоящие в «склеивании» несмежных вершин. Преобразования каждого очередного графа (7 продолжаются до тех пор, пока в нем не окажется ни одной пары несмежных вершин, т.е. пока (7 не окажется некоторым полным графом на к вершинах. Очевидно, что такой граф допускает только одну тривиальную раскраску: каждая из к вершин у красится своей краской, которая одновременно оказывается краской для всех вершин исходного графа, вклеенных в у. Поскольку все они попарно несмежны, такая раскраска оказывается допустимой, при этом количество вершин результирующего полного графа есть количество красок.

Задача получения минимальной раскраски становится задачей построения такой последовательности склеиваний вершин исходного графа, при которой количество вершин результирующего полного графа будет минимальным среди всех возможных. На основе этой идеологии можно непосредственно описать сам алгоритм, предложенный А.П. Ершовым, известный как алгоритм Ершова.

Напомним, что расстояние между вершинами определяется как длина минимального пути между ними. Назовем 1-окрестностью вершины у множество вершин на расстоянии единицы от у, ^-окрестностью вершины у — множество вершин на расстоянии р от у. Тогда реализация алгоритма сводится к набору шагов.

Шаг 1. Выбираем вершину и присваиваем ей первую краску. Выберем из 2-окрестности этой вершины любую вершину и присвоим ей ту же краску. Объединим эти две вершины в одну так, что все ребра, связывающие нераскрашенные вершины с этими вершинами, заменяются ребрами к этой объединенной вершине.

Шаг 2. Для полученного графа находим новую нераскрашенную вершину из 2-окресности, если таковая есть, красим ее в ту же краску и объединяем с объединенной вершиной.

Шаг 3. Такая процедура продолжается до тех пор, пока находятся нераскрашенные вершины в 2-окрестности объединенной вершины. Затем из числа нераскрашенных вершин выбирается новая вершина и для нее процедура раскраски повторяется, и так до тех пор, пока все вершины не будут раскрашены.

Алгоритм Ершова относится к так называемым эвристическим алгоритмам, построенным на основе некоторых разумных с точки зрения здравого смысла методах, для которых гарантий оптимальности нет. Можно привести примеры, когда решение имеет не минимальное количество красок.

Задача 2.13. С помощью алгоритма Ершова произвести раскраску графа (рис. 2.36, а) и оценить значение хроматического числа.

Решение.

Возьмем вершину 1 и присвоим ей цвет, например красный. Выберем из 2-окрестности этой вершины любую вершину (возьмем 3) и присвоим ей тот же красный цвет. Объединим эти две вершины в одну так, что все ребра, связывающие нераскрашенные вершины с этими вершинами, заменяются ребрами к этой объединенной вершине (рис. 2.36, б).

Выберем из 2-окрестности объединенной вершины 1&3 (вершина 1 объединена с вершиной 3) любую вершину (возьмем 8) и присвоим ей тот же красный цвет. Объединим эти две вершины в одну так, что все ребра, связывающие нераскрашенные вершины с этими вершинами, заменяются ребрами к этой объединенной вершине (рис. 2.36, в).

Выберем из 2-окрестности объединенной вершины 1&3&8 любую вершину (возьмем 12) и присвоим ей тот же красный цвет. Объединим эти две вершины в одну по аналогичному принципу (рис. 2.36, г). Больше в 2-окрестности объединенной вершины вершин не осталось (все с ней смежны, т.е. находятся в 1-окрестности).

Выберем как исходную любую нераскрашенную вершину, например 2, и присвоим ей другой цвет, допустим синий. Выберем из 2-окрестности этой вершины любую вершину (возьмем 4) и присвоим ей тот же синий цвет. Объединим эти две вершины в одну так, что все ребра, связывающие нераскрашенные вершины с этими вершинами, заменяются ребрами к этой объединенной вершине (рис. 2.36, д).

Выберем из 2-окрестности объединенной вершины 2&4 любую вершину (возьмем 10) и присвоим ей тот же синий цвет. Объединим эти две вершины в одну (рис. 2.36, е). Больше в 2-окрестности объединенной вершины вершин не осталось (все с ней смежны, т.е. находятся в 1-окрестности).

Продолжим процесс далее, возьмем вершину 6, окрасим ее в зеленый цвет, объединим с вершиной 5. На следующем шаге к объединенной вершине 6&5 добавится вершина 7 (рис. 2.36, ж). Результат следующей итерации (взятие новой вершины 9 в качестве исходной, присвоение ей цвета, например фиолетового, и объединение ее с вершиной 11) представлен на рис. 2.36, з.

Это уже финал алгоритма, так как получен полный граф (на четырех вершинах), следовательно, хроматическое число не превышает четырех.

Ответ. Хроматическое число графа не превышает четырех; возможная раскраска в четыре цвета: {1, 3, 8, 12} — красный; {2, 4, 10} — синий; {6, 5, 7} — зеленый; {9, 11} — фиолетовый.

В ряде случае вместо точных или эвристических алгоритмов можно воспользоваться различного рода свойствами, признаками и оценками.

Одной из наиболее полезных теорем при определении хроматического числа в рамках экзаменационных работ и в ряде практических случаев является следующая теорема.

Теорема 2.10

Хроматическое число графа равно двум тогда и только тогда, когда все имеющиеся в графе циклы содержат четное число ребер.

Если граф удалось раскрасить в два цвета и затем расположить вершины разных цветов в два яруса, то получим обычный двудольный граф. Отсюда следует, что во всех двудольных графах имеющиеся циклы обязательно четной длины. На основании сказанного выше можно сделать следующее обобщение.

Теорема 2.11

Хроматическое число, равное двум, имеют ациклические графы, содержащие хотя бы одно ребро, простые циклы на четном числе вершин и графы, содержащие только четные циклы.

Хотя изначально это может показаться неочевидным, но все указанные в теореме 2.9 типы графов по своей сути являются двудольными, точнее, имеют двудольное представление, если потребуется его изобразить. Этому могут быть посвящены отдельные задачи.

Задача 2.14. Определить, является ли граф (рис. 2.37, а) двудольным, и если да, построить его двудольное представление.

Решение.

В графе (см. рис. 2.37, а) все циклы имеют четную длину, следовательно, граф 2-раскрашиваемый (его хроматическое число равно двум). Это означает, что граф — двудольный. Для построения двудольного представления раскрасим граф в два цвета (разные штриховки на рис. 2.37, б). Теперь разместим все заштрихованные одним способом вершины в первой доле (вершины 1, 7, 3, 5, например имеющие красный цвет), а остальные вершины (2, 4, 6, 8, например имеющие синий цвет) — во второй доле.

Условие и этапы решения задачи 2.14

Рис. 2.37. Условие и этапы решения задачи 2.14

Теперь остается только провести ребра так, чтобы они соединяли смежные в исходном графе вершины. Например, из вершины 1 нужно провести ребра в вершины 2, 4, 6, 8. Далее достаточно рассмотреть 7, 3 и 5, т.е. вершины одной доли, в результате все ребра будут построены (рис. 2.37, в).

Ответ. Да, граф — двудольный, его двудольное представление построено.

Довольно много задач решается на основе теорем 2.8, 2.9. В остальных случаях приходится прибегать к различным способам оценки хроматического числа.

Снизу хроматическое число можно ограничить так называемым кликовым числом графа.

Клика графа — любой максимальный полный подграф. Иногда кликой называется произвольное подмножество вершин, в котором каждая пара различных вершин соединена ребром графа.

Кликовое число графа (7, обозначаемое как р((7) (густота или плотность), — максимальное число вершин в кликах данного графа.

Тогда чем более плотен граф, тем больше будет кликовое число:

/?((7) > р((7). (2.15)

Ограничение хроматического числа снизу кликовым числом графа представляется вполне логичным, ведь для раскраски клики графа потребуется число цветов, равное количеству вершин этой клики.

Оценку хроматического числа сверху можно произвести на основе теоремы Брукса.

Теорема 2.12. Теорема Брукса

Если наибольшая из степеней вершин нетривиального графа С равна 5тах, т0 этот граф зтах-раскрашиваем (т.е. его хроматическое число не превосходит 5тах) всегда, за исключением двух случаев:

  • 1) граф содержит полный подграф на 5тах + 1 вершине;
  • 2) 5тах = 2 и при этом данный граф содержит контур нечетной длины.

Совокупность таких оценок иногда позволяет определить точное или приблизительное значение хроматического числа без применения трудоемких алгоритмов.

Задача 2.15. Определить с достаточным обоснованием точное значение хроматического числа графа (рис. 2.38).

Решение.

Максимальная степень вершины 5тах = 3, граф — связный и не является полным; значит, по теореме Брукса он 3-раскрашиваемый, т.е. И < 3. Граф содержит контуры нечетной длины; значит, по теореме 2.10 его хроматическое число строго больше двух: И >2.

Так как И — натуральное число, совмещая данные ограничения, получим 2 < И < 3 и отсюда И = 3.

Ответ. И = 3.

В теории графов часто ставится вопрос о реберной раскраске графов. Какое минимальное число цветов нужно, чтобы раскрасить ребра графа так, что любые два смежных ребра (т.е. два ребра, имеющих общую вершину) были бы окрашены в разный цвет? Это минимальное число цветов называется хроматическим классом.

Дадим строгое определение. Граф б называется реберно к-раскрашиваемым, если его ребра можно раскрасить к красками та-ким образом, что никакие два смежных ребра не окажутся одного цвета. Если граф С реберно ^-раскрашиваем, но не является реберно - 1)-раскрашиваемым, то к называется хроматическим классом графа (7. При этом используется запись Н(Є) = к. На рис. 2.39 изображен граф (7, для которого //((7) = 4. Ясно, что если наибольшая из степеней вершин графа (7 равна 5тах, то //(С) > ?тах.

Граф, у которого хроматическое число равно четырем

Рис. 2.39. Граф, у которого хроматическое число равно четырем

Для хроматического класса графа справедлива гораздо более точная оценка, чем для хроматического числа, а именно верна следующая, в какой-то степени удивительная, теорема, известная как теорема Визинга.

Теорема 2.13. Теорема Визинга

Если в графе максимальная степень вершин равна хтах, то хроматический класс равен либо 5тах, либо 5тах + 1.

До сих пор нет хороших критериев для графов, позволяющих определить, когда же именно хроматический класс равен 5тах, а когда ^ + 1

Однако в некоторых частных случаях соответствующие результаты находятся легко. Например, хроматический класс простого цикла на п вершинах равен двум или трем в зависимости от того, четно п или нечетно. Хроматические классы полных двудольных и просто полных графов вычисляются в соответствии со следующими утверждениями.

Теорема 2.14

Для полных двудольных графов Н{КП )Ь) = р = тах(«1, п2).

Теорема 2.15

Для полных графов Н(Кп) = п, если п нечетно (пф),и Н(Кп) = п - 1, если п четно.

В заключение отметим, что реберная раскраска часто применяется при конструировании различных устройств, где провода, соединяющиеся в одном узле, должны для удобства иметь разные цвета.

Планарность графов

Существует несколько подходов к определению планарности. Наиболее общий подход основан на понятии геометрической реализации. Действительно, окружающий нас мир имеет как минимум три измерения, существуют разные геометрии, так что ограничиваться при построении теорий плоскостью довольно неосмотрительно.

Пусть задан неориентированный граф Є = (К, и). Пусть каждой вершине у, из Vсопоставлена точка я, в некотором евклидовом пространстве, причем а, Ф а і при і Ф у. Пусть каждому ребру и = (у,, уу) из и сопоставлена непрерывная кривая Ь, соединяющая точки а,? и а, и не проходящая через другие точки ак. Тогда если все кривые, сопоставленные ребрам графа, не имеют общих точек, кроме концевых, то это множество точек и кривых называется геометрической реализацией графа (7.

Теорема 2.16

Каждый конечный граф (7 можно геометрически реализовать в трехмерном евклидовом пространстве.

Граф называется планарным, если существует его геометрическая реализация на плоскости. Графы, уже реализованные на плоскости (изображенные без пересечения ребер), также называют плоскими.

Отсюда переходим к чрезвычайно важному понятию граней. Если имеется планарная реализация графа на плоскости и разрезать плоскость по всем линиям этой планарной реализации, то плоскость распадется на части, которые называются гранями этой планарной реализации (одна из граней бесконечна, она называется внешней).

Так, граф имеет четыре грани — три внутренних и одну внешнюю (рис. 2.40).

В свою очередь, граф куба (рис. 2.41) имеет шесть граней (пять внутренних и одну внешнюю). Внешнюю грань имеет всякий планарный граф, даже если в нем нет циклов.

Теорема 2.17. Формула Эйлера

Для любой планарной реализации связного планарного графа (7= (Г, и) сп вершинами, т ребрами и геранями выполняется равенство п-т + г-2.

Четыре грани у плоского графа К

Рис. 2.40. Четыре грани у плоского графа К4

Грани графа куба

Рис. 2.41. Грани графа куба: а — классическая реализация; 6 — плоская реализация

Формула Эйлера справедлива и для геометрической реализации связных графов на сфере.

Соотношение из теоремы 2.15 было найдено Эйлером в 1736 г. при изучении свойств выпуклых многогранников. Так, для любого выпуклого многогранника справедливо равенство п - т + г= 2, где п — число вершин; т — число ребер; г — число граней. Это соотношение справедливо и для других поверхностей с точностью до коэффициента, называемого эйлеровой характеристикой. Это — инвариант поверхности, для плоскости или сферы он равен двум.

Формула Эйлера позволяет достаточно легко доказать непланар-ность некоторых графов, например К5 и К3 3.

На непланарности этих двух графах основана широко известная в литературе теорема Понтрягина—Куратовского, которая дает необходимое и достаточное условие планарности графа. Для этого введем понятие стягивания.

Элементарным стягиванием называется такая процедура: берем ребро е (вместе с инцидентными ему вершинами, например V] и у2)

и «стягиваем» его, т.е. удаляем е и отождествляем V! и у2. Полученная при этом вершина инцидентна тем ребрам (отличным от с), которым первоначально были инцидентны V! или у2 (рис. 2.42).

Элементарное стягивание ребра е

Рис. 2.42. Элементарное стягивание ребра е: а — исходный; 6— полученный граф

Граф (7 называется стягиваемым к графу Н, если Н можно получить из (7 с помощью некоторой последовательности элементарных стягивании.

Теорема 2.18. Понтрягина—Куратовского

Граф планарен тогда и только тогда, когда он не содержит подграфов, стягиваемых в К5 или К3 3.

Есть и другие полезные утверждения, например следующая теорема.

Теорема 2.19

Для любого связного планарного графа без петель и кратных ребер выполняется неравенство т < 3(п - 2), где п = У; т = |?/|.

Это означает, что при большем числе ребер граф заведомо непланарен (обратное утверждение, кстати, неверно). Можно также доказать следующую теорему.

Теорема 2.20

Вершины любого планарного графа можно правильно раскрасить в не более чем пять цветов.

Однако существует гипотеза о том, что хроматическое число планарных графов меньше или равно четырем. Этой, гораздо более сложной, проблеме было посвящено огромное число математических работ. В конце концов удалось свести эту проблему к исследованию верности этой гипотезы для достаточно большого числа типов графов (порядка 30 тыс.), что и было сделано с помощью компьютеров в 1976 г. Изначально доказательство не было принято всеми математиками, поскольку его невозможно было проверить вручную. В дальнейшем оно получило более широкое признание, хотя у некоторых

долгое время оставались сомнения. На текущий момент проблема

четырех красок является одним из известнейших прецедентов неклассического доказательства в современной математике.

Вопросы и задания для самопроверки

  • 1. Какие графы можно однозначно задать с помощью матрицы смежности?
  • 2. Какие графы можно однозначно задать с помощью матрицы инциден-ций?
  • 3. Какие графы можно однозначно задать с помощью функционального представления?
  • 4. Сколько ребер содержит полный граф на девяти вершинах?
  • 5. Сколько ребер содержит регулярный граф степени пять на восьми вершинах?
  • 6. Сколько ребер содержит полный двудольных граф с долями 5 и 11?
  • 7. Сколько вершин и ребер имеет дополнение регулярного графа степени 5 на 12 вершинах?
  • 8. Сколько вершин и ребер имеет граф, полученный в результате сложения регулярного графа степени 3 на восьми вершинах и полного графа ЛГ9 (нет общих вершин)?
  • 9. Сколько вершин и ребер имеет граф, полученный в результате объединения регулярного графа степени 5 на десяти вершинах и полного графа КА (нет общих вершин)?
  • 10. Чему равно число компонент связности у дерева?
  • 11. Какое число компонент связности может быть у произвольного графа на десяти вершинах и девяти ребрах?
  • 12. Чему равно число компонент связности у графа, полученного в результате объединения полного графа на шести вершинах и простого цикла на восьми вершинах (нет общих вершин)?
  • 13. Какое минимальное число ребер имеет связный граф на 17 вершинах?
  • 14. Сколько компонент сильной связности у графа, полученного путем объединения двух ориентированных простых циклов, на десяти вершинах каждый (нет общих вершин)?
  • 15. Чему равно цикломатическое число полного графа на трех вершинах?
  • 16. Чему равно цикломатическое число простого цикла на 15 вершинах?
  • 17. Чему равно цикломатическое число регулярного графа степени 2 на 11 вершинах?
  • 18. Чему равно цикломатическое число дерева, у которого удалили одно ребро?
  • 19. У каких графов цикломатическое число всегда равно нулю?
  • 20. Чему равен копиклический ранг дерева на десяти вершинах?
  • 21. У каких графов копиклический ранг всегда равен нулю?
  • 22. Какое минимальное число ребер может иметь ациклический граф на 15 вершинах?
  • 23. Какое минимальное число ребер надо удалить из графа, являющегося деревом на восьми вершинах, чтобы он стал ациклическим?
  • 24. Какими должны быть степени всех вершин графа, чтобы в нем существовал эйлеров цикл?
  • 25. Является ли эйлеровым регулярный граф степени 3 на 12 вершинах?
  • 26. Является ли эйлеровым полный граф на 17 вершинах?
  • 27. Является ли гамильтоновым простой цикл на 17 вершинах?
  • 28. Может ли быть гамильтоновым несвязный граф?
  • 29. В каких графах всегда есть и совпадают эйлеров и гамильтонов циклы?
  • 30. Всегда ли есть гамильтонов и эйлеров циклы в полном графе?
  • 31. Чему равен диаметр полного графа на восьми вершинах?
  • 32. Чему равен диаметр пустого графа на пяти вершинах?
  • 33. Чему равен диаметр полного двудольного графа К5 9?
  • 34. Чему равен диаметр простого цикла на 15 вершинах?
  • 35. Чему равно число внешней вершинной устойчивости полного графа на семи вершинах?
  • 36. Чему равно число внешней вершинной устойчивости пустого графа на семи вершинах?
  • 37. Чему равно число внешней вершинной устойчивости простого цикла на семи вершинах?
  • 38. Чему равно число внутренней вершинной устойчивости простого цикла на девяти вершинах?
  • 39. Чему равно число внутренней вершинной устойчивости простого цикла на 31 вершине?
  • 40. Чему равно число внутренней вершинной устойчивости полного двудольного графа К49?
  • 41. У какого графа на 15 вершинах числа внутренней и внешней вершинной устойчивости совпадают и равны единице?
  • 42. Чему равно хроматическое число пустого графа на девяти вершинах?
  • 43. Чему равно хроматическое число полного графа на девяти вершинах?
  • 44. Чему равно хроматическое число простого цикла на девяти вершинах?
  • 45. У какого графа хроматическое число равно нулю?
  • 46. У какого графа хроматическое число равно единице?
  • 47. У какого графа на десяти вершинах хроматическое число равно десяти?
  • 48. Чему равно хроматическое число полного двудольного графа К4 9?
  • 49. Является ли планарным полный граф на четырех вершинах? Докажите.
  • 50. Является ли планарным полный двудольный граф К2 5? Докажите.
 
<<   СОДЕРЖАНИЕ   >>