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

1. Дискретная математика

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

2.

Впервые понятие «граф» ввел в 1936 г.
венгерский математик Денни Кёниг. Но первая
работа по теории графов принадлежала перу
великого Леонарда Эйлера и была написана
еще в 1736 г.
С помощью графов изображаются схемы
различных дорог, линии воздушных сообщений,
газопроводов, теплотрасс, электросетей, а
также микросхемы, дискретные многошаговые
процессы, системы различных бинарных
отношений, химические структурные формулы
и другие диаграммы и схемы.
Без
графов
сложно
анализировать
классификации в различных науках.

3.

Графы
Леонард Эйлер
(1707 – 1783)
Задача
о кенигсбергских мостах
3

4.

Граф – совокупность двух множеств G = <V, E>, где V – конечное
множество вершин, а E V V – множество ребер с заданным на нем
отношением инцидентности Р – «каждое ребро е инцидентно ровно
двум вершинам v1 и v2 , которые оно соединяет».
Если в графе нет дуг (ребра называются звеньями), то
граф называется неориентированным (н-графом),
если все ребра – дуги, то граф – ориентированный
(ор-граф).
Ребро, концевые вершины которого совпадают, называется
петлей.
Если в графе ребра разного типа, то граф – смешанный.
4

5.

Ориентированный граф (орграф)
- это граф, у которого на линиях,
соединяющих вершины, указано
направление (соединяющие линии
называются дугами)

6.

Если все пары (Vi ,Vj) во множестве X являются
упорядоченными, т.е. кортежами длины 2, то
граф
называется
ориентированным,
орграфом, или направленным.
В таком случае ребра принято изображать
стрелками.

7.

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

8.

Неориентированный граф
Ориентированный граф
Смешанный граф

9.

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

10.

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

11.

Определение.
Вершина графа, не принадлежащая ни одному ребру
называется изолированной.
Пример.
Вершина 5 является
изолированной.
Задание.
Вершины графа представляют жителей городка N, а ребра,
соединяющие две вершины, - тот факт, что эти люди
знакомы. Какую ситуацию изображает приведенный на
рисунке граф?

12.

Определение.
Вершина А графа Г, принадлежащая одному
ребру, называется висячей.
Пример
Вершины А и Б - висячие.
Задание
Укажите висячие вершины.
Есть ли здесь изолированные вершины?
Задание
Начертите граф, содержащий шесть висячих и две
изолированные вершины.

13.

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

14.

Примеры графов:
со смежными вершинами
полный

15.

Примеры графов:
со смежными ребрами
с петлей

16.

Записать:
смежные вершины:
смежные ребра:

17.

Граф G ( V, X) может иметь ребра с
одинаковыми парами вида X(V, W). Такие ребра
называются кратными, или параллельными.
На рис. кратными являются , например,
ребра х1(А,В) и х2(А,В).
Вершинам А и В инцидентны
ребра х1, х2. Количество
одинаковых пар вида х(V,W)
называется кратностью ребра (К, W).
На рис. ребро АС имеет кратность, равную 3, а
ребро АВ — кратность, равную 2.

18.

Дуги орграфа называются кратными, если они
имеют одинаковые начальные и конечные
вершины,
т.е.
одинаковые
направления.
Например, кратны дуги u(V2, V3) и t(V2, V3)

19.

Простой граф – это н-граф без петель
и без кратных ребер.
Турнир – ор-граф, в котором каждая
пара вершин соединена одним ребром.
Мультиграф - это граф с кратными
ребрами (без петель).
Псевдограф — это мультиграф,
допускающий наличие петель
мультичисло – наибольшее
число кратных ребер
Граф Бержа- ор-граф без кратных петель и
кратных дуг одного направления

20. Полный граф. Дополнение графа

Граф называется полным, если каждые две различные
вершины его соединены одним и только одним ребром (рис. 3).
В полном графе каждая его вершина принадлежит одному и тому же
числу рёбер. Для задания полного графа достаточно знать число его
вершин.
Граф, не являющийся полным, можно преобразовать в полный с
теми же вершинами, добавив недостающие рёбра. Например, граф Г на
рисунке 4 неполный. Проведя недостающие рёбра (для удобства их
можно выделить др. цветом или др. типом линии), получаем полный граф
с пятью вершинами (рис.5 а).
а)
Г:
Рис. 3
б)
Г':
Рис. 4
Рис. 5

21. Дополнение графа

Вершины графа Г и рёбра, которые добавлены, тоже
образуют граф. Он приведён на рисунке 5 (б). Такой граф
называют дополнением графа Г и обозначают его Г’.
Дополнением графа Г называется граф Г’ с теми же
вершинами, что и граф Г, и с теми и только теми
рёбрами, которые необходимо добавить к графу Г,
чтобы получился полный граф.
а)
Г:
Рис. 3
б)
Г':
Рис. 4
Рис. 5

22.

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

23.

Степени и инцидентность
Говорят, что если задана дуга (ребро) e = <v1, v2>, то такую дугу (ребро)
называют инцидентной вершинам v1 и v2, а вершины, соответственно,
инцидентными дуге (ребру) e.
Полустепень исхода ps(v) – количество дуг, инцидентных вершине v и
исходящих из нее.
Полустепень захода pd(v) – количество дуг, инцидентных вершине v и
входящих в нее.
Степенью вершины p(v) называется сумма полустепеней исхода и захода
p(v) = ps(v) + pd(v),
В неориентированном графе ребра, вообще говоря, считаются один раз (то есть
степенью вершины называется число ребер, инцидентных вершине), но
степень петли считается два раза (один раз как «исходящее» ребро, а
другой раз – как «входящее».
23

24.

Число ребер, инцидентных вершине А,
называется степенью этой вершины и
обозначается deg(A) (от англ. degree —
степень).
Если вершине инцидентна петля, она дает
вклад в степень, равный двум, так как оба
конца приходят в эту вершину.
На рис. вершина А имеет степень,
равную 1, вершина С-4,вершина D-2.
Записывается это в виде:
deg (A) = 1, deg (С) = 4,
deg (D) = 2.

25.

Граф G4 содержит четыре вершины:
V= (A,В, С, D)
и шесть ребер Х= {р, q, r, s, t, и}.
Записать, чему равна
степень вершин:
deg (A) =
deg (В) =
deg (С) =
deg (D) =

26.

Вершина графа, имеющая степень, равную
нулю, называется изолированной.
Граф, состоящий из изолированных вершин,
называется нуль-графом. Для нуль-графа Х= 0.
Вершина графа, имеющая степень, равную 1,
называется висячей.
На рисунке:
вершины А, В, Е, G, Н
— висячие,
вершина N – изолированная
deg (N) = 0
N

27.

Граф G называется полным, если любые две
его различные вершины соединены одним и
только одним ребром.
Таким образом, полный граф
определяется только своими
вершинами.
Пусть число вершин полного
графа n. Тогда степень любой вершины,
очевидно, равна deg( V) = n - 1, а число ребер
равно числу сочетаний из n по 2, т.е.

28.

29.

Набор степеней графа – это
последовательность степеней его вершин в
неубывающем порядке.
Вершина называется четной (нечетной), если
ее степень число четное (нечетное).
Если все вершины имеют одинаковую степень
k, то граф называется.
k-регулярным.
Исток- вершина ор-графа, у которой
полустепень захода равна 0.
Сток- вершина ор-графа, у которой
полустепень исхода равна 0.

30.

(1) 3
(2 ) 2
(3) 2
( 4) 3
(5) 2
( 6) 2
(7) 3
(8) 2
(9) 2
(10) 3

31. Свойства степеней:

(i) 2 P
1) Для любого графа
сумма степеней вершин равна удвоенному
количеству ребер
2) Для любого графа количество вершин
нечетной степени всегда четно
(Лемма о рукопожатии: в любой момент
времени количество людей, сделавших
нечетное количество рукопожатий, четно)
3) В любом графе есть по крайней мере 2
вершины, имеющие одинаковую степень.

32. Пример:

Может ли в государстве, в котором из
каждого города выходят ровно 3 дороги,
быть ровно 100 дорог?
Ответ: Нет (по формуле 3n=2*100,
откуда n-количество городов- не целое)

33.

Планарность
Граф называется планарным, если его можно изобразить на плоскости
без пересечения ребер.
2
д
1
д
д
3
К3,3
к
4
к
к
6
5
Для определения планарности несущественно
наличие петель, кратных ребер, висячих
вершин и вершин степени 2.
К5
Теорема Понтрягина – Куратовского: граф
планарен тогда и только тогда, когда он
не содержит подграфов К3,3 и К5
33

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

1. Явное задание графа в виде двух множеств
вершин V и ребер Е, когда каждое ребро
определено парой инцидентных ему концевых
вершин.
2. Геометрический способ.
3. Матрица смежности.
4. Матрица инцидентности.
5. Список ребер.
34

35.

V х1 , х2 , х3 , х4 , х5
множество вершин:
множество ребер:
U u1 , u 2 , u3 , u 4 , u5 , u6 , u7 , u8 , u9 , u10
отношение инцидентности:
P ( х1 , u1 , х2 ), ( х2 , u1 , х1 ), ( х2 , u 2 , х2 ), ( х3 , u3 , х1 ), ( х1 , u 4 , х3 ), ( х3 , u5 , х2 ), ( х2 , u5 , х3 ), ( х3 , u6 , х5 ),
( х5 , u6 , х3 ), ( х3 , u7 , х4 ), ( х4 , u7 , х4 ), ( х4 , u8 , х3 ), ( х4 , u9 , х5 ), ( х5 , u9 , х4 ), ( х4 , u10 , х5 )
35

36. Геометрический способ

Геометрический граф – это плоская фигура, состоящая из
вершин – точек плоскости и ребер – линий, соединяющих некоторые
пары вершин.
Точки называются вершинами, или узлами, графа, линии —
ребрами графа.
36

37.

3. Матрица смежности
37

38. Матрица смежности графа

39.

3. Матрица смежности
Граф:
3
1
2
3
4
5
6
5
4
2
3
1
2
3
4
5
6
7
8
1
0
1
0
1
0
0
1
0
0
2
1
0
0
0
0
0
1
0
1
0
3
0
0
0
0
1
0
0
1
4
1
0
0
0
0
1
0
0
5
0
0
1
0
0
0
0
0
1
0
6
1
0
1
0
1
0
0
0
1
0
7
0
1
0
0
0
0
1
0
0
0
8
0
0
1
0
0
1
0
0
0
1
2
1
6
6
7
8
39

40. МАТРИЧНЫЕ ПРЕДСТАВЛЕНИЯ ГРАФОВ

• Для орграфа (рис. 1) построить матрицу
смежности A(G).
Рис. 1

41. МАТРИЧНЫЕ ПРЕДСТАВЛЕНИЯ ГРАФОВ

42.

4. Матрица инцидентности
42

43.

43

44. МАТРИЧНЫЕ ПРЕДСТАВЛЕНИЯ ГРАФОВ

Матрицей инциденций B(G) = {bik] орграфа
G = (X,U) называется прямоугольная матрица
размерности n х т (n — число вершин
графа, m — количество дуг), элементы
которой удовлетворяют условиям:

45. МАТРИЧНЫЕ ПРЕДСТАВЛЕНИЯ ГРАФОВ

• В матрице инциденций для неографа при
ее построении элементы -1 следует
заменить на 1.
• Построим матрицу B(G) инциденций для
орграфа G (рис. 1).

46.

Матрица инцидентности
Граф:
3
1
2
3
5
6
5
4
2
3
1
6
6
7
8
1-4
1-6
2-6
2-7
3-5
3-8
4-6
5-8
6-7
1
-1
1
1
-1
1
0
0
0
0
0
0
0
2
1
0
0
1
-1
1
0
0
0
0
0
3
0
0
0
0
0
1
-1
-1
1
0
0
0
4
0
-1
1
0
0
0
0
0
-1
1
0
0
5
0
0
0
0
0
1
0
0
1
0
6
0
0
1
-1
1
0
0
0
1
0
-1
1
7
0
0
0
0
1
0
0
0
0
1
8
0
0
0
0
0
0
1
0
-1
1
0
1
2
4
1-2
46

47. Перечень (списки) ребер

Для хранения перечня ребер необходим
двумерный массив размерности M×2.
Строка массива описывает ребро.

48. Перечень ребер

1
5
1
2
3
9
3
4
2
1
8
6
4
8
5
7 7
6
2
1
1 6
2
4 9
3
2 3
4
3 4
5
1 2
6
7 8
7
6 7
8
4 5

49.

5. Список ребер
Граф:
3
1
2
3
5
6
5
4
2
3
3
1 4
2
1 6
5
2 6
3
2 7
2
3 5
1
3 8
4
4 6
6
5 8
1
6 7
6
1
2
4
1 2
1
6
6
7
8
49

50.

Пути и маршруты
3
2
4
1
1–2–3–7 –8–1
5
8
7
6
Последовательность попарно инцидентных вершин Vi1 ,Vi2,
..., Vik неориентированного графа, т.е. последовательность
ребер неориентированного графа, в которой вторая вершина
предыдущего ребра совпадает с первой вершиной
следующего, называется маршрутом.
Число ребер маршрута называется длиной маршрута.
Если начальная вершина маршрута совпадает с конечной, то
такой маршрут называется замкнутым или циклом.
50

51.

Расстоянием между двумя вершинами
называется минимальная длина из всех
возможных маршрутов между этими
вершинами при условии, что существует хотя
бы один такой маршрут.
Обозначается как d( V1V2) (от лат. distantio —
расстояние) d( V1V2) = min| V1…..V2 |.
В маршруте одно и то же ребро может
встретиться несколько раз. Если ребро
встретилось только один раз, то маршрут
называется цепью.

52.

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

53.

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

54.

Связность
вершины 1 и 3 – связаны;
вершины 2 и 4 – нет.
3
2
4
1
5
8
7
6
изображенный граф –
несвязный
две компоненты связности:
(1, 2, 3, 7, 8) и (4, 5, 6)
Две вершины называются связанными, если существует путь, начинающийся
в одной из этих вершин и заканчивающийся в другой.
Граф называется связным, если любые две вершины в нем связаны.
Компонента связности – максимальный связный подграф.
Подграф – это подмножество вершин вместе со всеми инцидентными им ребрами.
Максимальный – это означает, что при добавлении любой новой вершины
в множество граф становится несвязным.
В неориентированном графе компоненты связности всегда не пересекаются, и нет
ребер, ведущих из вершин одной компоненты в другую.
54

55.

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

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

57.

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

58.

Эйлеровым путем в графе называется
путь, содержащий все ребра графа.
Эйлеровым циклом в графе называется
цикл, содержащий все ребра графа.
Граф, обладающий эйлеровым циклом,
называется эйлеровым графом. Если
снять ограничение на замкнутость пути, то
граф будет называться полуэйлеровым.
Плоский эйлеров граф также называют
уникурсальным.
Теорема 1. Граф G является эйлеровым тогда и только
тогда, когда G – связный граф, имеющий все чётные
вершины.
На рисунке 1 изображён
пример эйлерова графа.

59. Циклы Эйлера

ЦИКЛЫ Эйлера
Эйлеров цикл содержит не только все ребра (по
одному разу) графа, но и все вершины этого графа
(возможно по несколько раз). Эйлеровым может
быть только связный граф. Примером такого графа
является граф, представленный на рис. 2.
Рис. 2.

60.

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

61. Теорема Эйлера об ориентированных графах

62. Алгоритм Флёри построения эйлерова цикла

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

63.

Join us on a mission to save more existing trees and plant new ones.
Гамильтоновым путём (циклом) графа G
называется путь (цикл), проходящий через
каждую его вершину только один раз. Граф,
содержащий гамильтонов цикл, называется
гамильтоновым. В графе на рисунке путь
(V3,V4,V1,V2,V5) является гамильтоновым, а путь
(V2,V3,V4,V1,V2,V5)
не
является
гамильто-новым. V1
V2
V4
рис. 6
V3
V5

64. Гамильтонов граф

Рис. 7

65. Достаточны условия Гамильтонова графа

66. Циклы Эйлера и Гамильтона

ЦИКЛЫ Эйлера и
Гамильтона
Составляя
задачи
отыскания
эйлеровых
и
гамильтоновых циклов, следует отметить, что внешне
формулировки задач похожи, однако они оказываются
принципиально
различными
с
точки
зрения
практического применения.
Эйлером получено просто проверяемое необходимое
и достаточное условие существования в графиках
эйлерова цикла.
Для гамильтоновых графов таких условий нет, поэтому
алгоритма построения таких циклов нет.

67.

Граф G называется планарным (плоским),
если существует изоморфный ему граф G , в
изображении которого на плоскости рёбра
пересекаются только в вершинах. Графы G1 и
G3 являются планарными, а G2 – нет.
G
G
1
3
G
2

68.

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

69. ПРИМЕР соответствия плоского графа кубу

70.

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

71.

Пример.
Данный граф выделяет
в плоскости следующие
области: А1 с границей q;
А2 с границей (o,s,t); A3 c
границей (q,s,u,r,t); A4 c
границей (p,u); А5 с границей (o,p,r).
q
А3
A
s
C
1
t
А2
u
о
p А
4
А5
r

72.

Теорема (Эйлера) Если G – связный планарный
граф, содержащий n вершин, m ребер и r граней, то
n m r 2
Доказательство.
Пусть G – связный планарный граф, который имеет k
вершин. Рассмотрим некоторый остов этого графа. Остов
имеет всего одну внешнюю грань r=1, n=k вершин и m=k-1
ребер,
т.е.
n - m + r= k - (k - 1) + 1 = 2.
Будем поочередно добавлять к остову недостающие
ребра графа G. При каждом добавлении число вершин не
изменится, число ребер увеличивается на единицу, так же
как и число граней, поскольку при добавлении к остову
ребра, связывающего две несмежные вершины,
получается цикл, разделяющий текущую грань на две.
Таким образом, формула будет верна для всякого
графа, получающегося в результате таких операций, а
поскольку графом G заканчивается вся эта процедура, то
эта формула будет верна и для него.

73.

Графы Понтрягина - Куратовского, играют важную
роль в теории планарности графов. Они не являются
планарными графами.
Граф
K5 представляет
собой
полный
граф
наименьшего порядка, который, не являясь планарным
графом (полные графы K2, K3, K4 - планарные),
становится планарным после удаления хотя бы одного
его ребра.
Второй (двудольный граф K33) является моделью
известной задачи о трех домах и трех колодцах.