ФГБОУ ВО ДГМА ИМЕНИ С.С. ПРОКОФЬЕВА

тема: Графы. Решение алгоритмических задач, связанных с анализом графов

Видео урока: https://resh.edu.ru/subject/lesson/5491/main/203178/

Решение алгоритмических задач связанных с анализом графов. .pptx 

Введение в теорию графов

 

Основные понятия теории графов

 

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

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

Рис. 1.57. Задача прокладки коммуникаций

 Основные понятия теории графов. Граф G задается с помощью пары множеств G = (V,R), где V — множество (совокупность) вершин, R — множество ребер, соединяющих пары вершин. Множество ребер может быть пустым, если ни одна из вершин не соединена с другими вершинами.

Обычно граф представляют с помощью схемы, на которой некоторые вершины соединены линиями (ребрами) (рис. 1.58).

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

Любую систему улиц в городе можно представить в вид» графа. Здесь вершины — это перекрестки.

Вершины называются смежными, если их соединяет ребро. Например, на рис. 1.58 смежные вершины V₁ и V₂, так как их соединяет ребро R₁₂.

Множества V и R являются конечными — мы можем перечислить все вершины и ребра графа. Количество вершин и количество ребер графа определяют мощности множеств V и R. Так, количество вершин графа G равно 5, а количество ребер равно 8.

Ребро и любая из его двух вершин называются инцидентными. Под степенью вершины подразумевается количество инцидентных ей ребер. Так, степень вершины V₁ равна 3, а степень вершины V₅ равна 4.

 

Рис. 1.58. Граф G в форме схемы

Маршрут графа

 

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

Маршрут является замкнутым (циклом), если его начальная и конечная вершины совпадают. Например, в графе G можно выделить несколько циклических маршрутов, например V₄R₁₂V₂R₂₃V₃R₃₄V₄R₁₄V₁ и V₂R₂₃V₃R₃₅V₅R₂₅V₂.

Маршрут называется простой цепью, если все его вершины и ребра различны.

Длина маршрута равна количеству ребер, входящих в него.

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

Например, маршрут между вершинами V₁ и V₄ может быть следующим: V₁R₁₂V₂R₂₃V₃R₃₄V₄.

 

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

 

Ориентированные графы

 

Сообразительный читатель может задать вопрос: имеет ли значение направление, ориентация ребра? Ведь в системе улиц можно найти дороги как с односторонним, так и с двусторонним движением. Именно поэтому в теории графов вводится понятие орграфа — ориентированного графа. В орграфе каждое ребро имеет одно направление. Такие ребра называются дугами. Другими словами, ребро — это неупорядоченная пара вершин, а дуга — упорядоченная. Очевидным является тот факт, что дуги R₁₂ и R₂₁ не совпадают в орграфе. Для орграфа вводятся такие понятия, как входящая и исходящая степени вершины. Это соответственно число входящих в вершину дуг и число исходящих из нее дуг.

Взвешенные графы

 

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

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

Описание графа с помощью матрицы смежности

 

Для наглядного представления графа используются схемы (см. рис. 1.58), а для математических расчетов удобнее использовать представление графа в форме матрицы смежности (рис. 1.59, а). Матрицу смежности можно представить в виде таблицы, строки и столбцы которой соответствуют номерам вершин графа. Если вершины смежные, то элемент матрицы смежности равен 1, если вершины не смежные, то элемент матрицы равен 0. Диагональные элементы матрицы равны 0, так как вершины сами с собой не смежные (их не соединяет ребро).

Пусть в матрице смежности графа G строки нумеруются индексом n, а столбцы — индексом k, тогда элементы матрицы смежности обозначаются R_nk. Для смежных вершин элементы матрицы смежности (R₁₂, R₁₄, R₁₅, R₂₁, R₂₃, R₂₅, R₃₂, R₃₄, R₃₅, R₄₁, R₄₃, R₄₅, R₅₁, R₅₂, R₅₃, R₅₄) равны 1, а для не смежных вершин элементы матрицы (R₁₃, R₂₄, R₃₁, R₄₂) равны 0. Диагональные элементы матрицы (R₁₁, R₂₂, R₃₃, R₄₄, R₅₅) равны 0.

Преобразуем граф G в сеть, т. е. присвоим ребрам, соединяющим смежные вершины, числовые значения (R₁₂ = 50, R₁₄ = 25, R₁₅ = 10, R₂₁ = 50, R₂₃ = 25, R₂₅ = 30, R₃₂ = 25, R₃₄ = 50, R₃₅ = 35, R₄₁ = 25, R₄₃ = 50, R₄₅ = 15, R₅₁ = 10, R₅₂ = 30, R₅₃ = 35, R₅₄ = 15). Отобразим сеть G в форме матрицы смежности (рис. 1.59, б).

Рис. 1.59. Граф и сеть G в форме матрицы смежности

Подграфы и деревья

 

Подграфом графа G называется граф, у которого все вершины и ребра принадлежат графу G (рис. 1.60, а).

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

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

 

Рис. 1.60. а — подграф графа G, б — основной связный подграф графа G, в — основное связное дерево

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

 

Пусть G = (V, R) — связный взвешенный неориентированный граф, где V — множество вершин, a R — множество ребер (см. рис. 1.58). Ребра графа не ориентированы, т. е. ребра Rnk и Rkn считаются одним и тем же ребром, поэтому в матрице смежности не учитываются дублирующие друг друга ребра. В результате граф G можно представить с помощью матрицы смежности, содержащей значения весов десяти ребер (на рис. 1.61 выделены жирным шрифтом).

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

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

ϒ = m - n + 1,

где m — количество ребер, n — количество вершин.

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

ϒ = m - n + 1 = 8 - 5 + 1 = 4.

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

Для каждого графа обычно существует несколько остовных связных деревьев, которые обладают различными весами. На рис. 1.60, в представлено остовное связное дерево графа G, вес которого равен 135, а на рис. 1.62 представлены три остовных связных дерева графа G, веса которых равны 130, 100, 135.

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

Для построения остовного связного дерева минимального веса используется алгоритм Крускала.

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

2. Ребра сортируются по возрастанию весов.

3. Ребра последовательно, по возрастанию их весов, включаются в основное дерево. Существуют четыре случая:

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

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

Рассмотрим реализацию этого алгоритма на примере построения остовного дерева минимального веса для графа G.