Теория графов
Литература
Задача о Кёнигсбергских мостах Леонард Эйлер(1707-1783)
Основные объекты графов
Понятие графа и орграфа
Неориентированный граф (граф)
Ориентированный граф (орграф)
Геометрический граф
Обозначение
типы метаграфов ГИПЕРГРАФ (модельный граф)
взвешенные метаграфы
Локальная структура графа
Пример
Степень вершины
Теорема
Свойства степеней графа
Степень графа
Локальная структура ориентированного графа
Пример
Степени вершин в орграфе
Свойства степеней орграфа
Свойства степеней орграфа
Матричное представление графа
Пример
Матрица инцидентности В
Пример
Матрица смежности орграфа
Пример
Матрица инцидентности В
Пример
Функциональный способ задания графов
Пример
Функциональный способ задания орграфов
Пример
Пример
Изоморфизм графов
Функциональное задание изоморфизма графов
Свойства изоморфизма
Пример изоморфных графов
Пример не изоморфных графов
Инварианты графа
Полный граф Kn
Двудольный граф
Двудольные графы. Примеры
Полный двудольный граф Km,n
Полные двудольные графы Km,n
Операции над графами
Удаление вершины
Подграфы
Подграфы
Дополнение графа
Самодополнительные графы
739.92K
Category: mathematicsmathematics

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

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. Самодополнительные графы

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