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

1.

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

2.

Приложении теории графов в
различных отраслях наук
Графы и
информация
«Транспортные»
задачи
Графы и физика
(Кирхгоф)
Графы и химия
Графы и
биология
(Кэли)
Логические
задачи
Обменные
схемы
Логистика

3.

Цель:
изучить
теоретический
материал по теме
«Теория графов» и
возможность его
применения
Задачи:
рассмотреть основные
определения;
сформулировать и
доказать основные
теоремы, в т.ч. лемму
«о рукопожатиях» ,
теоремы Кёнига, Оре,
Холла

4.

План лекции
Введение в теорию графов
1) основные определения;
2) виды графов;
II. Основные леммы и теоремы;
III. Применение «Теории графов» к решению задач
I.

5.

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

6.

Определения
q
• два ребра
E
A
C
называются
смежными, если
они имеют общую
вершину;
s
t
D
m
p
r
• два ребра
называют
кратными если
они соединяют
одну и ту же пару
вершин;
B
• вершина называется изолированной, если она не является концом
ни для одного ребра
• ребра называется петлей если его концы совпадают;
Пример:
Смежные ребра: DС и CA, CD и DB, DB и BA, BA и AC
Изолированная вершина: E
Кратные ребра: m и p
Петля: q

7.

Определения
• степенью вершины A называют количество ребер, для которых
она является концевой (петли считать дважды)
Обозначение: deg(A).
Пример:
D
F
B
C
E
A
G
H
q
E
C
A
s
D
u
p
t
deg(G) = 1
deg(H) = 1
deg(E) = 1
deg(B) = 1
deg(A) = 1
deg(C) = 4
deg (D) = 2
r
B
deg(E) = 0
deg(C) = 2
G, H, E, B, A висячие вершины
E – изолированная
вершина

8.

Лемма о рукопожатиях
В любом графе сумма степеней всех вершин равна
удвоенному числу ребер
Доказательство:
1. Если ребро соединяет две различные
Следствие
вершины графа, то при подсчете суммы
vi 2q
степеней
вершин
учтемнечетной
это ребро
|=> четно
В любомвсех
графе
число мы
вершин
степени
i
(по определению
дважды;
степени
2. Если ребро является петлей, то при
вершины)
подсчете суммы степеней всех вершин мы
ч.т.д
также учтем это ребро дважды;
степенью вершины называют количество ребер, для
которых она является концевой (петли считать дважды)

9.

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

10.

Пример:
Может ли в государстве, в котором из каждого
города выходит 3 дороги быть ровно 100 дорог
Решение:
1. Города – вершины графа (k, kєN ). Степень кратности
каждой вершины 3 =>
v 3k
i
i
2. Дороги – ребра графа (p = 100)
3. По Лемме 3k = 2p. Если р = 100, то k =
Но kєN => p ≠ 100
Ответ: не может
200
3

11.

Виды графов
• Граф, состоящий из
«изолированных» вершин,
называется нулевым графом
B
A
M
• Граф, в которых не построены
все возможные ребра, называют
неполным графом.
A
C
B
C
D
E
D
• Граф называется полным, если любые две его различные вершины
соединены одним и только одним ребром.
U
L
B
V
O

12.

Виды графов
граф без кратных ребер и петель называется обыкновенным
C
D
B
A
E
G
если степени всех вершин графа равны, то граф называется
однородным.
2
А
B
3 E
2
3
O
D
2
C
2
deg(A) = deg(B) = deg(C) = deg(D) = 2
3
3
P
K
deg(O) = deg(P) = deg(E) =deg(K) = 3

13.

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

14.

Орграф
Степень входа
вершин графа:
конец дуги(A,B)
B
u
r
A
deg ( B ) 1
t
s
C
Начало дуги
(A,B)
deg ( A) 1
дуги
Степенью входа (выхода) вершины
орграфа называется число ребер, для
которых эта вершина является концом
(началом)
deg (C ) 2
Степень выхода
вершин графа:
deg ( A) 1
deg ( B) 2
deg (C ) 1

15.

Связный граф
• Если в графе две любые вершины соединены путем, то
такой граф называется связным
S
B
A
M
D
D
C
C
O
связный граф
не связный граф

16.

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

17.

Пример:
Докажите, что граф с n вершинам, степень каждого из
которых не менее n 1 , связен.
2
Решение:
n 1
2
1
A
1
n 1
2
B
1) Рассмотрим вершины A и B, не соединенные путем.
2)
3)
n 1
Вершина А соединена не менее чем с
вершинами,
2
n 1
Вершина B также соединена не менее чем с 2 (по условию)
4) Вершина А отлична от В ( иначе между ними существует путь)
n 1 n 1
5) Тогда в графе 1+1+
+
вершин, то есть n+1.
2
2
6) Но по условию всего n вершин. Мы пришли к противоречию |=>
вершины соединены путем => граф связен.
ч.т.д.

18.

Интересные дороги
Решение:

19.

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

20.

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

21.

Определения
• Путём (или цепью) в графе называется такая
последовательность ребер, в которой каждые два соседних
ребра имеют общую вершину и никакое ребро не
встречается более одного раза.
A2
3
2
A1
A3
A5
4
1
A4
5
Пример:
1) (А1 А4); (А4 А5)
2) (А1 А2); (А2 А4); (А4 А5).
3) (А1 А4); (А4 А2); (А2 А1); (А1 А3); (А3 А4); (А4, А5).
4) (А1 А4); (А4 А2); (А2 А1); (А1 А3); (А3 А5);
путь

22.

Определения
Циклом называется путь, в котором совпадают его начальная и
конечная вершины.
Простым циклом в графе называется цикл, не проходящий ни
через одну из вершин графа более одного раза.
Пример:
Циклы состоящие из 4 ребер:
(AB, BC, CE, EA), (CD, DA, AB, BC)
(DA,AB,BE, EC, CA, AE, ED)
Простые циклы: (EB, BC, CD, DE) и т.д.
A
B
E
D
C

23.

Двудольный граф
Определения
Граф называется двудольным, если его вершины можно разбить
на множества Х и У таких, что каждое ребро графа соединяет
некоторую вершину из Х с некоторой вершиной из У.
• Множество Х и У называют долями этого графа
Х
Y

24.

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

25.

26.

Теорема Кенига

27.

Задача о назначениях
Дан двудольный граф, требуется построить максимальное паросочетание
Пример:
Задача о деревенских свадьбах
Назначение на должность: имеются вакантные должности и
претенденты на них, о каждом претенденте известно какие
должности он может занять, требуется заполнить максимум
вакансий
Выбор представителей: в парламенте есть несколько
комиссий, член парламенты может заседать в нескольких
комиссиях; нужно выбрать председателя каждой комиссии

28.

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

29.

Теорема Холла о свадьбах
Дан двудольный граф с долями X и Y. Совершенное паросочетание
существует тогда и только тогда когда |Х| = |Y| и |O(M)| ≥ |M| для
всякого M X
Y1
X1
Доказательство:
X2
Y2
Y3
X3
Y4
X4
Y5
X5
X6
Необходимость: Совершенное паросочетание Р в графе G можно
рассмотреть как функцию, отображающую каждую вершину из Х в
смежную ей вершину Y. По определению совершенного паросочетания
эта функция является биекций, откуда |X|=|Y|. Более того, P отображает
каждое подмножество M X в некоторое подмножество YM содержащие
|M| элементов, являющихся смежными к вершинам из М вершин. Но тогда
YM O(M) и |М|=| YM | |O(M)|
ч.т.д

30.

Достаточность
Пусть G – двудольный граф, для которого |X| = |Y| = n и
выполнено условие (1). Докажем что в G существует
паросочетание P, содержащие n ребер.
Проведем индукцией по n. В случае n = 1 (база).
Единственная вершина из Х и единственная вершина из Y
должны быть соединены ребром, чтобы условие (1)
выполнялось. Но тогда можно взять Р = G.
Перейдем к шагу индукции: предположим, что для
двудольных графов с меньшим чем n числом вершин в
каждой доле утверждения теоремы верно. Возможно два
случая

31.

Эйлеровы графы
•Граф является эйлеровым тогда и только тогда, когда он
связный граф, имеющий все четные вершины

32.

Определения
• Эйлеровым путем в графе называется путь, содержащий
все ребра графа.
• Эйлеровым циклом или эйлеровой цепью называется цикл,
содержащий все ребра графа и притом по одному разу.
Теорема №1
Если граф G(V,E) обладает эйлеровым циклом, то он связный и
все его вершины четные.
Теорема №2 (Эйлер)
Граф без изолированных вершин является эейлоровым, тогда и
только тогда, когда он связен и степени всех вершин его четны

33.

Гамильтоновы графы
• Гамильтонов путем (циклом) графа называется путь ( цикл)
проходящий через каждую вершину только один раз
• Граф, содержащий гамильтонов цикл, называется
гамильтоновым
Пример:
гамильтонов путь:
(C, D, A, B, M);
(B, A, D, C, F)
A
B
D
M
C
F

34.

Теорема (Оре)
Пусть дан обыкновенный связный граф, содержащий n > 2
вершин, такой что сумма степеней любых двух несмежных
вершин не меньше, чем n. Тогда граф гамильтонов.
Доказательство:
• Предположим что существует граф G, который удовлетворяет
условию теоремы, но не является гамильтоновым графом. Будем
добавлять к нему новые ребра до тех пор, пока не получим
максимальный негамильтонов граф G1
• Пусть u, v несмежные вершины в полученном графе G1. Если
добавить ребро uv, появится гамильтонов цикл. Тогда путь (u, v) –
гамильтонов.
• Для вершин u,v выполняется неравенство:
deg u + deg v ≥ n
• По принципу Дирихле всегда найдутся две смежные вершины t1 и t2 на
пути (u, v) т.е. u…t1t2..v, такие что существует ребро ut2 и ребро ut1
• |S|+|T| = deg u + deg v ≥ n, но |S|+|T| < n, тогда |S T| = |S|+|T|

35.

Планарные (плоские) графы
• Граф G(V, E) называется планарным, если на плоскости его
можно изобразить так, чтобы все пересечения его ребер
являются вершинами графа G(V, E)
• Грань в плоском представлении
графа называется часть плоскости,
ограниченная простым циклом и не
содержащая внутри других циклов.
Пример: (BAC), (CAE), (CDE)
первоначальный
граф
C
B
D
A
E
изображенный иначе

36.

Мультиграф
Мультиграфом называется
граф, в котором пара вершин
соединяется несколькими
различными ребрами. Для
ориентированного мультиграфа
вершины могут соединятся
несколькими ребрами в
каждом из направлений.
Псевдографом
называется граф, в
котором есть и петли и
кратные ребра
A
A
C
B
B
C

37.

Пример:
Каждый из 102 учеников одной школы знаком не менее, чем с
68 другими. Докажите, что среди них найдутся четверо, имеющие
одинаковое число знакомых
Решение:
1) пусть верно обратное.
2) тогда для каждого числа от 68 до 101 имеется не более трех
человек, имеющих такое же число знакомых.
3) имеется ровно 34 натуральных числа, начиная с 68 и заканчивая
101, а 102 = 3 ∙ 4. Это означает что для каждого числа от 68 до 101
есть ровно три человека, имеющие такое число знакомых
4) Но тогда количество людей, имеющих нечетное количество
знакомых нечетно. (Л) | => верно обратное, т.е. среди учеников
найдутся четверо, имеющие одинаковое число знакомых

38.

Задача о кёнигсберских мостах
• Город Кенигсберг ( ныне Калининград) расположен на
берегах реки Прегель и двух островах на этой реке. Части
города соединены мостами. Спрашивается, можно ли,
выйдя из какой либо точки города, пройти по каждому
мосту ровно один раз и вернутся в исходную точку

39.

Решение:
Объекты – части города
Связи - мосты
Можно ли обойти данный граф пройдя по каждому ребру ровно один раз
и вернуться и вернувшись в исходную вершину, то есть существует ли
последовательность ребер графа со следующими свойствами:
любые два соседних ребра имеют общую вершину;
последнее ребро имеет общую вершину с первым;
каждое ребро графа встречается в последовательности ровно
один раз

40.

Операции над графами
Дополнением графа G1 (V1,E1) называется граф G1 (V1 , E1 ),
множеством вершин которого является множество V1, а
множеством его ребер является множество E1 {e V1 V1 : e E1}
G1
G2
G3
Дополнение
графа G1
графом G3, до
графа G2
Объединением графов G1 (V1 , E1 ) и G2 (V2 , E2 ) при условии, что
V1 V2 ; E1 E2 , называется граф G1 (V1 , E1 ) и G2 (V2 , E2 ),
множеством вершин которого является множество V1 V2 , а
множеством его ребер является множество E1 E2 .

41.

Операции над графами
Пересечением графов G1 (V1 , E1 ) и G2 (V2 , E2 ) называется граф G1 (V1 , E1 ) G2 (V2 , E2 )
множеством вершин которого является множество V1 V2 а, множеством его ребер
– множество E1 E2 .
Суммой по модулю два графа G1 (V1 , E1 ) и G2 (V2 , E2 ) при условии, что V1 V2 ; E1 E2 ,
называется граф G1 (V1 , E1 ) G2 (V2 , E2 ), множеством вершин которого является
множество V1 V2 , а множеством его ребер – множество E1 E2 .
Другими словами, этот граф не имеет изолированных вершин и состоит только из
ребер, присутствующих либо в первом графе, либо во втором, но не в обоих графах
одновременно.

42.

Способы задания графов
Аналитический способ задания графов
Граф G(V,E) задан, если задано множество элементов V и отображение Е
множества V в V. Отображение Е может быть как однозначным, так и многозначным.
В общем случае на V и E никаких ограничений не накладывается.
Пусть дано множество V { v1 , v2 ,..., vn} , которое имеет мощность
V { v1 , v2 ,..., vn} иногда пишут V { v i}, i { 1,2,...,}.n
V . n Вместо
Для того чтобы задать отображение Е на V или, что то же самое, отображение V в
V, необходимо каждому элементу vi V поставить в соответствие Е. Это
подмножество обозначают через Evi , поэтому Evi V .
Другой формой аналитического способа задания является задание графа как
совокупности множества элементов V и подмножества упорядоченных пар vi , v j V V .
Подмножество множества пар vi , v j декартова произведения V V эквивалентно
бинарному отношению R, заданному на множестве V. Поэтому множество V и
бинарное отношение R на множестве V также определяет некоторый граф G.

43.

Геометрический способ
Множество элементов V графа G изображают кружками, это множество вершин.
Каждую вершину vi V соединяют линиями с теми вершинами vi V , для которых
выполняется условие vi Vvi . Множество линий, которое соответствует множеству
упорядоченных пар vi , v j , есть множество ребер графа.
Матричный способ
Квадратная матрица элементами которой являются нули и единицы, а также
некоторое число m, называется матрицей смежности графа G(V,E) тогда
ai , j , и только
тогда когда ее элементы образуются по следующему правилу: элемент
стоящий
на пересечении vi го
столбца, равен единице, если имеется ребро, идущие
из
ai , j
вершины vi в вершину v j , и ai j равен нулю в противном случае. Элемент
равен
единице, если
ai j при вершине vi имеется петля, и равен нулю в противном случае.
vj
Элемент vi
равен некоторому
числу m, где m – число ребер графа, идущее из
вершины v1 ,...,
в вершину
.
vn ,
e1 ,..., em
Пусть
- вершины, а
- ребра некоторого ориентированного графа
G(V,E). Матрица размером (m 1x, если
n), где
называется
еi исходит
из v1 ; матрицей инцидентности для
ориентированного графа.
ai , j 1, если еi заходит в v1 ;
0, если е не инцидентна v ;
i
1