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

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

Лекция 1

2. Литература

1. В.А. Горбатов Дискретная математика М.:
АСТ; Астрель, 2003
2. Харари Ф. Теория графов, 2003г
3. Кристофидес, Н. Теория графов.
Алгоритмический подход. 1978
4. Кузнецов О.П., Дискретная математика для
инженера, 2009.
5. Тихомирова А.Н. Теория графов, МИФИ,

3. Задача о Кёнигсбергских мостах Леонард Эйлер(1707-1783)

4. Основные объекты графов

• носитель метаграфа (конечное множество
вершин). V={v1,v2, … vp}
• сигнатура метаграфа (конечное множество
связей между вершинами). U={u1,u2, … uq}
П.Порешин

5. Понятие графа и орграфа

Граф G=<V,U>, где
V={v1,v2,…,vn}, n 1 –
множество вершин (носитель),
U V V (сигнатура).

6. Неориентированный граф (граф)

G = <V, U>,
V = {v1,v2,…,vn},n 1,
U V V
(vi,vj) = (vj, vi)
(vi,vj) – ребро графа
(vi, vi) - петля

7. Ориентированный граф (орграф)

G=<V,U>,
V={v1,v2,…,vn},n 1
U V V
(vi,vj) ≠ (vj, vi)
(vi,vj) - дуга

8. Геометрический граф

Граф
Орграф

9. Обозначение

Gp,q V = p, U = q
G1,0 - тривиальный граф

10. типы метаграфов ГИПЕРГРАФ (модельный граф)

Сигнатура (U) - множество граней, каждая из
которых связывает некоторое подмножество
вершин. Грань – подмножество вершин
гиперграфа
u ÎU ® u V
G = V ,U
V = { v1 , v2 , v3 , v4 }
u1 = { v1 , v2 , v4 }
u2 = { v2 , v3 , v4 }
U = { u1 , u2 }
П.Порешин

11. взвешенные метаграфы

f: V®N - весовая функция для носителя (вершин)
g: U ®K - весовая функция для сигнатуры (ребер или дуг)
N, K – некоторые множества (весовые характеристики)
П.Порешин

12. Локальная структура графа

(vi,vj)ÎU – vi и vj – смежны
uk= (vi,vj) – uk инцидентно vi,
uk инцидентно vj, vi инцидентно uk
vj инцидентно uk
uk= (vi,vj), un= (vi,vm) –
uk и un – смежны

13. Пример

14. Степень вершины

Степень вершины (d(vi)) – число рёбер,
инцидентных вершине
d(v1)=2
d(v2)=2
d(v3)=3
d(v4)=1

15. Теорема

В любом конечном графе
число вершин нечётной
степени чётно.

16. Свойства степеней графа

Gp,q
p
d
(
v
)
=
2
q
i
i =1

17. Степень графа

Степень графа (максимальная степень
вершины)
(G ) = max {d (vi )}
viÎV
Минимальная степень вершины графа
(G ) = min{d (vi )}
viÎV

18. Локальная структура ориентированного графа

uk= (vi,vj) – дуга uk положительно
инцидентна vi,
дуга uk отрицательно инцидентна vj,
uk= (vi,vj), un= (vi,vm) –
uk и un – смежны

19. Пример

20. Степени вершин в орграфе

d+(vi) – число
положительно
инцидентных дуг
вершины vi.
d-(vi) – число
отрицательно
инцидентных дуг
вершины vi.
d+(v1) =2, d-(v1) =0;
d+(v2) =1, d-(v2) =2.

21. Свойства степеней орграфа

Для любого ориентированного графа
d
(
v
)
=
d
(
v
)
i i
vi ÎV
vi ÎV

22. Свойства степеней орграфа

Для любого ориентированного графа
(
d
(
v
)
d
(
v
))
=
2
q
i
i
vi ÎV

23. Матричное представление графа

Матрица смежности А:
1, (vi , v j ) Î U
aij =
0
,
(
v
,
v
)
U
i
j

24. Пример

А=
0
1
1
0
1
0
1
0
1
1
0
1
0
0
1
0

25. Матрица инцидентности В

1, vi инцидентно u j
bij =
0
,
v
не
инцидентно
u
i
j

26. Пример

В=
1
1
0
0
1
0
1
0
0
1
1
0
0
0
1
1

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

А:
1, (vi , v j ) Î U
aij =
0
,
(
v
,
v
)
U
i
j

28. Пример

А=
0
0
0
0
1
0
1
0
1
1
0
0
0
0
1
0

29. Матрица инцидентности В

1, u j = (vi , vk )
bij = 1, u j = (vk , vi )
0, v не инцидентно u
j
i

30. Пример

В=
1
-1
0
0
1
0
-1
0
0
1
-1
0
0
-1
1
0
0
0
1
-1

31. Функциональный способ задания графов

G=<V,Г>
Г- функция окрестности вершин
Г:V®P(V)
Г(v)={vi vi смежна с v}

32. Пример

Г(v1)={v2, v3}
Г(v2)={v1, v3}
Г(v3)={v1, v2,v4}
Г(v4)={v3}

33. Функциональный способ задания орграфов

G=<V,Г+> G=<V,Г->
Г+, Г- - функции положительной и
отрицательной полуокрестности
вершины, соответственно
Г+ : V® P(V)
Г- : V® P(V)
Г+(v)={vi (v,vi)Î U} Г-(v)={vi (vi,v)Î U}

34. Пример

Г(v1)+={v2, v3}
Г(v2) ={v3}
+
Г(v3) ={v2,v4}
+
Г(v4)+=

35. Пример

-
Г(v1) =
-
Г(v2) ={v1,v3}
-
Г(v3) ={v1,v2}
-
Г(v4) ={v3}

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

Графы изоморфны, если
существует взаимно однозначное
соответствие между
множествами вершин,
сохраняющее отношение
смежности

37. Функциональное задание изоморфизма графов

Два графа Ga= Va,Ua и Gb= Vb,Ub
изоморфны, если существует взаимно
однозначная функция
h: Va®Vb такая, что:
1) если (va1 ,va2 )Î Ua, то (h(va1),h(va2)) Î
U b;
2) если (vb1,vb2) Î Ub, то
(h1(v ),h-(v )) Î Ua
b1
b2

38. Свойства изоморфизма

Отношение
• рефлексивно
• симметрично
• транзитивно
Эквивалентность

39. Пример изоморфных графов

40. Пример не изоморфных графов

41. Инварианты графа

Количественная или качественная
характеристики, неизменные для всех
изоморфных между собой графов (орграфов)
называется ИНВАРИАНТОМ
Поиск полной системы инвариантов графа,
задающей граф с точность до изоморфизма –
основная задача теории графов
(полная система инвариантов ещё не
найдена)

42. Полный граф Kn

Граф полный, если каждая вершина
смежна с каждой.
Полный граф с n вершинами - Kn

43. Двудольный граф

Граф двудольный, если множество
вершин графа можно разбить на два
непересекающихся подмножества, в
каждом из которых никакая пара вершин
не смежна.
G=<V, U>, V=V1 V2,
V1 V2= , U V1 V2

44. Двудольные графы. Примеры

45. Полный двудольный граф Km,n

Km,n - граф двудольный и каждая
вершина из множества V1 смежна с
каждой вершиной из V2, V1 =m,
V2 =n.
G=<V, U>, V=V1 V2, V1 V2= ,
U=V1 V2

46. Полные двудольные графы Km,n

47. Операции над графами

Удаление ребра
G=<V, U>, G\u=<V, U\{u}>

48. Удаление вершины

G=<V, U>, G\v=<V’, U’>
V’=V\{v}, U’=U (V’ V’)

49. Подграфы

G’=<V’, U’> подграф графа
G=<V, U>, если
V’ V,
U’=U (V’ V’)
(порождённый
подграф)

50. Подграфы

G’=<V’, U’> частичный
подграф графа
G=<V, U>, если
V’ V,
U’ U (V’ V’)
(частичный
граф, подграф)

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

=<V, U’> дополнение
графа G=<V,U>,
если
U’=((V V)\U)\I

52. Самодополнительные графы

Граф, изоморфный своему
дополнению - самодополнительный