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

ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ

Неориентированный граф G = (V, Е) состоит из конечного множества вершин V и мно­жества ребер Е. В отличие от ориентированного графа, здесь каждое ребро (v,w) соот­ветствует неупорядоченной паре вершин: если (v,w) — неориентированное ребро, то (v, w) = (w, v). Далее неориентированный граф мы будем называть просто графом.

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

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

Путем называется такая последовательность вершин v₁,v₂,….,v_n, что для всех i , 1 ≤i < n, существуют ребра (v_i,v_i+1). Путь называется простым, если все вершины пути различны, за исключением, возможно, вершин v₁ и v_n. Длина пути равна количеству ребер, составляющих путь, т.е. длина равна n - 1 для пути из n вершин. Если для вершин v₁ и v_n существует путь v₁,v₂,….,v_n, то эти вершины называются свя­занными. Граф называется связным, если в нем любая пара вершин связанная.

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

1. множество V' является подмножеством множества V,

2. множество Е' состоит из ребер (v, w) множества Е таких, что обе вершины v и w принадлежат V'.

Если множество Е' состоит из всех ребер (v, w) множества Е таких, что обе вершины v и w принадлежат V', то в этом случае граф G' называется индуцированным подграфом графа G.

На рис. 1,а показан граф G = (V, Е) с множеством вершин V = {а, b, c, d} и множеством дуг Е = {(a, b), (a, d), (b, с), (b, d), (с, d)}. На рис. 1,б представ­лен один из его индуцированных подграфов, заданный множеством вершин V' = {а, b. с} и содержащий все ребра, не инцидентные вершине d.

Связной компонентой графа G называется максимальный связный индуцированный подграф графа G.

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

Рис. 1. Граф и один из его подграфов

Рис. 2. Несвязный граф

Циклом (простым) называется путь (простой) длины не менее 3 от какой-либо вершины до нее самой. Мы не считаем циклами пути длиной 0, длиной 1 (петля от вершины v к ней самой) и длиной 2 (путь вида v, w, v). Граф называется циклическим, если имеет хотя бы один цикл. Связный ациклический граф, представляющий собой "дерево без корня", называют свободным деревом. На рис. 2 показан граф, состоящий из двух связных компонент, каждая из которых является свободным де­ревом. Свободное дерево можно сделать "обычным"' деревом, если какую-либо вер­шину назначить корнем, а все ребра сориентировать в направление от этого корня.

Свободные деревья имеют два важных свойства, которые мы будем использовать в следующих разделах.

1. Каждое свободное дерево с числом вершин n, n ≥ 1, имеет в точности n - 1 ребер.

2. Если в свободное дерево добавить новое ребро, то обязательно получится цикл.

Мы докажем первое утверждение методом индукции по n. Очевидно, что утверждение справедливо для n = 1, поскольку в этом случае имеем только одну вершину и не имеем ребер. Пусть утверждение 1 справедливо для свободного дерева с n - 1 вершинами. Рассмотрим дерево G c n вершинами.

Сначала покажем, что в свободном дереве существуют вершины, имеющие одно инцидентное ребро. Заметим, что G не содержит изолированных вершин (т.е. вершин, не имеющих инцидентных ребер), иначе граф G не был бы связным. Теперь создадим путь от некоторой вершины v₁, следуя по произвольному ребру, инцидент­ному вершине v₁. На каждом шаге построения этого пути, достигнув какой-либо вершины, выбираем инцидентное ей ребро, которое ведет к вершине, еще не участво­вавшей в формировании пути. Пусть таким способом построен путь v₁,v₂,….,v_k. Вершина v_k будет смежной либо с одной вершиной v_k-1, либо еще с какой-нибудь, не входящей в построенный путь (иначе получится цикл). В первом случае получаем, что вершина v_k имеет только одно инцидентное ей ребро, и значит, наше утвержде­ние о том, что в свободном дереве существуют вершины, имеющие одно инцидентное ребро, будет доказано. Во втором случае обозначим через v_k+1 вершину, смежную с вершиной v_k , и строим путь v₁,v₂,….,v_k+1. В этом пути все вершины различны (иначе опять получится цикл). Так как количество вершин конечно, то этот процесс закончится за конечное число шагом и мы найдем вершину, имеющую одно инци­дентное ребро. Обозначим такую вершину через v, а инцидентное ей ребро — (v, w).

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

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

ПРЕДСТАВЛЕНИЕ НЕОРИЕНТИРОВАННЫХ ГРАФОВ

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

На рис. 3 показаны матрица смежности и списки смежности, пред­ставляющие граф из рис. 1,a.

	a	b	c	d
a
b
c
d

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

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

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

ОСТОВНЫЕ ДЕРЕВЬЯ МИНИМАЛЬНОЙ СТОИМОСТИ

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

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

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

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

СВОЙСТВО ОСТОВНЫХ ДЕРЕВЬЕВ МИНИМАЛЬНОЙ СТОИМОСТИ

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

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

Поскольку дерево Т - свободное дерево, то из второго свойства свободных деревь­ев следует, что добавление ребра (u, v) к этому дереву приведет к образованию цикла. Этот цикл содержит ребро (u, v) и будет содержать другое ребро (u', v') такое,что u' принадлежит U и , как показано на рис. 5. Удаление ребра (u', v') приведет к раз­рыву цикла и образованию остовного дерева, чья стоимость будет не выше стоимости дерева Т, поскольку с(u, v) ≤ с(u', v'). Мы пришли к противоречию с предположени­ем, что остовное дерево Т — это дерево минимальной стоимости.

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

АЛГОРИТМ ПРИМА

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

Если ввести два массива, то можно сравнительно просто организовать на каждом шаге алгоритма выбор ребра с наименьшей стоимостью, соединяющего множества U и V \ U. Массив CLOSEST[i] для каждой вершины i из множества V\U содержит вершину из U, с которой он соединен ребром минимальной стоимости (это ребро вы­бирается среди ребер, инцидентных вершине i, и которые ведут в множество U). Другой массив LOWCOST[i] хранит значение стоимости ребра (i, CLOSEST[i]).

На каждом шаге алгоритма просматривается массив LOWCOST, находится мини­мальное значение LOWCOST[k]. Вершина k принадлежит множеству V \ U и соеди­нена ребром с вершиной из множества U. Затем выводится на печать ребро (k, CLOSEST[k]). Так как вершина k присоединяется к множеству U, то вследствие этого изменяются массивы LOWCOST и CLOSEST. На вход программы посту­пает массив С размера n х n, чьи элементы C[i][j] равны стоимости ребер (i, j). Если ребра (i, j) не существуют, то элемент C[i][j] полагается равным некоторому достаточ­но большому числу BB.

После нахождения очередной вершины k остовного дерева LOWCOST[k] ложится равным BB (бесконечность), очень большому числу, такому, чтобы эта вершина уже в дальнейшем не рассматривалась. Значение числа BB должно быть больше стоимости любого ребра графа.