Тексты лекций / Текст лекции 10

§ 3.3. Деревья

Дерево. Лес (ациклический граф). Остовный подграф. Остов. Взвешенный граф. Минимальный остов. Кодирование деревьев.

Базовые понятия и утверждения

1. Определение и основные свойства деревьев.

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

считается деревом.

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

Пример 1. Граф (рис. 3.19) не является ни деревом, ни лесом. Граф (рис. 3.20) - дерево. Граф (рис. 3.21) - лес, состоящий из четырех деревьев.

Рис. 3.19. Рис. 3.20. Рис. 3.21.

Пример 2. Представьте диаграммами все (с точностью до изоморфизма) деревья с пятью вершинами.

◄Имеется три различных (сточностью изоморфизма) дерева с пятьювершинами (рис.

3.22- 3.24). ►

Рис. 3.22. Рис. 3.23. Рис. 3.24.

Упражнение 3.15. Представить диаграммами все (с точностью до изоморфизма) деревья с шестью вершинами.

Деревья обладают рядом характеристических свойств, по наличию или отсутствию каждогоихкоторыхврассматриваемомграфе = ( ,)можноопределить,являетсяграф деревом или нет. Перечислим эти свойства:

1) граф - дерево в том и только в том случае, когда в нем нет циклов и | | = | |−

1;

2)граф - дерево в том и только в том случае, когда он связный и | | = | |− 1;

3)граф - дерево в том и только в том случае, когда он связный, и каждое его ребро является мостом;

4)граф - дерево в том и только в том случае, когда любые две вершины графа можно соединить простой цепью, притом единственной;

1

Тема 10. «Деревья и леса» Олейник Т.А., 2020

5) граф - дерево в том и только в том случае, когда в нем нет циклов и добавление к нему нового ребра приводит к образованию единственного простого цикла.

Также приведем одно из характеристических свойств леса: граф = ( ,), имеющий

компонент связности, является лесом в том и только в том случае, когда | | = | |− .

Упражнение 3.16.Представитьдиаграммамивселесастремяребрамиишестьювершинами.

2. Остовы графа. Подграф графа называется остовным подграфом, если множество его вершин совпадает с множеством вершин графа .

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

Пусть = ( ,) - связный граф. Если содержит хотя бы один цикл, то удалив из графа некоторое ребро этого цикла, мы уменьшим число циклов графа по крайней мере на единицу, сохранив при этом его связность. Ясно, что, последовательно разрушая циклы данного графа, можно прийти к остову графа. Поскольку дерево с | | вершинами имеет ровно| |− 1ребро,тодляполучения остованужноудалитьизграфа | |− (||− 1)ребро, т.е. число ребер, равное цикломатическому числу ( ) связного графа .

Пусть теперь = ( ,) - произвольный граф с компонентами связности. Из каждой компоненты связности = (, ) этого графа удалим | | − | |+1 ребро так, чтобы получился остов этой компоненты. В результате получим некоторый остовный лес графа . Подсчитаем общее число ребер, которое нам пришлось для этого удалить. Сложив равен-

ства | | − | | +1, 1 ≤ ≤ , получим:

∑ (| |− | |+1) = ∑ | |− ∑ | | + = | | − | |+ = ( ).

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

Пример 3. Построимостовграфа ,диаграммакоторогоизображенанарис.3.25.Уда-

2

где ( ) - матрица смежности графа, соответствующая данному упорядочению вершин. Справедливы следующие утверждения:

1)алгебраические дополнения всех элементов матрицы Кирхгофа графа равны между

собой;

2)число остовов в связном неодноэлементном обыкновенном графе равно алгебраическому дополнению любого элемента его матрицы Кирхгофа.

Доказательство этих утверждений опустим.

Пример 4. Найдем число остовов в полном графе с помеченными вершинами и представим их диаграммами.

◄ Пометим вершины графа (рис. 3.29) и выпишем для полученного графа матрицу Кирхгофа:

Найдем алгебраическое дополнение к элементу матрицы , стоящему на пересечении первой строки и первого столбца (элемент взят нами произвольно):

Таким образом, число помеченных остовов в полном графе с тремя вершинами равно 3. Их диаграммы изображены на рис. 3.30 - 3.32. ►

Упражнение 3.18. Найти число остовов, а также сами остовы в помеченном графе

, .

3. Построение минимального остова. Взвешенным графом называется граф, на мно-

жестве ребер которого задано отображение : → [0;+∞), приписывающее каждому ребру неотрицательное число ( ).

Число ( ) называется весом ребра , число ( ) = ∑ ( ) - весом графа . Остов связного взвешенного графа называют минимальным остовом, если для лю-

бого остова выполнено неравенство ( ) ≤ .

Опишем алгоритм построения минимального остова в связном взвешенном графе,

предложенный Дж. Краскалом в 1956 г. Пусть - связный взвешенный граф.

0-й шаг. Строим остовный подграф графа , множество ребер которого пусто.

3

4. Кодирование деревьев. Выделим в дереве какую-нибудь одну вершину, которую назовем корнем. Полученное дерево с выделенной вершиной называется корневым.

4

Для задания (с точностью до изоморфизма) корневых деревьев используют бинарный код (из 0 и 1), который мы определим индуктивно.

Определение. Бинарным кодом корневого дерева с одним ребром является последовательность (01). Пусть деревья и с корнями a и b соответственно (рис. 3.40) имеют коды и .Тогдакодомдерева скорнемсявляетсякод(0 1),акодомдерева скорнем

= = - код .

Рис. 3.40.

Пример 6. Построить бинарный код дерева, изображенного на рис. 3.41.

Рис. 3.41.

◄ Этапы построения кода отражены на рис. 3.41. Код дерева -

(00010101100100101111).►

Упражнение 3.20. Построить бинарный код дерева, изображенного на рис. 3.42.

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

Например, последовательность (0011101001) не может быть бинарным кодом дерева, поскольку в отрезке 00111 из пяти первых цифр этой последовательности единиц больше, чем нулей.

Чтобы построить корневое дерево по коду из нулей и единиц, нужно разбить после-

довательность на пары 0 и 1, следуя правилу: первая попавшаяся в коде единица образует пару с предшествующим нулем; каждая следующая единица образует пару с ближайшим

5

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

Пример 7. Построить дерево по коду (010010010111010011).

◄Разобьем элементы последовательности на пары: 010010010111010011 и по-

строим дерево (рис. 3.43).► Упражнение 3.21. Построить дерево по коду (001000111011).

Для задания деревьев c занумерованными вершинами используют код из натуральных чисел (код Прюфера).

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

Пример 8. Построить код Прюфера для дерева, изображенного на рис. 3.44. ◄ Применим описанный выше алгоритм:

37

наименьшим номером - это 3. Записываем смежную с ней вершину 2 в конец строящегося кода - 22. Удаляем ребро с концами 3, 2 и получаем дерево, изображенное на рис. 3.45,б.

3-й шаг. У дерева на рис. 3.45,б висячая вершина с наименьшим номером - это 2. Записываем смежную с ней вершину 4 в конец строящегося кода - 224. Удаляем ребро с концами 2, 4 и получаем дерево, изображенное на рис. 3.45,в.

4-й шаг. У дерева на рис. 3.45,в висячая вершина с наименьшим номером - это 5. Записываем смежную с ней вершину 4 в конец строящегося кода - 2244. Удаляем ребро с концами 5, 4 и получаем дерево, изображенное на рис. 3.45,г.

5-й шаг. У дерева на рис. 3.45,г висячая вершина с наименьшим номером - это 4. Записываем смежную с ней вершину 6 в конец строящегося кода - 22446. Удаляем ребро с концами 4, 6 и получаем дерево, изображенное на рис. 3.45,д.

6-й шаг. У дерева на рис. 3.45,д висячая вершина с наименьшим номером - это 7. Записываем смежную с ней вершину 6 в конец строящегося кода - 224466. Удаляем ребро с концами 6, 7 и получаем дерево, изображенное на рис. 3.45,е.

Таким образом, код дерева, изображенного на рис. 3.44 - [2 2 4 4 6 6]. ►

6

77

Упражнение 3.22. Построить код Прюфера для дерева, изображенного на рис. 3.46.

3

15

6

9

Рис. 3.46.

Построение дерева по коду из натуральных чисел рассмотрим на примере кода

[2 2 4 4 6 6]. Прежде всего заметим, что дерево, которое нам предстоит построить, имеет 8 вершин.

(32), (24), (54), (46), (76). Каждая такая пара - это пара концов одного из ребер дерева. Этот список дополним парой вершин, отсутствующих в предпоследней строчке, т.е. парой (6,8). Теперь построим дерево: отметим на плоскости точки - вершины дерева и соединим их ребрами согласно списку (см. рис. 3.47).

Упражнение 3.23. Построить дерево по коду [2 2 5 5 5 5].

Теоретические обоснования

Теорема 3.4 (о характеристических свойствах деревьев). Для графа = ( , ) сле-

дующие утверждения равносильны:

1)граф - дерево;

2)ациклический и | | = | |− 1;

3)связный и | | = | |− 1;

7

4)связный, и каждое его ребро является мостом;

5)любыедвевершиныграфа можносоединить простойцепью,притом единственной;

6)ациклический, и добавление к нему нового ребра приводит к образованию единственного простого цикла.

Доказательство. Доказательство проведем по следующей схеме: 1 2 3 4 5 6 1.

1 2. Индукцией по числу ребер проверим, что для любого дерева выполняется ра-

венство | | = | |− 1.

Базис индукции. Пусть | | = 0, тогда | | = 1, и равенство | | = | | − 1выполнено. Индуктивный переход. Предположим, что требуемое равенство выполняется для любого дерева с числом ребер, меньшим либо равным . Докажем, что оно справедливо и для дерева с числом ребер + 1. Удалим из графа произвольное ребро   . Согласно свойству мостов (см. теорему о мостах и циклах из параграфа 3.2), ребро   - мост. По теореме о мостах, ( − ) = ( )+1 = 2. Следовательно, граф − состоит из двух ком-

понент связности = ( , )и = ( , ), каждая из которыхдеревос числом ребер, меньшим либо равным . Для каждой компоненты связности справедливо предположение

2 3. Докажем, что если граф = ( , ) ациклический и | | = | |− 1, то граф связный. Будем рассуждать от противного, т.е. предположим, что найдется ациклический граф, число ребер которого на единицу меньше числа вершин, который связным не является. Пусть , ≥ 2, - число компонент связности графа . Каждая компонента связности - дерево. Переход 1 2 уже доказан, следовательно, для каждой компоненты связности =

Так как ≥ 2, то пришли к противоречию с условием | | = | |− 1. Следовательно, наше предположение было неверным.

3 4. Докажем, что если граф связный и | | = | |− 1, то каждое его ребро является мостом. Будем рассуждать от противного. Предположим, что найдется связный граф = ( , ),укоторого| | = | | − 1и приэтоместьребро  ,неявляющеесямостом.Тогдаграф− связный и

( − ) = | ( − )|− | ( − )| +1 = = (| |− 1) − | |+1 = | |− | | = −1 < 0.

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

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

8

ее с цепью  . В результате получим цикл, содержащий  , а это противоречит тому, что ребро   - мост.

5 6. Пусть для графа выполнено условие 5.

Проверим сначала, что граф не содержит циклов. Будем рассуждать от противного. Предположим, что на графе имеется цикл. Пусть = - одно из ребер этого цикла. Тогда -однапростаяцепь,соединяющаявершины и ,ачастьциклазавычетомребрадругая (если = - петля, то имеется также две простые цепи из в : ими является цепь из одной вершины и цепь ). Получили противоречие с условием 5.

Покажем, что добавление к графу нового ребра приводит к образованию цикла, причем только одного. Возьмем на графе две произвольные вершины и и соединим их новым ребром  ; получим граф + . По условию на графе имеется единственная простая цепь из в . Склеив ее с цепью , получим на графе + простой цикл. Докажем, что этот цикл единственный. Предположим, что при добавлении ребра   образовалось два простых цикла. Тогда, удалив из каждого из них ребро  , получим на графе две простые цепи из в , а наличие двух таких цепей противоречит условию 5.

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

Следствие. Неодноэлементное дерево имеет не менее двух висячих вершин.

Доказательство. Рассмотрим произвольное дерево, имеющее не менее двух вершин. Представим множество его вершин в виде = ( \вис) вис, где вис - множество висячих вершин этого дерева. Тогда

Но | | = | |− 1, поэтому 2| |− 2 ≥ 2| |− | вис|, откуда | вис| ≥ 2.■

Задачи повышенной сложности

3.21.Опираясьнатеоремуохарактеристическихсвойствахдеревьев,доказать,чтограф= ( ,), имеющий компонент связности, является лесом в том и только в том случае,

когда | | = | |− .

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

3.23.Используя теорему Кирхгофа, показать, что число остовов в полном графе с

помеченными вершинами равно .

9

Тема 10. «Деревья и леса» Олейник Т.А., 2020

Замечание. Любой остов в полном графе с помеченными вершинами - это дерево с вершинами 1,2,3,..., , асовокупность всехтаких остововэто совокупностьвсех деревьев с помеченными вершинами. Отсюда заключаем: число деревьев с помеченными верши-

нами равно (теорема Кэли).

Ответы и указания к упражнениям

Рис. 3.

Рис. 4.

Рис. 5.

3.21. Рис. 6. 3.22. [2 2 4 6 4 2 4]. 3.23. Рис. 7.

Рис. 6. Рис. 7.

10