Меню
Главная
Авторизация/Регистрация
 
Главная arrow Информатика arrow Информатика
Посмотреть оригинал

ВВЕДЕНИЕ В ТЕОРИЮ ГРАФОВ

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

Задача прокладки коммуникаций

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

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

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

Граф G в форме диаграммы

Рис. 12.22. Граф G в форме диаграммы

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

Вершины называются смежными, если их соединяет ребро. Например, смежны вершины V-j и V2, так как их соединяет ребро R12.

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

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

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

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

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

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

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

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

Взвешенные графы. Выше мы познакомились со структурами, которым присущи те или иные свойства графа. Немного расширяя терминологию теории графов, математика вводит понятие взвешенного графа, или более обобщенно — сети.

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

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

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

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

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

(Д/2> R1Ф R21’ ^23’ б* >,? R'j2’ R34’ б*;,? R4p R431 Д^5> б*,,. R32, R54)

равны 1, а для не смежных вершин элементы матрицы (R13, R24, R31, R42) равны 0. Диагональные элементы матрицы (R1V R22, R33, R44, Д55) равны 0.

Преобразуем граф G в сеть, т.е. присвоим ребрам, соединяющим смежные вершины, числовые значения, которые соответствуют их длине (R12 = 50, Ru = 25, R15 = 10, R21 = 50, Rr3 = 25, R25 = 30, R32 = 25, R34 = 50, R35 = 35, R41 = 25, R43 = 50, R45 = 15, R51 = 10, RT> = 30, R53 = 35, R34 = 15). Отобразим сеть G в форме матрицы смежности (рис, 12.29).

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

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

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

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

Подграф

Рис. 12.24. Подграф

Остовной связный подграф

Рис. 12.25. Остовной связный подграф

Остовное связное дерево

Рис. 12.26. Остовное связное дерево

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

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

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

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

где т — количество ребер;

п — количество вершин.

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

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

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

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

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

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

  • 1. Первоначально каждая вершина исходного графа помещается в одноэлементное подмножество, где все вершины изолированы.
  • 2. Ребра сортируются по возрастанию веса.
  • 3. Ребра последовательно включаются в остовное дерево. Существуют четыре случая:
    • ? обе вершины ребра не принадлежат пока ни одному множеству, тогда они объединяются в новое множество,
    • ? одна из вершин принадлежит множеству, а другая нет, тогда включаем вторую в множество первой,
    • ? обе вершины принадлежат разным множествам, тогда объединяем множества,
    • ? обе вершины принадлежат одному множеству, тогда исключаем данное ребро.

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

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

п/п

Выполняемые

действия

Множество вершин

Граф

1

Построим остовной подграф, содержащий только изолированные вершины

Каждая вершина исходного графа помещается в одноэлементные подмножества: {V"rb {V2}, {V3}, {V4}, {V5}

2

Найдем ребро минимального веса (в данном случае Я,5) и добавим его в остовной подграф

Образуется связное подмножество вершин: {Vv V5). Сохраняются одноэлементные подмножества вершин:

{Уф {Уф {УЛ

3

Среди оставшихся ребер найдем ребро минимального веса (в данном случае R45) и добавим его в остовной подграф

Так как одна вершина ребра входит в связное подмножество добавим в нее и вторую: {Vv V5, V4}. Сохраняются одноэлементные подмножества вершин:

{Уф {У3}

4

Среди оставшихся ребер найдем ребро минимального веса (в данном случае R23) и добавим его в остовной подграф

Так как ни одна из вершин ребра не входит в связное подмножество, создадим второе связное подмноже- ство: {V2, V3}.

Существует также первое связное подмножество:

{У„ У5, УФ

5

Среди оставшихся ребер найдем ребро минимального веса (в данном случае Я25) и добавим его в остовной подграф

Так как одна вершина ребра входит в одно связное подмножество, а другая вершина в другое связное подмножество, эти подмножества объединяются в единое связное множе- ство: {Vu V5, V4, V2, V3]

6

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

п/п

Выполняемые

Множество вершин Граф действия г т

7

Получен граф, который:

  • ? является остовным, так как включает все вершины;
  • ? является связным, так как все вершины в нем можно соединить маршрутами;Зцух1уЫявляется деревом, так как в нем отсутствуют циклы;
  • ? обладает минимальным весом, так как в него последовательно включались ребра, отсортированные по возрастанию.

8

Полученное остовное связное дерево обладает минимальным весом: R12 + R25 + Rjs + R45 = 25 + 30 + 10 + 15 = 80.

9

Цикломатическое число графа G равно у = т - п + 1 = 8- 5 + 1 =4, что соответствует количеству ребер, не включенных в остовное связное дерево.

Контрольные вопросы

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

Практикум к главе 12

Практическая работа 12.1. Проект «Бросание мячика в площадку» Практическая работа 12.2. Проект «Графическое решение уравнения» Практическая работа 12.3. Проект «Распознавание волокон»

Практическая работа 12.4. Проект «Распознавание удобрений» Практическая работа 12.5. Проект «Модели систем управления»

 
Посмотреть оригинал
< Предыдущая   СОДЕРЖАНИЕ   Следующая >
 

Популярные страницы