Главная Промышленная автоматика.

закончится за конечное число шагом и мы найдем вершину, имеюшую одно инцидентное ребро. Обозначим такую вершину через v, а инцидентное ей ребро - (и, w).

Теперь рассмотрим граф G, полученный в результате удаления из графа G вершины V и ребра (v. w). Граф G имеет п - 1 вершину, для него выполняется утверждение 1 и поэтому он имеет п - 2 ребра. Но граф G имеет на одну вершину и на одно ребро больше, чем граф G, поэтому для него также выполняется утверждение 1. Следовательно, утверждение 1 доказано.

Теперь мы легко докажем утверждение 2 о том, что добавление ребра в свободное дерево формирует цикл. Применим доказательство от противного, т.е. предположим, что добавление ребра в свободное дерево не формирует цикл. Итак, после добавления нового ребра мы получили граф с п вершинами и п ребрами. Этот граф остался связным и, по нашем предположению, ацикличным. Следовательно, этот граф - свободное дерево. Но в таком случае получаем противоречие с утверждением 1. Отсюда вытекает справедливость утверждения 2.

Представление неориентированных графов

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

Пример 7.3. На рис. 7.3 показаны матрица смежности и списки смежности, пред-ставляюшие граф изрис. 7.1,а. D

а Ь

с б

0 1

0 1

1 0

1 1

0 1

0 1

1 0

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

¥ 0 ->

1 ,

1 *

б. Списки смежности

Рис. 7.3. Представления неориентированного графа

Очевидно, что матрица смежности для неориентированного графа симметрична. Отметим, что в случае представления графа посредством списков смежности для су-шествуюшего ребра (i, j) в списке смежности вершины / присутствует вершина а в списке смежности вершины j - вершина /.



7.2. Остовные деревья минимальной стоимости

Пусть G = (V, Е) - связный граф, в котором каждое ребро (v, w) помечено числом c(v, w), которое называется стоимостью ребра. Остовным деревом графа G называется свободное дерево, содержащее все вершины V графа G. Стои.чость остовного дерева вычисляется как сумма стоимостей всех ребер, входящих в это дерево. В этом разделе мы рассмотрим методы нахождения остовных деревьев минимальной стоимости.

Пример 7.4. На рис. 7.4 показаны граф с помеченными ребрами и его остовное дерево минимальной стоимости. О



Рис. 7.4. Граф и его остовное дерево

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

Свойство остовных деревьев минимальной стоимости

Существуют различные методы построения остовных деревьев минимальной стоимости. Многие из них основываются на следующем свойстве остовных деревьев минимальной стоимости, которое для краткости будем называть свойством ОДМС. Пусть G = (V. Е) - связный граф с заданной функцией стоимости, определенной на множестве ребер. Обозначим через U подмножество множества вершин V. Если (и, v) - такое ребро наименьшей стоимости, что и е U я D е V \ и, тогда для графа G существует остовное дерево минимальной стоимости, содержащее ребро (и, v).

Доказать это свойство нетрудно. Допустим противное: существует остовное дерево для графа G, обозначим его Г - (V, Е), содержащее множество [/ и не содержащее ребро (и. v), стоимость которого меньше любого остовного дерева для G, содержащего ребро (и, v).

Поскольку дерево Г - свободное дерево, то из второго свойства свободных деревьев следует, что добавление ребра (и, v) к этому дереву приведет к образованию цикла. Этот цикл содержит ребро (и, v) и будет содержать другое ребро (и. v) такое, что u%UveV\U, как показано на рис. 7.5. Удаление ребра (и, v) приведет к разрыву цикла и образованию остовного дерева, чья стоимость будет не выше стоимости дерева Г, поскольку с(и, v) < с(и. v). Мы пришли к противоречию с предположением, что остовное дерево Г - это дерево минимальной стоимости.




Рис. 7.5. Цикл в остовном дереве

Алгоритм Прима

Существуют два популярных метода построения остовного дерева минимальной стоимости для помеченного графа G = (V, Е), основанные на свойстве ОДМС. Один такой метод известен как алгоритм Прима (Prim). В этом алгоритме строится множество вершин f/, из которого "вырастает" остовное дерево. Пусть V= {1, 2, п). Сначала и = {1}. На каждом шаге алгоритма находится ребро наименьшей стоимости (и, v) такое, что и е U п v е V \ U, затем вершина v переносится из множества V \U в множество U. Этот процесс продолжается до тех пор, пока множество U не станет равным множеству V. Эскиз алгоритма показан в листинге 7.1, а процесс построения остовного дерева для графа из рис. 7.4,а - на рис. 7.6.

Листинг7.1. Алгоритм Прима

procedure Prm { G: граф; var Т: множество ребер ); var

U: множество вершин; и, v. вершина; begin

Г;= 0; V- {1};

while и Ф V йо begin

нахождение ребра (и, v) наименьшей стоимости и такого,

что U £ У и V € V\Ui Т:= Г U {{и, V) ); U:= и и {v)

end; { Prim }

Если ввести два массива, то можно сравнительно просто организовать на каждом шаге алгоритма выбор ребра с наименьшей стоимостью, соединяющего множества U и У\ и. Массив СЬ08Е8Т[1]для каждой вершины / из множества У\ U содержит вершину из и, с которой он соединен ребром минимальной стоимости (это ребро выбирается среди ребер, инцидентных вершине /, и которые ведут в множество U). Другой массив LOWCOST[г]хранит значение стоимости ребра (i, CLOSESTli]).

На каждом шаге алгоритма просматривается массив LOWCOST, находится минимальное значение LOWCOSTih]. Вершина к принадлежит множеству V \ U п соединена ребром с вершиной из множества U. Затем выводится на печать ребро (к, CLOSEST[k\).lAK как вершина к присоединяется к множеству U, то вследствие этого изменяются массивы LOWCOST и CLOSEST. Программа на языке Pascal, реализующая алгоритм Прима, представлена в листинге 7.2. На вход программы посту-





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 [66] 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123

0.0018