Теория графов. Определения и примеры. Пути и циклы

Сентябрь 14, 2022

Главная
Математика
Теория графов. Определения и примеры. Пути и циклы

Содержание

2. Определения и примеры Хотя обычно теорию графов считают одной из современных областей математики, ее начало датируется
3. Определения и примеры Эйлер (1707 – 1783) родился в Швейцарии и провел большую часть жизни в
4. Определения и примеры Как и большинство выдающихся математиков того времени, Эйлер внес вклад почти в каждую
5. Определения и примеры Что такое ‘граф’? Интуитивно, граф – это набор точек, называемых ‘вершинами’, и набор
6. Определения и примеры
7. Определения и примеры
8. Определения и примеры
9. Определения и примеры
10. Определения и примеры
11. Определения и примеры
12. Определения и примеры Определение 2 Степенная последовательность графа – это последовательность степеней его вершин, записанных в
13. Определения и примеры
14. Определения и примеры
15. Определения и примеры Степени четырех вершин приведены в следующей таблице.
16. Определения и примеры
17. Определения и примеры Граф Петерсена – хорошо известный простой 3-регулярный граф. На рисунке изображены две диаграммы
18. Определения и примеры Определение 3 Нулевым графом (или вполне несвязным графом) называется граф с пустым множеством
19. Определения и примеры
20. Определения и примеры Примеры Так как полный граф является простым, то в нем нет петель, и
21. Определения и примеры
22. Определения и примеры Примеры Полные графы с тремя, четырьмя и пятью вершинами приведены на следующем рисунке.
23. Определения и примеры
24. Определения и примеры
25. Определения и примеры
26. Определения и примеры
27. Определения и примеры
28. Определения и примеры
29. Определения и примеры
30. Определения и примеры
31. Определения и примеры
32. Определения и примеры
33. Определения и примеры
34. Определения и примеры
35. Определения и примеры Примеры Матрица смежности полного графа – матрица с нулями на главной диагонали (так
36. Определения и примеры
37. Определения и примеры
38. Определения и примеры
39. Пути и циклы По аналогии с дорожной картой мы можем рассматривать различные типы ‘путешествий’ в графе.
40. Пути и циклы
41. Пути и циклы
42. Пути и циклы Последовательность ребер графа – это произвольная последовательность ребер, которую можно начертить на диаграмме
43. Пути и циклы
44. Пути и циклы
45. Пути и циклы
46. Пути и циклы
47. Пути и циклы
48. Пути и циклы
49. Пути и циклы
50. Пути и циклы
51. Пути и циклы
52. Пути и циклы
54. Пути и циклы
55. Пути и циклы
56. Пути и циклы
57. Пути и циклы
58. Пути и циклы На интуитивном уровне ясно, что некоторые графы являются ‘единым целым’, а другие состоят
59. Пути и циклы Определение 7 Граф называется связным, если для любых двух его различных вершин существует
60. Пути и циклы
61. Пути и циклы Компоненты графа – это его связные ‘куски’. В частности, связный граф имеет только
62. Пути и циклы
63. Пути и циклы
64. Пути и циклы
65. Пути и циклы
66. Пути и циклы
68. Скачать презентацию

Слайд 2

Определения и примеры
Хотя обычно теорию графов считают одной из современных областей

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

Слайд 3

Определения и примеры
Эйлер (1707 – 1783) родился в Швейцарии и провел

большую часть жизни в России (Санкт Петербург) и Пруссии (Берлин).
Он был одним из самых плодовитых математиков. Собрание его научных трудов составляет более 70 томов.

Gamilton

Слайд 4

Определения и примеры
Как и большинство выдающихся математиков того времени, Эйлер внес

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

Gamilton

Слайд 5

Определения и примеры
Что такое ‘граф’?
Интуитивно, граф – это набор точек,

называемых ‘вершинами’, и набор линий, называемых ‘ребрами’, при этом каждая линия либо соединяет пару точек, либо соединяет точку саму с собой.
Пример графа, знакомый каждому, – карта дорог, на которой города являются вершинами, а соединяющие их дороги – ребрами графа.

Слайд 6

Определения и примеры

Слайд 7

Определения и примеры

Слайд 8

Определения и примеры

Слайд 9

Определения и примеры

Слайд 10

Определения и примеры

Слайд 11

Определения и примеры

Слайд 12

Определения и примеры
Определение 2
Степенная последовательность графа – это последовательность степеней его

вершин, записанных в неубывающем порядке.

Слайд 13

Определения и примеры

Слайд 14

Определения и примеры

Слайд 15

Определения и примеры
Степени четырех вершин приведены в следующей таблице.

Слайд 16

Определения и примеры

Слайд 17

Определения и примеры
Граф Петерсена – хорошо известный простой 3-регулярный граф. На

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

Слайд 18

Определения и примеры
Определение 3
Нулевым графом (или вполне несвязным графом) называется граф

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

Слайд 19

Определения и примеры

Слайд 20

Определения и примеры
Примеры
Так как полный граф является простым, то в нем

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

Слайд 21

Определения и примеры

Слайд 22

Определения и примеры
Примеры
Полные графы с тремя, четырьмя и пятью вершинами приведены

на следующем рисунке.

Слайд 23

Определения и примеры

Слайд 24

Определения и примеры

Слайд 25

Определения и примеры

Слайд 26

Определения и примеры

Слайд 27

Определения и примеры

Слайд 28

Определения и примеры

Слайд 29

Определения и примеры

Слайд 30

Определения и примеры

Слайд 31

Определения и примеры

Слайд 32

Определения и примеры

Слайд 33

Определения и примеры

Слайд 34

Определения и примеры

Слайд 35

Определения и примеры
Примеры
Матрица смежности полного графа – матрица с нулями на

главной диагонали (так как нет петель) и единицами на остальных позициях (так как каждая пара различных вершин соединена единственным ребром).

Слайд 36

Определения и примеры

Слайд 37

Определения и примеры

Слайд 38

Определения и примеры

Слайд 39

Пути и циклы
По аналогии с дорожной картой мы можем рассматривать различные

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

Слайд 40

Пути и циклы

Слайд 41

Пути и циклы

Слайд 42

Пути и циклы
Последовательность ребер графа – это произвольная последовательность ребер, которую

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

Слайд 43

Пути и циклы

Слайд 44

Пути и циклы

Слайд 45

Пути и циклы

Слайд 46

Пути и циклы

Слайд 47

Пути и циклы

Слайд 48

Пути и циклы

Слайд 49

Пути и циклы

Слайд 50

Пути и циклы

Слайд 51

Пути и циклы

Слайд 52

Пути и циклы

Слайд 53

Слайд 54

Пути и циклы

Слайд 55

Пути и циклы

Слайд 56

Пути и циклы

Слайд 57

Пути и циклы

Слайд 58

Пути и циклы
На интуитивном уровне ясно, что некоторые графы являются ‘единым

целым’, а другие состоят из нескольких частей.
Объясним эту ситуацию, используя понятие пути.

Слайд 59

Пути и циклы
Определение 7
Граф называется связным, если для любых двух его

различных вершин существует путь, связывающий эти вершины.

Слайд 60

Пути и циклы

Слайд 61

Пути и циклы
Компоненты графа – это его связные ‘куски’.
В частности, связный

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

Слайд 62