2.1     Основные понятия теории графов и способы представления графов

Граф С - упорядоченная пара (V, Е), где V - множество и Е семейство неупорядоченных пар элементов из V. Элементы множества V называют­ся вершинами графа С, а элементы Е - его ребрами. Вершины а, Ь ребра {а, 6} £ Е называются его концами. Говорят, что ребро а = {а, 6} инци­дентно своим концам а и 6, а концы, в свою очередь, инцидентны ребруа. Граф С = (У, Е) называется простым, если V - конечное множество и семейство Е тоже является множеством, т.е. каждую пару вершин графа может соединять не более чем одно ребро. Часто рассматривают ориен­тированные графы С = (у,Е), представляющие собой пару (¥,Е), где V - некоторое множество, а Е - семейство упорядоченных пар элементов из V, т.е. Е - семейство элементов декартова квадрата V х V. При этом в ребре а = (а,Ь) £ Е вершину а называют началом, а Ь - концом ребра а и изображают следующим образом

Иногда рассматривают смешанные графы, которые имеют как ориенти­рованные, так и неориентированные ребра. Например, план города можно рассматривать как смешанный граф, в котором вершины - перекрестки, а ребра - улицы с односторонним или с двусторонним движением. Из определения графа следует, что допускаются ребра вида (а, а), называемые петлями (обычно, петля считается неориентированной), а также кратные ребра, соединяющие две вершины о>\ = (0,6)1, «2 = (0,6)2 :

Два графа 0\ = (У\,Е\) и 02 = (У^-Е^) назовем изоморфными, если существует биекция 1| на 12. <р ■ У\ —>■ У2, такая, что

{х, у} Є Е\ <^=> {<р(х), <р(у)} Є Е2 (если ребра ориентированы, то ориента­ция сохраняется). Если Є\ изоморфен Є2, то будем писать Є\ = Є2.

а

Ъ

Пример 1. Следующие графы являются изоморными

 

относительно биекции щ —>• Ъи г < 7.

Вершина, не инцидентная никакому ребру, называется изолированной. Граф, состоящий только из изолированных вершин называется нуль-графом и обозначается Еп, где п - число вершин. Граф, содержащий п вершин, в котором любые две различные вершины соединены одним ребром, на­зывается полным графом и обозначается Кп (граф К\ = Е1 называется тривиальным). Заметим также, что простой граф порядка п (т.е. содер­жащий п вершин) имеет не более С2 ребер. Число ребер простого графа называется его размером и обозначается ие(С).

Пример 2. Следующие "пространственные" графы допускают изоморф­ное изображение на плоскости:

і)

 

тетраэдроктаэдр

4)

додекаэдр

5)

 

икосаэдр

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

Утверждение 1.Пусть уе = уе{0) - число всех ребер графа Є = (V, Е). Тогда

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

Доказательство следует из того, что в сумме £ р(а) каждое ребро {а, 6} учитывается два раза.

Иногда число всех ребер графа Є обозначается символом е(Є).

Следствие 1. В однородном степени к конечном графе порядка п спра­ведливо равенство

к ■ п

уе =-.

2

В частности, если к - нечетное число, то число вершин является чет­ным.

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

Пример 3. Следующие графы имеют порядок не превосходящий 4 и размер 3:

 

Граф С = (V, Е') является подграфом графа С = (V, Е), если V С V я Е' С Е (в обозначении, С С б). Если подграф С содержит все ребра графа С, соединяющие любые две вершины из С, то он называется натянутым (или индуцированным) на V.

Пример 4. Рассмотрим граф

С = ({1,2,3,4,5,6}, {{1,2}, {1,4}, {1,6}, {2,5}, {3,4}, {3,6}, {4, 5}, {5,6}}).

1

 

4

Тогда нижеследующие графы С\ и С являются соответственно подгра­фом С и подграфом С, натянутым на {1,2,3,4,6} :

Подграф С, натянутый на множество V С У, обозначают С = С[V Если И' С У (С), то С \ И' = С[У \ IV] - подграф С, полученный из С вы­черкиванием всех верщин из \У и всех ребер, инцидентных этим вершинам. Аналогично, если Е' С Е(в), то С \ Е' = (У(С), Я(С) \ Е').

Задача 1. Доказать, что следующие графы не являются изоморфными

 

 

УКАЗАНИЕ. В первом графе есть последовательность инцидентных ре­бер, возвращающаяся к исходной вершине (цикл):

{1,2}, {2,3}, {3,4}, {4,8}, {8, 7}, {7,6}, {6, 5}, {5,1}.

Во втором графе такой последовательности нет.

Если имеется простой граф без петель Є = (V. Е). \С\ = п, то его мож­но дополнить до полного графа Кп, проведя недостающие ребра. Граф, образованный множеством вершин У(С) и вновь проведенными ребрами, называется дополнением Є и обозначается через О.

Пример 5.

 

 

Пусть Є = (У(С),Я(С)) и Н(У(Н),Е(Н)) - два графа. Назовем их объединением следующий граф:

С и Я = (У(С) и У(Я), Е{С) и Е(Н)).

Суммой Є + Я называется граф, полученный из Є и Я добавлением всех ребер, соединящих вершины из У (Є) с вершинами из У (Я). Граф называ­ется конечным, если число его ребер конечно. Т.е., если в конечном графеимеется бесконечное число вершин, то все они, за исключением конечного числа, являются изолированными. Система ребер графа = (У, Е)

Аща} = {{аіи аг2}> {_аІ2і aiz)i ■ ■ ■ і {_ais-ii ais}}i

где щ = а-ц. щв = <ij и {а,-,. Є Е, 1 < t < s — 1, at Є V называется

Путем (или Маршрутом), СОеДИНЯЮЩИМ ВерШИНЫ Щ и dj. Если щ = Oj, то

путь Аа.а. называется циклическим. Граф G называется связным, если для любых двух различных вершин щ и aj графа G существует путь, соединя­ющий эти вершины. Ясно, что каждый граф конечного порядка является объединением конечного числа связных непересекающихся (т.е. не имею­щих общих вершин) подграфов, называемых связными компонентами гра­фа.

Путь Аа.а., в котором каждое ребро встречается не более одного раза, называется цепью. Циклический путь, являющийся цепью, называется ци­клом. Цикл с концом а называется простым циклом: если а не является в нем промежуточной вершиной и никакие другие вершины не повторяют­ся. Аналогично, назовем нециклическую цепь простой цепью, если в ней никакая вершина не повторяется. Фигура S С R/3), состоящее из точек 61,62,... и кривых (отрезков), их соединяющих (в обозначении {hi,bj}; за­метим также, что никакая внутренняя точка кривой не является вершиной или внутренней точкой другой кривой), называется геометрической реали­зацией графа G = (У, Е), где У = {а\, а2, • • • }, если существуют биекции У на {61,... } и Е на {{6^, bj}} такие, что {6те., bTlj} О (щ, aj) тогда и только тогда, когда Ьщ о щ, bTlj о aj (т.е. S = G).

Утверждение 2. Каждый конечный граф G = (V,E) можно реализо­вать в

ДОКАЗАТЕЛЬСТВО. Без ограничения общности можно считать, что \G\ = п < оо. Возьмем прямую в и проведем через нее связку из т плоскостей, где т - число ребер G. Выберем на прямой п точек 61,..., Ьп и рассмотрим биекцию 6/ ^ а-,, і < п. где У = {а\,..., ап}. Каждому ребру

{щ, а,у} Є Е поставим в соответствие некоторую плоскость из пучка и в ней дугу окружности, соединяющую Ьі яЬу В результате получаем искомую геометрическую реализацию 5 нашего графа С в Ы^.

Вопрос о реализации произвольного конечного графа в К/2) является не простым, хотя и имеет полное решение (см. ниже теорему Понтрягина-Куратовского).

Задача 2. (о трех домах и трех колодцах)

А      В С

 

х    у г

На участке земли были построены три дома А, В, С к вырыты три колод­ца X, У, 2. От каждого из домов имелась тропа к каждому из трех колодцев. Спустя некоторое время обитатели домов А, В, С поссорились друг с дру­гом и решили проложить дорожки к колодцам Х,У^ так, чтобы по пути к колодцам им не приходилось встречаться друг с другом. Спрашивается, можно ли это сделать?

Попытки решить эту задачу приводят нас к убеждению, что это невоз­можно, хотя число точек пересечения ребер можно свести к 1:

 

Предположим, что наш граф допускает плоскую реализацию. Начертим на плоскости непересекающиеся ребра АХ, ВХ, У В, УС, С2, 2А :

 

А

Можно считать, что полученный замкнутый контур описывается непре­рывной кривой. Проводя непересекающиеся непрерывные линии АУ и BZ, можно считать, что одна из них лежит внутри контура, а вторая вне его. Но тогда дуга СХ обязательно пересечет одну из дуг. В доказательстве есть элементы интуитивности. Строгость достигается, если пользоваться теоремой Жордана:

Пусть К - непрерывная замкнутая линия на плоскости. Линия К де­лит плоскость на внешнюю и внутреннюю области так, что любая не­прерывная кривая, соединяющая любую точку внутренней области с не­которой точкой внешней области, пересекает К.

Другое доказательство основано на следующей теореме Л.Эйлера (1752), справедливой для любого конечного плоского связанного графа: 6 + г = р + 2, где 6 - порядок графа, р - число его ребер и г - число его граней.

В нашем графе 6 = 6, р = 9. Если бы граф был бы плоским, то г = 11 — 6 = 5. Обозначим через щ - число ^-угольных граней графа. Тогда г = <Р2 +    + • • • и 2р = 2(^2 + 3(^з + ..., так как каждое ребро принадлежит двум граням. Следовательно,

5 = Ц>2 + <Рз + • • •

2р 18 = 2(р2 + З^з + • • • •

Так как <^2 = <£>з = 0, то

5 = (р4 + (р5 + . . .

18

4(р4 + 5(^5 + 6(^6 + • • •

20 = 4(^4 + 4(^5 + 4(^6 + • • • •

Откуда следует, что 18 > 20. Противоречие.

Задача 3. Доказать, что полный граф К5 не является плоским.

 

РЕШЕНИЕ. Действительно, допустив противное, имеем

6 = 5, р = К), г = р + 2 — 6 = 7.

Следовательно,

7 = <Р2 + <^3 + • • • ,

20 = 2<р2 + З^з + ••• •

Так как <^2 = 0, то 21 = 3<^з + 3^| + 3^.-, + • • • > 20 = 3<^з + 4щ + 5<^5 + .... Противоречие.

Задача 4. Каждый из 4-х соседей соединил свой дом с тремя другими домами при помощи непересекающихся дорожек.

 

Пятый человек построил свой дом поблизости. Доказать, что его нельзя соединить с другими домами непересекающимися дорожками. УКАЗАНИЕ 1. Воспользоваться теоремой Жордана. УКАЗАНИЕ 2. Воспользоваться теоремой Эйлера.

Имеем 6 = 5, р = К). г = р + 2 — 6 = 7. Далее рассуждаем аналогично решению задачи 2.

Двудольные графы

Граф С = (V. Е) называется двудольным, если У = V') и 1-2- V') П I = = 0 и каждое ребро соединяет какую-нибудь вершину из У\ с какой-либо вершиной из 12- Например,

 

Если двудольный граф является простым и каждая вершина из У\ со­единена с каждой вершиной из У2, то он называется полным двудольным и обозначается Кт,п, где т = \У\\.п = |1*2|. Ясно, что Кт,п = Е"' + Е". Граф К\р называется звездным.

Пример 6.

 

Пример 7. Граф, возникающий в задаче о трех колодцах, изоморфен Яз,з.

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

ДОКАЗАТЕЛЬСТВО. Пусть граф уложен на поверхности сферы. Вы­берем точку М на сфере, не совпадающей ни с одной вершиной графа и не лежащей ни на одном его ребре. Плоское представление графа полу­чается применением стереографической проекции из т. М на плоскость, диаметрально противоположную точке М.

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

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

Пример 8. Графы

 

являются гомеоморфными.

Утверждение 4 (теорема Понтрягина-Куратовского).

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

Замечание. Л.С.Понтрягин доказал ее в 1927 г., но не опубликовал; К.Куратовский доказал ее независимо в 1930 г.

ДОКАЗАТЕЛЬСТВО см. в [22].

Задача 5. Доказать, что регулярный граф Петерсена

 

не является план арным.

УКАЗАНИЕ. Если а = {а,Ь} Є Е(Є), то операция удаления ребра а в Є и отождествление вершин а и 6 называется стягиванием. Справедлива теорема о том, что граф является планарным тогда и только тогда, когда

ОТВЕТЫ:

/ 0 1 1 1 \ 10 11 110 1

\1 1 1 о/

V

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

Матрицей смежности графа С = (У, Е) называется матрица А = (а^ размера п х п, в которой ац равно числу ребер, соединяющих вершину у, с у^ где V = {т-\, • • • •<'„}•

Задача 6.

а) Построить матрицы смежности графов: К4, К^^-

I 0 0 0 1 1 \

0 0 0 1 1 0 0 0 1 1 1110 0 1110 0

б) Пусть Сп - граф с множеством вершин {у\,..., уп}: в котором у^ и у у ин­цидентны о (г, ]) = 1. Изобразить ^4, Се и найти их матрицы смежности. Доказать, что если т < п, то Сто - подграф О,,.

Задача 7. Пусть С - простой конечный граф (т.е. в нем нет петель и кратных ребер). Тогда С содержит две вершины с одинаковыми степенями (п= \в\ > 2).

УКАЗАНИЕ. Достаточно считать, что граф является связным. Пусть V = {у\,..., уп}. Если 1 < р{у\) < р{У2) ■ ■ ■ < р(щ), то из неравенств р{у%) < п — 1, г <п — 1 и принципа Дирихле следует, что найдутся а, /3 < п такие, что

РМ = рМ, {а ф /3).

Задача 8. Докажите, что среди 6 человек всегда найдутся трое таких, которые либо попарно знакомы, либо ни один из них не знает двух других. Задача 9. Приведите примеры (когда это возможно):

а) двудольного регулярного графа;

б) кубического графа порядка 9;

в) Платонова двудольного графа;г) простого графа порядка п, имеющего (п — 1)(п — 1)/2 ребер. ОТВЕТ на вопрос г): Кп~1 и Е1.

Замечание. При решении задач полезно иметь в виду следующее изо­бражение графа Яз5з : д

В предыдущем параграфе мы сформулировали теорему Эйлера для плос­ких связных графов и убедились в ее важности. Прежде чем строго фор­мулировать теорему, определим понятие грани графа С = (У,Е). Пусть х - точка плоскости, не принадлежащая V и не лежащая ни на одном ребре Е. Грань графа Є, содержащая х, это множество таких точек плоскости, которые можно соединить с х жордановыми кривыми, целиком состоящи­ми из точек, не принадлежащих V и ребрам графа. Одна грань в графе является неограниченной.

Теорема. (Эйлер Л., 1752) Пусть С - плоский связный граф; пусть Ъ =       р = у(Є), г - число граней С Тогда р + 2 = Ъ + г.

ДОКАЗАТЕЛЬСТВО. Доказательство проведем индукцией по р. Если р = 0, то 6 = 1 и г = 1. Теорема доказана. Предположим, что теорема верна для графов с числом ребер < р — 1. Рассмотрим плоский граф Є с у (Є) = р. Если он содержит петлю

то ее удаление уменьшает число ребер на 1 и число граней тоже   на 1, т.е.