назад

3.4 Деревья

1. Ребро с произвольного графа G называется циклическим, если оно принадлежит хотя бы одному элементарному циклу в графе, и ациклическим в противном случае. Примером ациклического ребра является висячее. Справедливы два простых утверждения:

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

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

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

  1. связный граф, который становится несвязным при удалении любого ребра;
  2. связный граф, у которого число ребер на единицу меньше числа вершин;
  3. граф, любые две вершины которого связаны единственной; элементарной цепью;
  4. граф без циклов, в котором после добавления ребра; связывающего две любые вершины, появляется цикл.

2. Выберем в дереве произвольную вершину а0 и назовем корнем, или вершиной нулевого яруса. Соседние вершины назовем вершинами первого яруса и т.д. - вершины, соседние вершинам (i - 1)-го яруса, не отнесенные еще ни к одному ярусу, назовем вершинами i-гo яруса. Каждая вершина дерева принадлежит ровно одному ярусу.

Очевидно, что номер яруса совпадает с расстоянием между его вершинами и корнем дерева. В силу свойства (3) каждая вершина i-гo яруса связана ребром ровно с одной вершиной (i - 1)-го яруса и не вязана ребром ни с какой вершиной i-гo яруса (рисунок 5). Такое представление дерева часто является удобным. Оно показывает, в частности, что в конечном дереве всегда существуют концевые вершины (например, вершины последнего яруса, но, возможно, и другие).

Рисунок 5

Выделение корня в дереве D определяет на множестве его вершин частичный порядок: < β, если ≠ β и элементарная цепь из корня в вершину β содержит (рисунок 6). Корень 0 является единственным минимальным элементом в этом частично упорядоченном множестве вершин, а все концевые вершины (исключая корень: он может быть, но может и не быть концевой вершиной) - максимальными. Каждая вершина однозначно определяет корневое поддерево D, натянутое на множество таких вершин β, что < β каждом таком поддереве D (в том числе в D0 = D) можно выделить вершины, непосредственно подчиненные корню поддерева, т.е. такие вершины i, что < i и не существует промежуточных вершин δ, для которых < δi < i. Для каждой такой вершины δ i определим ветвь D I дерева D как корневое поддерево с корнем , натянутое на множество вершин {} {δ : δ }. Все поддерево D получается из своих ветвей склеиванием в корне .
Рисунок 6

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

На рисунке 7а - пример остова (его ребра выделены) графа с 11 вершинами и 18 ребрами. Последовательность циклов и удаляемых из них ребер представлены в таблице 1. Оставшиеся ребра, образующие, остов: 2, 3,4, 7, 10, 11, 12, 15, 17, 18.
aб
Рисунок 7
Таблица 1
ЦиклУдаляемое ребро
[1,9,14]1
[6,7,10]6
[5,13,14]5
[4,12,13]13
[8,11,12]8
[2,9,14,4,3]9
[14,10,11,4]14
[16,17,18]16

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

Для того же графа на рисунке 7б - остов, построенный аналогичным образом. Последовательность присоединяемых ребер, составляющих в конечном счете остов, - в первом столбце таблицы 2. Во втором столбце - ребра, не включаемые в остов на данном этапе построения: комментарий - в третьем столбце. Обратите внимание на то, что ребра, первоначально не присоединенные, могут впоследствии войти в остов (таковы ребра 5, 6, 7).

Ребро 8 отвергается дважды по разным причинам. Ребра 4, 8, 10, 11, 12, 13, 14, 18 - хорды.

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

в любом конечном дереве число ребер на единицу меньше числа вершин.

Обратно, пусто связный граф G с Ь вершинами содержит (b - 1) ребер. Докажем, чго G - дерево в соответствии с характеристическим свойством (2). Действительно, в противном случае, удалив некоторое число q циклических ребер, мы получили бы осгов с b вершинами и (b-1-q) ребрами, что невозможно (так как остов - дерево).

Если к дереву D добавить ребро ( , β), где , β D, то в графе появится (единственный!) элементарный цикл, составленный из этого ребра и (единственной) элементарной цепи [, β] D. Если удалить из дерева D произвольное ребро (, δ), не удаляя вершин, то получится несвязный граф (так как любое ребро дерева - ациклическое), состоящий ровно из двух компонент связности (так как восстановление этого ребра превращает граф в связный). Любой подграф Н дерева не содержит элементарных циклов, поэтому все компоненты связности подграфа H - деревья.

 

Таблица 2
Ребра остова  Комментарий
1
2
3
 
 
 
 
 
9
5
6
7
 
 
 
 
 
 
15
16
17
 
 
 
 
4
5
6
7
8
 
 
 
 
8
10
11
12
13
14
 
 
 
18
 
 
 
образует цикл с ребрами 1,2,3
не смежно ни одному из ранее выбранных ребер
--"--"--"--"--
--"--"--"--"--
--"--"--"--"--
 
 
 
 
образует цикл с ребрами 5,6,7
образует цикл с ребрами 6,7
образует цикл с ребрами 2,3,6,7,9
образует цикл с ребрами 2,3,5,9
образует цикл с ребрами 1,9,5
образует цикл с ребрами 1,9
 
 
 
образует цикл с ребрами 16,17

 

Вопросы для самоконтроля

  1. Дайте определение циклического и ациклического ребра.
  2. Сформулируйте несколько определений дерева.
    Приведите пример.
  3. Дайте определение остова графа G.

Tест для самоконтроля