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

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

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

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

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

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

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

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

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

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

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

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

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

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

Списки связи

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример построения остовного дерева минимального веса для графа 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 }

Выполняемые действия Множество вершин Граф 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 }.

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

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

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

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

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

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

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

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

V1V1 V2V2 V3V3 V4V4 V5V5

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

V1V1 V2V2 V3V3 V4V4 V5V5

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

V1V1 V2V2 V3V3 V4V4 V5V5

Ответы

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

Ответы