Презентация на тему: Тема3. Элементы теории графов

Тема3. Элементы теории графов
Тема3. Элементы теории графов
С. 57-76
С. 28-40; 331-348
Тема3. Элементы теории графов
Тема3. Элементы теории графов
Тема3. Элементы теории графов
Пример графа «звезда»
Тема3. Элементы теории графов
Тема3. Элементы теории графов
Тема3. Элементы теории графов
Теория графов
Тема3. Элементы теории графов
Тема3. Элементы теории графов
Тема3. Элементы теории графов
Тема3. Элементы теории графов
Тема3. Элементы теории графов
Тема3. Элементы теории графов
Тема3. Элементы теории графов
Arthur Cayley ; (1821 - 1895) — английский математик.
Тема3. Элементы теории графов
Уильям Роуэн Гамильтон
Терминология теории графов
Теория графов и кибернетика
Тема3. Элементы теории графов
Тема3. Элементы теории графов
Тема3. Элементы теории графов
Тема3. Элементы теории графов
2.Основные виды графов
Ориентированный граф -орграф
Тема3. Элементы теории графов
Тема3. Элементы теории графов
Тема3. Элементы теории графов
Тема3. Элементы теории графов
Тема3. Элементы теории графов
Тема3. Элементы теории графов
Тема3. Элементы теории графов
Тема3. Элементы теории графов
Тема3. Элементы теории графов
3. Задание графов
Матрица смежности
Задание орграфа
Тема3. Элементы теории графов
Тема3. Элементы теории графов
4. Характеристики графов
Тема3. Элементы теории графов
Тема3. Элементы теории графов
Деревья. Лес.
Деревья. Лес.
Степень вершины
Теорема о сумме степеней вершин
Подграф
Частичный граф
Тема3. Элементы теории графов
Тема3. Элементы теории графов
Тема3. Элементы теории графов
Цикломатическое число.
Тема3. Элементы теории графов
Хроматическое число графа.
Тема3. Элементы теории графов
Примеры раскраски графов
Тема3. Элементы теории графов
Тема3. Элементы теории графов
Проблема четырёх красок — математическая задача, предложенная Гутри (англ.) в 1852 году.
Тема3. Элементы теории графов
Изоморфизм графов.
Тема3. Элементы теории графов
Изоморфизм графов
Тема3. Элементы теории графов
Тема3. Элементы теории графов
Понятие об операциях над графами.
Понятие об операциях над графами.
Сети Петри
Тема3. Элементы теории графов
Сети Петри
Основными свойствами сети Петри являются:
Некоторые виды сетей Петри:
Некоторые виды сетей Петри:
Множество устойчивости
Тема3. Элементы теории графов
1/80
Средняя оценка: 4.4/5 (всего оценок: 16)
Код скопирован в буфер обмена
Скачать (1879 Кб)
1

Первый слайд презентации

Тема3. Элементы теории графов

Изображение слайда
2

Слайд 2

Лекция 11 ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ ГРАФОВ

Изображение слайда
3

Слайд 3: С. 57-76

Изображение слайда
4

Слайд 4: С. 28-40; 331-348

Изображение слайда
5

Слайд 5

С.15-31

Изображение слайда
6

Слайд 6

1. Понятие о графах и теории графов.

Изображение слайда
7

Слайд 7

Совокупность множества М с заданным на нем бинарным отношением называется графом G=<M,T>, где М – носитель графа – множество вершин, изображаемых точками, Т – сигнатура графа – множество линий, обозначающих отношения и называемых ребрами.

Изображение слайда
8

Слайд 8: Пример графа «звезда»

М={1,2,3,4,5}, Т={(1,3),(1,4),(2,4),(2,5),(3,1), (3,5),(4,2),(4,1),(5,3),(5,2}).

Изображение слайда
9

Слайд 9

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

Изображение слайда
10

Слайд 10

Между элементами двух множеств М и Т определено отношение инцидентности, т.е. связи между двумя элементами множества М через один элемент множества Т. Множество линий-ребер в Т задается обозначением пары ( i, j ), где i,j – инцидентные вершины, отношение Т – «быть связанным». Между элементами одного множества определено отношение смежности, то есть «соседства».

Изображение слайда
11

Слайд 11

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

Изображение слайда
12

Слайд 12: Теория графов

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

Изображение слайда
13

Слайд 13

Родоначальником теории графов считается Леонард Эйлер. В 1736 - задача о кёнигсбергских мостах

Изображение слайда
14

Слайд 14

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

Изображение слайда
15

Слайд 15

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

Изображение слайда
16

Слайд 16

Первые серьезные результаты теории графов связаны с решением задач построения электрических цепей (Г. Кирхгоф)

Изображение слайда
17

Слайд 17

Г. Кирхгоф (1824-1887 гг.) – Законы Кирхгофа

Изображение слайда
18

Слайд 18

Изображение слайда
19

Слайд 19

Подсчет числа химических соединений с различными типами молекулярных связей (А. Кэли).

Изображение слайда
20

Слайд 20: Arthur Cayley ; (1821 - 1895) — английский математик

Изображение слайда
21

Слайд 21

КУРАТОВСКИЙ (Kuratowski) Казимеж (1896-1980), польский математик, иностранный член АН СССР (1966). Труды по топологии, теории функций, теории графов.

Изображение слайда
22

Слайд 22: Уильям Роуэн Гамильтон

Уильям Роуэн Гамильтон ( William Rowan Hamilton ; 1806 —1865) — выдающийся ирландский математик. Гамильтонов граф

Изображение слайда
23

Слайд 23: Терминология теории графов

Терминология теории графов поныне не определена строго. Иногда граф называют "сетью", но мы будем считать сетью граф особого вида (транспортная сеть)

Изображение слайда
24

Слайд 24: Теория графов и кибернетика

В 30-е годы ХХ века благодаря трудам Д. Кенига теория графов стала развиваться как самостоятельный раздел математики. Широкое развитие теория графов получила с 50-х годов ХХ века в связи с появлением такой науки, как кибернетика.

Изображение слайда
25

Слайд 25

Термин «граф» (от латинского слова «графио» - пишу) приобрел права гражданства и вошел в математический язык в 1936 году, после выхода в свет известной монографии Кёнига, в которой впервые графы рассматриваются как самостоятельные математические объекты независимо от их конкретного содержания.

Изображение слайда
26

Слайд 26

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

Изображение слайда
27

Слайд 27

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

Изображение слайда
28

Слайд 28

Графы используются в поисковых системах (Google) Теория графов используется в химии (для описания структур, путей сложных реакций) Новая наука – компьютерная химия

Изображение слайда
29

Слайд 29: 2.Основные виды графов

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

Изображение слайда
30

Слайд 30: Ориентированный граф -орграф

Изображение слайда
31

Слайд 31

Множество ребер может быть пусто. Если же множество вершин пусто, то пусто и множество ребер. Такой граф называется пустым .

Изображение слайда
32

Слайд 32

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

Изображение слайда
33

Слайд 33

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

Изображение слайда
34

Слайд 34

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

Изображение слайда
35

Слайд 35

Полный граф: все вершины соединены друг с другом. Это квадрат множества М. Петли необязательны.

Изображение слайда
36

Слайд 36

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

Изображение слайда
37

Слайд 37

Псевдограф содержит и ребра, и дуги. Тривиальный граф содержит только одну вершину.

Изображение слайда
38

Слайд 38

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

Изображение слайда
39

Слайд 39

Представление бинарных отношений

Изображение слайда
40

Слайд 40: 3. Задание графов

Граф можно задать так называемой матрицей смежности В, каждой i -ой строке ( j -му столбцу) которой однозначно сопоставляют элемент множества М, между которыми выполняется отношение смежности. Две вершины, инцидентные одному ребру, смежны. Два ребра, инцидентные одной вершине, тоже смежны.

Изображение слайда
41

Слайд 41: Матрица смежности

i /j 1 2 3 4 5 1 0 0 1 1 0 2 0 0 0 1 1 3 1 0 0 0 1 4 1 1 0 0 0 5 0 1 1 0 0 Каждая клетка bij соответствует квадрату множества М  М

Изображение слайда
42

Слайд 42: Задание орграфа

i /j t1 t2 t3 t4 t5 1 -1 0 0 0 1 2 1 -1 -1 0 0 3 0 1 0 -1 0 4 0 0 1 1 -1

Изображение слайда
43

Слайд 43

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

Изображение слайда
44

Слайд 44

Граф может быть задан списочной структурой: списками смежности и массивами рёбер (дуг).

Изображение слайда
45

Слайд 45: 4. Характеристики графов

Маршруты, цепи, пути, циклы и контуры

Изображение слайда
46

Слайд 46

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

Изображение слайда
47

Слайд 47

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

Изображение слайда
48

Слайд 48: Деревья. Лес

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

Изображение слайда
49

Слайд 49: Деревья. Лес

Деревом может быть задано отношение подчинения в трудовом коллективе, в государстве. Простейшее дерево состоит из двух вершин, соединенных ребром. Каждый раз, когда добавляется еще одно ребро, в конце его прибавляется также и вершина. Следовательно, дерево с n вершинами имеет n -1 ребро.

Изображение слайда
50

Слайд 50: Степень вершины

Степенью вершины х, обозначаемой deg(х), называют число ребер, инцидентных ей. Если degх=1, то вершина х тупиковая, если degх=0, то вершина изолированная. Если G – неориентированный граф с n вершинами и m ребрами, то сумма степеней вершин равна удвоенному количеству ребер:

Изображение слайда
51

Слайд 51: Теорема о сумме степеней вершин

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

Изображение слайда
52

Слайд 52: Подграф

Подграфом G Ω графа G =<М,Т> называется граф, в который входит лишь часть вершин графа G, образующих множество А, вместе с ребрами (дугами), их соединяющими. Так, карта шоссейных дорог Пермской области является подграфом графа «Карта шоссейных дорог Российской Федерации»

Изображение слайда
53

Слайд 53: Частичный граф

Частичным графом G  по отношению к графу G называется граф, содержащий только часть ребер (дуг) графа G. Так, карта главных дорог России –частичный граф карты шоссейных дорог России

Изображение слайда
54

Слайд 54

Если две вершины соединены ребром, то говорят, что каждая вершина инцидентна этому ребру, а соответствующие вершины – смежны (две вершины, инцидентные одному ребру – смежны). Два ребра, инцидентные одной вершине, также смежны.

Изображение слайда
55

Слайд 55

Если две вершины соединены ребром, то говорят, что каждая вершина инцидентна этому ребру, а соответствующие вершины – смежны (две вершины, инцидентные одному ребру – смежны). Два ребра, инцидентные одной вершине, также смежны.

Изображение слайда
56

Слайд 56

Если две вершины соединены ребром, то говорят, что каждая вершина инцидентна этому ребру, а соответствующие вершины – смежны (две вершины, инцидентные одному ребру – смежны). Два ребра, инцидентные одной вершине, также смежны.

Изображение слайда
57

Слайд 57: Цикломатическое число

Пусть G – неориентированный связный граф, имеющий n вершин и m ребер. Цикломатическим числом связного графа G с n вершинами и m ребрами называется число  (G)=m-n+1. Это число имеет интересный физический смысл: оно равно наибольшему числу независимых циклов в графе. При расчете электрических цепей цикломатическое число используется для определения числа независимых контуров.

Изображение слайда
58

Слайд 58

а) I 1 б) I II III 1 в) I 1 2 г) I 1 2 II III IV д) I 1 2 3 е) I 1 2 3 II ж) 1 2 3 4 I з) II 1 2 3 4 I и) 1 2 3 4 II 1 2 3 4 I III

Изображение слайда
59

Слайд 59: Хроматическое число графа

Граф G называют р - хроматическим, где р – натуральное число, если его вершины можно раскрасить р различными цветами так, чтобы никакие две смежные вершины не были раскрашены одинаково.

Изображение слайда
60

Слайд 60

Наименьшее число р, при котором граф является р -хроматическим, называют хроматическим числом графа и обозначают  (G). Если  (G)=2, то граф называют бихроматическим. Необходимым и достаточным условием бихроматичности является отсутствие в графе циклов нечетной длины.

Изображение слайда
61

Слайд 61: Примеры раскраски графов

Изображение слайда
62

Слайд 62

Изображение слайда
63

Слайд 63

Френсис Гутри, студент де Моргана, в 1852 году: можно ли всякую расположенную на сфере карту раскрасить четырьмя красками так, чтобы любые две области, имеющие общий участок границы, были раскрашены в разные цвета?

Изображение слайда
64

Слайд 64: Проблема четырёх красок — математическая задача, предложенная Гутри (англ.) в 1852 году

Изображение слайда
65

Слайд 65

К. Аппель и В. Хакен доказали в 1976 г. С помощью ЭВМ, что так можно раскрасить любую карту. Поэтому некоторые математики отнеслись к этому доказательству с недоверием, что объяснялось не только использованием компьютера, но и громоздкостью описания алгоритма первых доказательств (741 страница). Впоследствии были предложены более компактные алгоритмы и скорректирован ряд ошибок.

Изображение слайда
66

Слайд 66: Изоморфизм графов

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

Изображение слайда
67

Слайд 67

Изображение слайда
68

Слайд 68: Изоморфизм графов

Если граф ориентированный, то направление дуг в изоморфных графах должно совпадать. Чтобы узнать, представляют ли две матрицы смежности изоморфные графы, можно произвести всевозможные одинаковые перестановки строк и столбцов. Если после одной из этих перестановок возникнет матрица, совпадающая с заданной, то сравниваемые графы изоморфны. Для этого требуется максимум n ! перестановок, где n – число вершин графа.

Изображение слайда
69

Слайд 69

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

Изображение слайда
70

Слайд 70

Два не изоморфных графа, у которых эти параметры совпадают

Изображение слайда
71

Слайд 71: Понятие об операциях над графами

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

Изображение слайда
72

Слайд 72: Понятие об операциях над графами

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

Изображение слайда
73

Слайд 73: Сети Петри

Сети Петри — математический аппарат для моделирования динамических дискретных систем. Впервые описаны Карлом Петри в 1962 году.

Изображение слайда
74

Слайд 74

Сеть Петри представляет собой двудольный ориентированный граф, состоящий из вершин двух типов — позиций и переходов, соединённых между собой дугами, вершины одного типа не могут быть соединены непосредственно. В позициях могут размещаться метки (маркеры), способные перемещаться по сети.

Изображение слайда
75

Слайд 75: Сети Петри

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

Изображение слайда
76

Слайд 76: Основными свойствами сети Петри являются:

Ограниченность — число меток в любой позиции сети не может превысить некоторого значения K. Безопасность — частный случай ограниченности, K=1. Достижимость — возможность перехода сети из одного заданного состояния (характеризуемого распределением меток) в другое. Живость — возможностью срабатывания любого перехода при функционировании моделируемого объекта. В основе исследования перечисленных свойств лежит анализ достижимости.

Изображение слайда
77

Слайд 77: Некоторые виды сетей Петри:

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

Изображение слайда
78

Слайд 78: Некоторые виды сетей Петри:

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

Изображение слайда
79

Слайд 79: Множество устойчивости

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

Изображение слайда
80

Последний слайд презентации: Тема3. Элементы теории графов

Если две вершины соединены ребром, то говорят, что каждая вершина инцидентна этому ребру, а соответствующие вершины – смежны (две вершины, инцидентные одному ребру – смежны). Два ребра, инцидентные одной вершине, также смежны.

Изображение слайда