64 лекции по математике кн2

64.2. Основные понятия в теории графов. В дальнейшем под записью G={V, E}будем понимать неориентированный граф или мультиграф, оговаривая при необходимости, какой именно граф имеется в виду. Пусть V ={v1,v2,...,vn} есть множество вершин графа. Две вершиныvi иv j на-

зываются смежными, если ребро (vi ,vj )принадлежит E. Ребро (vi ,vj )назы-

вается инцидентным вершинамvi иv j , а вершиныvi иv j , называются ин-

цидентными ребру (vi ,vj ). Если ребро является петлей, то оно считается

дважды инцидентной соответствующей вершине.

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

Рис. 64.4

Число ребер графаG={V, E}, инцидентных вершинеvi называется степенью вершины vi и обозначается d (vi ) .Для графов на рис. 64.2,а и рис. 64.2,в имеем:

а) d (v1 ) =5, d (v2 ) =6, d (v3 ) =3, d (v4 ) =3, d ( v5 )=3 ,

в) d (v1 ) =3, d (v2 ) =4, d (v3 ) =3, d (v4 ) =3, d (v5 )=3 ,

Так как каждое ребро инцидентно двум вершинам, то:

192

∙сумма степеней всех вершин графа является четным числом

иравно удвоенному числу ребер;

∙в любом графе число вершин с нечетными с тепенями является четным.

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

nвершинами степень каждой вершины равна (n-1), а т.к. каждое ребро соединяет две вершины, то:

∙в полном графе с nвершинами содержится n(n-1)/2 ребер.

ребро графа G = {V, E }с вершинами из множества V1 , является также реб-

Рис. 64.5

Графы на рис. 64.5 являются подграфами графа, изображенного на рис. 64.4,б, но только подграф на рис.64.5,аявляется пор ожденным множеством вершин {v1 , v2 , v3 , v4 }.

Пусть задан гра ф G = {V, E }с множеством его вершин V ={v1,v2 ,...,vn}.

Путь длины nв данн ом графе это последовательность вершин

L=vi1 ,vi2 ,vi3 ,...,vik ,vik+1 ,...,vin ,vin+1 ,

вкоторой вершины v ik и vik +1 (k=1,…, n) соединены ребром. Вершина vik

называется началом пути L, а вершина vik +1 называется концом пути L.

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

193

Рис. 64.6

Две вершины графа G = {V, E }называются связны ми, если существует путь L, их соеди няющий. Граф называется связны м, если любые две его вершины могут б ыть соединены путем. Существует расхожее высказывание, что упомянуты й выше «граф знакомств», в котор ом в качестве вершин выступают люди всей земли, является связным, и б олее того, что любые две вершины в нем могут быть соединены путем, длина которого, не превосходит шести.

В графе на рис.64.6 вершиныv1 и v10 связными не являются, т.к. от-

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

Если граф G несвязен, то множество его вершин V можно разбить на

называется компонен той связности графа G и, таким о бразом, считается, что граф Gсостоит из k компонент связности. Граф G на рис. 64.6 состоит из 2-х компонент связности. Первая компонента определяется подмножеством вершин {v1,v2,. ..,v8}, а вторая компонента определяется подмножест-

вом вершин {v9 ,v10}.

Ребро, после удаления которого компонента связности графа перестает быть связной, называется мостом. В графе на рис. 64.6 ребро(v4,v5 ) яв-

ляется мостом.

Внеориентированном графе:

∙путь, в котор ом нет повторяющихся ребер называ ется цепью;

∙цепь без повторяющихся вершин называется простой;

∙цепь, в котор ой совпадают концевые вершины, называется цик-

лом;

∙цикл, в котором нет повторяющихся вершин, кроме концевых, на-

зывается простым циклом, или контуром.

шины, однако, если путь L1 является цепью, то путь L2 цепью не является,

194

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

64.3. Эйлеровы графы. Пусть G={V, E}есть неориентированный граф. Цепь, соде ржащая все ребра графа, нaзывается эйлеровой цепью. Цикл, содержащ ий все ребра графа, называется эйл еровым циклом. Цикл L =ν1,ν3,ν5,ν2,ν4 ,ν1 в графе в) на рис. 64.6 является эйлеровым. Путь

L=ν5,ν2,ν3,ν4,ν5,ν1,ν2 в графе б) на рис. 64.6 является эйлеровой цепью.

После введенных определений вопрос Иммануила Канта относительно кенигсбергских мостов может быть сформулирован так: существует ли эйлеров цикл в граф е на рис.64.3,б?

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

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

Так как в графе кенингсбергских мостов (рис. 64.3,б) все вершины имеют нечетные сте пени, то из данной теоремы следует отрицательный ответ на вопрос Имм ануила Канта. Более того, эйлерова цепь в нем также отсутствует, т.к. он и меет 4 вершины с нечетными степен ями. Граф на рис. 64.7 с учетом пунктирного ребра содержит эйлеров цикл, а без учета пунктирного ребра содержит эйлерову цепь.

Рис. 64.7

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

195

эйлеровом графе найти эйлеров цикл; 3) в найденном эйлеровом цикле удалить дополнительное ребро.

Рассмотрим граф на рис. 64.7. После введения пунктирного ребра (v1,v5) граф становится эйлеровым. Начнем поиск эйлерова цикла с 1-ой вершины. На рис. 64.8 указана одна из возможных последовательностей прохождения его ребер. Искомый эйлеров цикл будет таким:

v1,v1,v2,v4,v3,v1,v5,v7,v8,v6,v5,v4,v1.

Заметим, что после 6-ого шага нельзя из вершины v5,идти в вершину v4, т.к. ребро (v4,v5) после удаления пройденных ребер стало мостом. Вычеркнув из полученного цикла ребро (v1,v5) и переставив начальный его кусок в конец, получаем искомую эйлерову цепь

v5,v7,v8,v6,v5,v4,v1,v1,v2,v4,v3,v1.

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

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

ли между элементами множеств V1 иV2 можно установить взаимно одно-

значное соответствие f , при котором пара (vi,vj) E1, тогда и только тогда, когда (f (vi), f(vj)) E2 , т.е. вершины vi и vj соединены ребром в графе

G1только в том случае, когда вершины f (vi) и f(vj) соединены ребром в графе G1. Иначе говоря, соответствие fсохраняет свойство пар вершин быть смежными.

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

196

Рис. 64.8

Непосредственно из определения следует, что все вершинно-реберные свойства изоморфных графов идентичны. Потому, если найдется свойство такого типа, которым обладает один граф и не обладает другой, то такие два графа являются неизоморфными. Так, сразу видно, что графы 64.8,в и 64.8,г на рис. 64.8 неизоморфны, т.к. в графе 64.8,в степени 4-х вершин равны 3, а в графе 64.8,г только две вершины имеют степени, равные 3. У графов 64.8 ,г и 64.8,д на этом рисунке наборы степеней всех вершин совпадают (у двух вершин степени равны 3 и у 4-х вершин степени равны). Однако эти графы также неизоморфны, иб о в графе на рис. 64.8,г имеется цикл д лины 3, а в графе на рис.64.8,д такого цикла нет.

Рис. 64.9

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

197

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

v1↔ u1↔ w1, v2↔ u3↔ w3, v3↔ u6↔ w5, v4↔ u5↔ w2, v5↔ u2↔ w4, v6↔ u4↔ w6

64.5. Деревья. Очень важным в теории графов является понятие дерева. Деревом назыв ается связный граф, не содержащ ий циклов. Графы G1 иG2на рис. 64.10 я вляются деревьями, а графыG3(ест ь цикл) иG4(не является связным) дере вьями не являются.

Рис. 64.10,а

Дерево обладает след ующими свойствами:

∙каждое дерево, состоящее из n вершин, содержит ровн о (n-1) ребро;

∙любые две верши ны дерева соединены ровно одной п ростой цепью;

∙каждое ребро дер ева является мостом.

Рис.64.10,б

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

Остовом связного графа G={V, E}называется п одграф, содержа-

щий все его вершин ы и являющийся деревом.

198

Рис. 64.11

Деревья, изображенные на рис. 64.11,б и рис. 64.1 1, в представляют собой два различных остова графа, изображенного на рис.64.11,а

Рис. 64.12,а

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

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

Рис. 64.12,б 199

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

Приведем без доказательства алгоритм Прима, решающий данную задачу. Пусть дан взвешенный граф G={V, E}, имеющий n вершин. Алгоритм Прима состоит в следующем. На первом шаге выбираем в графе G´ ребро минимального веса. Оно представляет собой дерев оD1 , состоящее из одного ребра. Далее среди ребер, соединяющих вершины дереваD1 с вершинами графа G´, которые не входят в D1, выбираем реб ро минимального веса и присоединяем его к дереву D1 . Получается дерево D2 , состоящее из двух ребер. Далее среди ребер, соединяющих вершины дереваD2 с верши-

нами графа G´, которые не входят в D2 ,выбираем ребро минимального веса и присоединяем его к дереву D2 . Получается дерев оD3 , состоящее из трех ребер.

Дерево Dn −1 , построенное в результате повторения описанной

процедуры (n-1) раз, будет являться остовом минимального веса.

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

(v3,v6), (v3,v10), (v3 ,v1), (v10,v8), (v8,v11),(v6,v4), (v4,v5), (v5,v9), (v1,v2),

Рис.64.13

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

200