Теория графов

23

Теория графов

1. Из истории теории графов

Родоначальником теории графов является Леонард Эйлер (1707 - 1782).

В 1736 году Эйлер решил задачу о Кенигсбергских мостах. Задача состояла в следующем: «Найти маршрут прохождения всех четырех участков суши (см. рис.), который бы начинался на любом из них, кончался на этом же участке и ровно один раз проходил по каждому из них.»

Река Преголь

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

23

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

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

В 1857 году Келли открыл важный класс графа - деревья. Он стремился перечислить число изомерных предельных углеводородов СnH2n+2

В 1869 Жордан независимо от Келли ввел и изучал деревья, как отдельные математические объекты. С того времени можно считать, что теория графов возникла как самостоятельная математическая дисциплина.

2. Основные понятия теории графов

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

На этих диаграммах ни расположение точек на рисунке, ни форма и длина линий не играют никакой роли. Существенно лишь, какие именно пары точек соединены линиями. Такие диаграммы описывают связь между элементами системы. Так, например, диаграммы в, г и г' представляют собой одну и ту же структуру связи между элементами A, B, C, D, E: (A, B), (B, C), (C, D), (D, E), (E, A), (D, B). В данном случае пары неупорядоченные, поскольку порядок элементов в них не важен (в противном случае они бы назывались упорядоченными). Пары элементов, а также рисунки в, г и г' обозначают один и тот же математический объект. Одинаковые структуры связи между элементами описывают также диаграммы д и е; ж, з и к.

Определение 2.1. Графом G называется пара множеств V и E (G = (V, E)), где V не пустое множество, а Е - некоторое множество пар элементов множества V (E = {(Vi, Vj)}, i = 1, 2, 3, …, n, j = 1, 2, 3, …, n, i j, где n - число вершин графа).

Определение 2.2. Элементы множества V называются вершинами, а элементы Е - ребрами.

Пример: На диаграмме в: V = {A, B, C, D, E}, E = {(A, B), (B, C), (C, D), (D, E), (E, A), (D, B)}.

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

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

Определение 2.5. Число вершин, смежных с данной вершиной U, называются степенью этой вершины. Если степень вершины равна нулю, то такая вершина называется изолированной.

Определение 2.6. Граф называется конечным, если множество его вершин конечно, то есть множество V конечно.

Определение 2.7. Граф с p вершинами и q ребрами называется (p, q)-граф.

Пример: (1, 0) - тривиальный граф.

Определение 2.8. Граф G' = (V', E') называется подграфом графа G, если V' V, E' E.

Геометрическая интерпретация графа (диаграмма)

23

Смежные вершины: U и V, U и W.

Инцидентность: U инцидентно ребру x, V инцидентно ребру y, V инцидентно ребру z, W инцидентно ребру z.

Смежные ребра: x и y, y и z.

Степень: degV = 3.

3. Виды графов

Существуют различные виды графов:

Определение 2.9. Граф называется неориентированным, если все его ребра являются неупорядоченными парами его вершин, и ориентированным, если его ребра - упорядоченные пары вершин.

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

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

Будем рассматривать конечные неориентированные графы без петель.

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

Определение 2.13. Последовательность ребер = {(V0, V1), (V1, V2), …, (Vn-1, Vn)} называется путем, соединяющим V0 и Vn. Длиной пути называется число ребер в такой плоскости.

Пример:

(1, 2), (2, 3), (3, 4) - путь, соединяющий вершины 1 и 4. Его длина равна 3.

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

Определение 2.15. Путь называется замкнутым, если он начинается и заканчивается в одной и той же вершине (v0 = vn).

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

Пример:

23

Циклы:

1) (1, 2), (2, 3), (3, 1).

2) (5, 4), (4, 3), (3, 5).

3) (1, 3), (3, 4), (4, 5), (5, 3), (3, 2), (2, 1).

(1-й и 3-й циклы различаются только длиной пути)

Определение 2.17. Цикл называется простым, если он более одного раза не проходит через одну и ту же вершину, то есть v0, …, vn-1 - различные.

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

Примеры:

Граф G1 не связанный, так как 5 - изолированная вершина.

Граф G2 не связанный, так как не существует путей, соединяющих (3, 4).

Свойства путей и циклов:

Если в графе имеется путь, соединяющий вершины a и b, то в нем имеется простой путь, соединяющий эти вершины.

Пример:

Путь: (1, 2, 3, 4, 2, 5). Простой путь: (1, 2, 5).

Доказательство: Пусть в графе существует путь = {(v0, v1), (v1, v2), …, (vi-1, vi), (vi, vi+1), …, (vj-1, vj), (vj, vj+1), …, (vn-1, vn)}, который соединяет вершины a=v0 и b=vn. Вообще говоря, этот путь может и не быть простым. Так, если vi = vj, то - непростой путь. Удалим в нем участок от (vi, vi+1) до (vj-1, vj) включительно. Тогда образуется новая последовательность вершин, которая будет путем, так как vi = vj. Этот путь будет простым, поскольку он ни по одному ребру не проходит более одного раза, что и требовалось доказать.

Если в графе имеется цикл, проходящий через ребро (a, b), то в нем есть и простой цикл, проходящий через это ребро.

Доказательство: Рассмотрим путь ={(v0, v1), (v1, v2), …, (vn-1, vn)}, соединяющий вершины a=v0 и b=vn. Если он непростой, то сделаем его простым по алгоритму, использованному при доказательстве первого свойства. В результате получим простой путь 1 от вершины a=v0 до b=vn. Сделаем из него цикл, дополнив ребром (vn, v0). Таким образом, получился цикл, являющийся простым, поскольку он образован из простого пути.

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

Доказательство: Возьмем самый длинный простой путь, который имеется в данном графе: ={(v0, v1), (v1, v2), …, (vn-1, vn)}. Из условия следует, что в этом графе, кроме вершины vn-1, есть еще, по крайней мере, одна вершина, смежная с вершиной vn. Назовем ее w. Возможны 2 ситуации: w=vi (i = 0, 1, 2,…, n-2) или w=vj (j>n). При реализации второго случая возникает противоречие с тем, что изначально был выбран самый длинный простой путь. Значит, имеет место первая ситуация, т.е. в графе есть цикл.

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

Задание списка вершин и ребер. G = (V, E)

Геометрическая интерпретация (графический способ).

Матричный.

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

а) Матрица смежности

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

Пример:

Определение 2.20. Матрицей смежности конечного графа G (A(G) = ||Vij|| (i, j = 1, 2, …, p)) с p вершинами называется матрица размером p p, в которой:

б) Матрица инцидентности

Обозначается: I(G) = (bij), где i = 1,2, …, p, а j = 1, 2, …, q, где p - число вершин, q - число ребер.

Определение 2.21. Матрицей инцидентности графа G с p вершинами и q ребрами называется p p матрица, в которой:

Пример:



Заметим, что deg vi равна числу единиц в i-ой строке или i-ом столбце матрицы смежности.

Заметим, что:

Каждый столбец матрицы I(G) содержит ровно две единицы и никакие две строки не идентичны.

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

Число единиц в i-ой строке равно степени вершины Vi.

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

в) Матрица векторов смежности

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

Пример: (х1: (1, 2), х2: (2, 3), х3: (3, 4), х4: (4, 5), х5: (5, 1), х6: (1, 3), х7: (3, 5)).

Размер этой матрицы никогда не превышает p d, где d = .

Матрицей векторов смежности особенно удобно пользоваться при решении задачи с небольшим числом просмотров каждого ребра графа G.

5. Характеристики вершин

Степень вершины - число ребер, инцидентных данной вершине.

Определение 2.22. Если степень вершины равна единице, то такую вершину называют висячей (концевой, тупиковой).

Пример:

(V1 - висячая, V6 - изолированная).

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

Основная теорема теории графов. Сумма степеней вершин графа G равна удвоенному числу его ребер ( = 2q). (Теорема доказана изложенными выше рассуждениями).

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

Доказательство: Пусть V1 V - множество вершин с нечетными степенями, V2 V - множество вершин с четными степенями. Множество всех вершин рассматриваемого графа - V =V1 V2, V1 V2 = . По основной теореме теории графов =2q - четное число. Кроме того, и = 2k - четное число. Следовательно, =2(p-k) также является четным числом.

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

Степень вершины: 0? deg v ? p-1, для любой вершины v.

Определение 2.23. Пусть , (G) =. Если в графе G, G = G = r, то все вершины имеют одинаковую степень и такой граф называется регулярным или однородным степени r, то есть deg G = r.

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

Пример:

 - полный граф из 4-х вершин.

Заметим, что:

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

Для задания полного графа достаточно знать число его вершин.

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

Пример:

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

Определение 2.26. Две вершины в графе дополнения к G являются смежными тогда и только тогда, когда они несмежные в графе G.

В полном графе каждая пара вершин смежная. Отсюда следует, что любой полный граф является регулярным с p вершинами (при этом deg Kp = p-1). Но далеко не каждый регулярный граф является полным.

Пример:

(полный граф, а следовательно, регулярный)

 (регулярный, но не полный)

Регулярный граф степени ноль совсем не имеет ребер.

Определение 2.27. Если граф G - регулярный граф степени 3, то он называется кубическим.

Пример:

deg G1 = deg G2 = 3.

Каждый кубический граф имеет кубическое число вершин.

Планарный граф

Определение 2.28. Изображение графа называется правильным (плоским), если линии, изображающие его ребра, не пересекаются.

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

Пример:

(планарный граф)

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

Определение 2.31. Имеется одна неограниченная грань, называемая внешней, все остальные грани называются внутренними.

Пример:

f5 - внешняя грань.

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

Теорема о количестве граней связанного планарного графа.

Пусть G - связанный планарный граф с p вершинами и q ребрами. Число граней в любом его плоском изображении равно r=q-p+2 - формула Эйлера (*).

Доказательство (метод математической индукции по числу ребер):

q=0 p=1 r=1=0-1+2 (*) верно при q=0

Допустим, что формула (*) справедлива для графа с q-1 ребром.

а) Пусть в графе с q ребрами есть хотя бы одна тупиковая вершина. Удалим эту вершину. Удаляется и ребро, соединенное с этой вершиной. Получим граф G' с q'=q-1 ребрами и p'=p-1 вершинами. Тогда число граней r'=r, но при этом формула r'=q'-p'+2 - верна по допущению. Значит r=q-1-(p-1)+2=q-p+2 (*) истинна и для графа G c q ребрами и с хотя бы одной тупиковой вершиной.



б) Пусть в графе G с q ребрами нет ни одной тупиковой вершина, а значит - каждая вершина имеет как минимум степень 2. По свойству 3 путей и циклов в этом графе есть цикл. Пусть (a, b) - ребро из этого цикла. На диаграмме, изображающей граф G, ребро (a, b) лежит на границе двух областей (f1 и f2). Удалим ребро (a, b). Получим граф G'', у которого p''=p, q''=q-1, r''=r-1. По допущению справедлива формула r''=q''-p''+2 r-1=q-1-p+2, то есть (*) верно и для графа G с q ребрами, у которого нет тупиковой вершины.

В пунктах (а) и (б) мы доказали, что равенство (*) справедливо для любого графа G.

Так как выполнено оба условия обобщенного принципа математической индукции, то (*) выполняется для любого графа G.

Следствия:

Если связанный планарный граф G имеет p вершин (p 3) и q ребер, то q?3(p-2).

Если граф G к тому же еще и содержит цикл длины 3, то q?2(p-2).

Доказательство:

1) Пусть r - число граней в плоском изображении графа G. Тогда r=q-p+2. Пронумеруем грани натуральными числами от 1 до n. Обозначим через ai число ребер, принадлежащих границе грани c номером i. Так как каждое ребро принадлежит границе не более двух граней, то . С другой стороны, при p3 граница каждой грани имеет не менее трех ребер, т.е. для любого i ai 3 и, следовательно, . Таким образом, мы получили, что , 3r ? 2q 3(q-p+2) ? 2q q?3(p-2), что и требовалось доказать.

2) Если граф G не содержит цикл длины 3, то граница всякой грани имеет не менее 4 ребер, т.е. для любого i ai 4, то . Таким образом, 4r?2q 4(q-p+2)?2q q?2(p-2), что и требовалось доказать.

Пример: Является ли планарным граф K5?

p = 5, q = 10. q ? 3(p - 2) 10 ? 33 - неверно. Следовательно, граф K5 не планарный.

Эйлеровы графы

Определение 2.32. Цикл, содержащий все ребра графа, называется эйлеровым циклом.

Определение 2.33. Граф, содержащий эйлеровы циклы, называется эйлеровым графом.

Пример:

- эйлеровый граф - не эйлеровый граф

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

Пример:



Теорема Эйлера об эйлеровых графах (критерий эйлеровости графа)

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

Доказательство: См. [2], стр. 106 - 107.

Задача о Кенигсбергских мостах

- это не эйлеров граф, так как все его вершины имеют нечетную степень.

6. Изоморфизм графов

Определение 2.34. Два графа: G и H - изоморфные (G H), если между множествами их вершин существует взаимно-однозначное отображение, сохраняющее смежность.

Определение 2.35. Два графа G = (V, X) и H = (W, Y) называются изоморфными, если существует взаимно-однозначное отображение : V W, сохраняющее смежность, такое, что для вершин u, V ((u), ())Y (u, )X. В этом случае отображение называют изоморфизмом.

Пример:

: (Ui Wi), i = 1, 2, 3, 4 - не изоморфизм.

: (U1 W2, U2 W3, U3 W4, U4 W1) - изоморфизм

Определение 2.36. Граф G, в котором выделена некоторая вершина V, называется корневым, а эта вершина - корень графа G. При изоморфизме корневых графов корню должен соответствовать корень.

Инварианты

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

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

Определение 2.37. Компонентой связности графа G называется его максимальный связный подграф.

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

Пример:

- 5 компонент связности.

Таким образом, несвязный граф имеет как минимум 2 вершины.

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

Пример:

p = 1

p = 2

p = 3

Множество вершин - полный инвариант.

Пример: p = 4, q = 3.

- не изоморфны

Алгоритм решения задач изоморфизма:

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

2. Последовательно сравнивают значения инвариантов.

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

3а. если есть несовпадающие инварианты, то графы неизоморфны.

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

Число графов с p вершинами (g(p))

Теорема (О числе графов с p вершинами):



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

способами. По теореме о мощности множества всех подмножеств данного множества всего имеется графов.

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

.

Пример: g(3) = 23 = 8, но существует всего 4 неизоморфных между собой графов с 3 вершинами.

7. Деревья. Лес

Определение 2.39. Граф называется ациклическим, если в нем нет циклов.

Определение 2.40. Деревом называется связный ациклический граф.

Определение 2.41. Каждый граф, не содержащий циклов, называется лесом.

Примеры:

дерево

Вывод: Таким образом, компонентами леса являются деревья.

Теорема о количестве ребер дерева

В дереве с p вершинами число ребер равно p-1, то есть q=p-1 (*).

Доказательство (методом математической индукции):

p=1 q=0 (*) истинно при p=1.

Допустим, что равенство (*) верно и для графа с p-1 вершиной, то есть допустим, что q=p-2. Докажем что (*) справедлива и для дерева с p вершинами. Поскольку дерево - ациклический граф, то в нем есть хотя бы одна вершина тупиковая вершина. Удалим ее. Получится граф с p-1 вершиной. По допущению, у такого дерева p-2 ребра. Рассматриваемый граф с p вершинами отличается от полученного графа с p-1 вершиной наличием лишнего ребра. Значит, у графа с p вершинами ребер на единицу больше, чем p-2, то есть q=p-1.

Вывод: Так как выполнено оба условия обобщенного принципа математической индукции, то (*) выполняется для любого дерева.

Пример дерева с выделенным корнем:



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

Выпишем все нули и единицы: 000010110010111010011101 - такая последовательность называется кодом дерева. В ней содержится одинаковое число единиц и нулей, равное числу ребер. Код задает дерево однозначно, поэтому с помощью кода дерево удобно представлять в ЭВМ.