Дискретная математика

Очевидно, что у звёздного графа K1;n n висячих вершин (deg(vi) = 1) и одна вершина степени n.

181

Глава 10

Деревья

10.1Определение и свойства деревьев

Определение 10.1. Дерево - это связный граф без циклов. Лес - граф, компонентами которого являются деревья.

Пример 10.1.

а) Граф G1 - дерево

б) G2 - лес, состоящий из 4 компонентов (деревьев)

G2

в) Граф G3 не является деревом (граф содержит цикл из трех вершин, так называемый "треугольник").

182

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

Лес и дерево обладают многими важными свойствами.

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

Лемма. Ребро в графе является мостом тогда, и только тогда, когда оно не входит ни в один цикл.

Доказательство.

Необходимость. Пусть некоторое ребро ei является мостом. Докажем, что не существует цикла, содержащего данное ребро.

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

183

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

Теорема 10.1. Граф является лесом тогда, и только тогда, когда каждое ребро графа - мост.

Доказательство. По определению, лес - граф без циклов. Значит, ни одно ребро не входит ни в какой цикл, то есть все ребра - мосты.

Теорема 10.2. Граф G является деревом тогда и только тогда, когда любые две его вершины соединены ровно одной простой цепью.

Доказательство.

Необходимость. Пусть G - дерево. Докажем, что любые его две вершины vi и vj соединены ровно одной простой цепью.

В силу связности дерева существует хотя бы один маршрут из vi в vj. Предположим, что таких путей по меньшей мере два. Объединив маршруты, получаем цикл - противоречие с определением дерева.

Достаточность. Докажем, что, если в графе G любые две вершины vi и vj соединены ровно одной простой цепью, то G - дерево.

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

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

Теорема 10.3. В каждом дереве число вершин на единицу больше числа ребер.

184

Доказательство. Пусть G - дерево с n вершинами.

Согласно теореме 10.1 каждое ребро дерева является мостом. Удаление каждого моста, согласно определению 10.2, увеличивает количество компонент связности на 1.

Так как дерево - связный граф, то исходный граф G имеет одну компоненту связности. Удалив любое ребро, получаем 2 компоненты связности. Удалив 2 моста, имеем 3 компоненты связности. В общем случае, удалив i ребер, получаем i + 1 компоненту связности.

Итак далее, удалив все мосты, получаем n компонент связности

-изолированных вершин. Значит, процедуру удаления применяли к

n −1 мосту. Таким образом, в исходном графе G было n −1 ребро.

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

Теорема 10.4. Для графа G с n вершинами следующие утверждения эквивалентны:

1.G - дерево;

2.G не содержит циклов и имеет n − 1 ребро;

3.G связен и имеет n − 1 ребро;

4.G связен и каждое его ребро является мостом;

5.G не содержит циклов, но добавление любого ребра приводит к образованию ровно одного цикла.

Следствие 10.4.1. В дереве, содержащем не менее двух вершин, по крайней мере две вершины являются висячими.

10.2Остовные деревья

Определение 10.3. Остовом (остовным деревом) графа G называется подграф T , являющийся деревом и содержащий все вершины графа G.

185

Пример 10.3.

Деревья T1, T2 и T3 - остовы графа G.

Теорема 10.5. У каждого связного графа G существует подграф T , который является остовным деревом.

Доказательство. Пусть граф G содержит цикл. Если ребро {vi, vj} входит в цикл, то существует по крайней мере два маршрута из vi в vj. Удалим ребро {vi, vj}, маршрут из vi в vj все равно существует. Если, после удаления ребра, граф еще содержит цикл, удалим ребро {vk, vs}, входящее в цикл. Будем удалять ребра, пока все циклы не будут удалены. Поскольку количество ребер в графе конечно, процесс удаления также конечен.

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

Определение 10.4. Граф называется взвешенным, если каждому его ребру e поставлено в соответствие неотрицательное число λ(e) -

вес ребра.

Весом графа G =< V, E > называют сумму весов всех его ребер:

∑

λ(G) = λ(e)

e E

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

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

186

Рассмотрим задачу.

Имеется n пунктов, которые объединяют в единую телефонную сеть. Для любых двух пунктов vi и vj известна стоимость прокладки кабеля lij. Требуется проложить кабель таким образом, чтобы любые два пункта имели телефонную связь, и при этом суммарная стоимость прокладки кабеля была бы минимальной.

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

Существует несколько методов построения минимального остова простого связного взвешенного (не обязательно полного) графа G. Мы рассмотрим два из них - алгоритмы Краскала и Прима.

10.2.1Алгоритм Краскала построения минимального остова в графе

Идея метода состоит в том, чтобы создавать дерево T , выбирая ребра

снаименьшим весом так, чтобы не возникал цикл.

1.Упорядочим ребра в порядке возрастания их весов.

2.Включаем в остов все вершины исходного графа.

3.Включаем в остов T первое ребро из списка.

4.Включаем в T следующие в списке ребра заданного графа, не образующие циклов с уже включенными в остов ребрами.

Алгоритм заканчивается, когда в остов включено n − 1 ребро (n - количество вершин в исходном графе).

10.2.2Алгоритм Прима построения минимального остова в графе

Алгоритм похож на предыдущий; различие состоит в том, что строим последовательность деревьев, увеличивая на каждом шаге количество вершин в дереве.

187

1.Возьмем произвольную вершину v1 из множества вершин графа V . Из всех ребер, смежных с v1, возьмем ребро с наименьшим весом. Сформируем дерево T1.

2.Пусть дерево Tk уже сформировано. Если имеется вершина, не принадлежащая Tk, выбираем ребро с наименьшим весом, смежное с ребром дерева Tk. Получили дерево Tk+1.

3.Предыдущий шаг продолжаем, пока есть вершины графа, не принадлежащие остову (то есть до тех пор, пока граф не станет связным).

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

а) алгоритм Краскала;

б) алгоритм Прима.

Решение.

Сначала для удобства обозначим вершины графа. Порядок нумера-

G

188

а) Алгоритм Краскала.

1.Выписываем ребра в порядке возрастания их длин: Ребра длины 2: {v0, v1}, {v0, v2}, {v5, v7};

Ребра длины 3: {v0, v3}, {v1, v2}, {v2, v3}, {v4, v6}; Ребра длины 4: {v1, v4}, {v3, v4}, {v5, v6}, {v6, v7};

Ребра длины 5: {v1, v5}, {v3, v6}, {v4, v5}.

2.Включаем в остов все восемь вершин графа.

3. Включаем в остов ребро {v0, v1} - первое ребро из списка.

4.Включаем в T ребра {v0, v2} и {v5, v7}, так как они не образуют цикла с ребром {v0, v1}. Количество ребер в дереве равно 3.

189

5.Ребро {v0, v3} длины 3 также включаем в остов. Количество ребер 4.

6.Ребра {v1, v2} и {v2, v3} в остов не включаем, так как они образуют циклы с уже включенными в дерево ребрами. Ребро {v4, v6} не образует цикла с ребрами из T , включаем его в остов. Количество ребер в T равно пяти.

7.Ребро {v1, v4} длины 3 включаем в остов, а ребро {v3, v4} - нет (образуется цикл). Ребро {v5, v6} включаем в остов.

Количество ребер на данном этапе работы алгоритма равно 7, что ровно на единицу меньше, чем количество вершин. Ал-

190