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

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

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

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

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

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

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

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

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

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

10 Матрица инциденций

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

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

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

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

15 Списки связи

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

17 Перечень ребер

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

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

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

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

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

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

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

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

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

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

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

29 Пример построения остовного дерева минимального веса для графа GG Выполняемые действия Множество вершин Граф 1Построим остовной подграф с изолированным и вершинами Получим 5 одноэлементных подмножеств: {V 1 }, {V 2 }, {V 3 }, {V 4 }, {V 5 } 2Найдем ребро минимального веса (R 15 ) и добавим его в остовной подграф Образуем связное подмножество вершин: {V 1,V 5 }. Сохраняем подмножества {V 2 }, {V 3 }, {V 4 }

30 Выполняемые действия Множество вершин Граф 3Среди оставшихся найдем ребро минимального веса (R 45 ) и добавим его в остовной подграф Добавим в связное подмножество вершину: {V 1,V 5, V 4 }. Сохраняем подмножества {V 2 }, {V 3 } 4Среди оставшихся найдем ребро минимального веса (R 23 ) и добавим его в остовной подграф Образуем новое связное подмножество вершин: {V 2,V 3 }. Сохраняем первое связное подмножество {V 1,V 5, V 4 }.

31 Выполняемые действия Множество вершин Граф 5Среди оставшихся найдем ребро минимального веса (R 25 ) и добавим его в остовной подграф Объединяем подмножества в одно связное подмножество {V 1,V 5, V 4,V 2,V 3 }. 6Остальные ребра не включаются в граф, т.к. все их вершины уже принадлежат одному связному множеству.

32 Выполняемые действия Множество вершин Граф 7Получен граф, который: остовной (все вершины включены); связный (все вершины можно соединить маршрутами); дерево (нет циклов); имеет минимальный вес. 8Полученное остовное дерево имеет минимальный вес: R 12 +R 25 +R 15 +R 45 = =80 9 Циклическое число графа G равно γ=m-n+1=8-5+1=4, что соответствует количеству ребер, не включенных в дерево.

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

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

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

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

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

38 Даны координаты вершин графа. Вычислить весы ребер. Вывести матрицу смежности взвешенного неориентированного графа. Построить остовное связное дерево минимального веса. V 1 (50,59) V 2 (84,6) V 3 (70,32) V 4 (22,59) V 5 (91,40)

39 V1V1 V2V2 V3V3 V4V4 V5V5

40 Решение R 12 =round(sqrt(sqr(84-50)+sqr(59-6)))=63

41 V1V1 V2V2 V3V3 V4V4 V5V5

42 Решение. мин 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= =114

43 V1V1 V2V2 V3V3 V4V4 V5V5

44 Ответы

45 Даны координаты вершин графа. Вычислить весы ребер. Вывести матрицу смежности взвешенного неориентированного графа. Построить остовное связное дерево минимального веса.

46 Ответы