'

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

Понравилась презентация – покажи это...





Слайд 0

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


Слайд 1

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


Слайд 2

Граф это конечное множество вершин V и множество ребер R, соединяющих пары вершин, G=(V,R). Мощности множеств V и R равны N и M. Множество ребер может быть пустым. Примеры вершин – объекты любой природы (населенные пункты, компьютерные сети). Примеры ребер – дороги, стороны, линии.


Слайд 3

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


Слайд 4

Ориентированный граф Неориентированный граф В орграфе ребро называют дугой.


Слайд 5

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


Слайд 6

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


Слайд 7

Способы описания графа: матрица инциденций, матрица смежности, списки связи, перечни ребер.


Слайд 8

Матрица инциденций N – количество вершин M – количество ребер Матрица инциденций – это двумерный массив размерности N?M


Слайд 9

Матрица инциденций 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8


Слайд 10

Матрица смежности – это двумерный массив N*N.


Слайд 11

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


Слайд 12

Матрица смежности сети (с учетом весов ребер)


Слайд 13

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


Слайд 14

Списки связи 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8


Слайд 15

Перечень ребер Для хранения перечня ребер необходим двумерный массив размерности M?2. Строка массива описывает ребро.


Слайд 16

Перечень ребер 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8


Слайд 17

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


Слайд 18

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


Слайд 19

Преобразование графа в остовное связное дерево минимального веса Пусть G=(V,R) – связанный взвешенный неориентированный граф. Граф G можно представить в виде матрицы смежности, содержащий значения весов ребер.


Слайд 20

Граф в форме схемы


Слайд 21

Матрица смежности связного взвешенного неориенторованного графа


Слайд 22

Подграф графа, остовной связный подграф, остовное связное дерево


Слайд 23

Цикломатическое число ? показывает сколько ребер графа нужно удалить, чтобы в нем не осталось циклов. ?=m-n+1 Пример, ?=8-5+1=4 Для каждого графа обычно существует несколько связных деревьев, с различными весами.


Слайд 24

Остовные связные деревья графа G


Слайд 25

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


Слайд 26

Существует 4 случая: 1) обе вершины включаемого ребра принадлежат одноэлементным подмножествам, тогда они объединяются в новое, связное подмножество; 2) одна из вершин принадлежит связному подмножеству, а другая нет, тогда включаем вторую в подмножество, которому принадлежит первая; 3) обе вершины принадлежат разным связным подмножествам, тогда объединяем подмножества; 4) Обе вершины принадлежат одному связному подмножеству, тогда исключаем данное ребро.


Слайд 27

Алгоритм заканчивает работу, когда все вершины будут объединены в одно множество, при этом оставшиеся ребра не включаются в остовное дерево.


Слайд 28

Пример построения остовного дерева минимального веса для графа G


Слайд 29


Слайд 30


Слайд 31


Слайд 32

Вопросы для закрепления В какой форме можно представить граф? В чем разница между орграфом и не орграфом? Какие графы являются деревьями? Какой граф обладает минимальным весом?


Слайд 33

Изучение графов на языке Паскаль. Построить остовные связные деревья минимального веса для графов с 5-ю вершинами Матрицу смежности графа и дерева вывести в виде таблиц.


Слайд 34

Объявление переменных Два целочисленных пятиэлементных массива X и Y для хранения координат вершин графа Целочисленный двумерный массив R для хранения весов ребер графа Целочисленные переменные i, n и k для счетчиков циклов Целочисленная переменная S для хранения суммы весов ребер дерева минимального веса


Слайд 35

Генерация случайных координат 5-ти вершин графа (цикл по i). Вычисление весов ребер. Вывод матрицы смежности взвешенного орграфа (вложенные циклы по n и по k) Вывод матрицы смежности взвешенного неориентрованного графа – половины элементов начальной матрицы (начальное значение k=n+1) Тело программы


Слайд 36

Построение остовного связанного дерева минимального веса с учетом 4-х случаев. Тело программы


Слайд 37

Даны координаты вершин графа. Вычислить весы ребер. Вывести матрицу смежности взвешенного неориентированного графа. Построить остовное связное дерево минимального веса. V1(50,59) V2(84,6) V3(70,32) V4(22,59) V5(91,40)


Слайд 38

V1 V2 V3 V4 V5


Слайд 39

Решение. R12=round(sqrt(sqr(84-50)+sqr(59-6)))=63


Слайд 40

V1 V2 V3 V4 V5


Слайд 41

Решение. мин R35=22, {3,5} мин R14=28, {3,5}, {1,4} мин R23=30, {3,5,2}, {1,4} мин R13=34, {1,2,3,4,5} S=22+28+30+34=114


Слайд 42

V1 V2 V3 V4 V5


Слайд 43

Ответы 50 59 84 6 70 32 22 59 91 40 63 34 28 45 30 82 35 55 22 72 22 3 5 28 1 4 30 2 3 34 1 3 114


Слайд 44

68 50 22 88 86 10 78 58 79 29 Даны координаты вершин графа. Вычислить весы ребер. Вывести матрицу смежности взвешенного неориентированного графа. Построить остовное связное дерево минимального веса.


Слайд 45

Ответы 68 50 22 88 86 10 78 58 79 29 60 44 13 24 101 64 82 49 20 29 13 1 4 20 3 5 24 1 5 60 1 2 117


Слайд 46

Практическая работа 46 51 51 83 43 53 6 60 17 96 32 4 41 54 31 51 36 38 50 38 6 4 1 3 31 2 3 36 2 5 38 3 4 109


Слайд 47

4 67 45 74 25 39 43 83 4 33 42 35 42 34 40 9 58 48 22 63 6 9 2 4 22 3 5 34 1 5 35 1 3 100


Слайд 48

83 88 78 64 1 43 89 34 83 51 25 94 54 37 80 32 14 88 82 18 6 14 2 5 18 4 5 25 1 2 80 2 3 137


Слайд 49

65 34 69 12 33 63 57 18 18 58 22 43 18 53 62 13 69 51 16 56 6 13 2 4 16 3 5 18 1 4 43 1 3 90


Слайд 50

29 35 64 37 26 58 73 1 47 82 35 23 56 50 43 37 48 74 32 85 6 23 1 3 32 3 5 35 1 2 37 2 4 127


Слайд 51

40 57 7 70 86 76 88 3 98 81 35 50 72 63 79 105 92 73 13 79 6 13 3 5 35 1 2 50 1 3 72 1 4 170


Слайд 52

48 37 86 62 40 3 31 40 99 70 45 35 17 61 75 59 15 38 89 74 6 15 2 5 17 1 4 35 1 3 38 3 4 105


Слайд 53

2 23 96 36 56 76 89 96 1 20 95 76 114 3 57 60 96 39 78 116 6 3 1 5 39 3 4 57 2 3 60 2 4 159


Слайд 54

87 51 11 6 51 15 66 51 59 34 88 51 21 33 41 71 56 39 21 18 6 18 4 5 21 1 4 21 3 5 41 2 3 101


Слайд 55

1 54 67 23 50 13 13 61 93 58 73 64 14 92 20 66 44 61 62 80 6 14 1 4 20 2 3 44 2 5 61 3 4 139


×

HTML:





Ссылка: