1. Ребро с произвольного графа G называется циклическим, если оно принадлежит хотя бы одному элементарному циклу в графе, и ациклическим в противном случае. Примером ациклического ребра является висячее. Справедливы два простых утверждения:
1) при удалении из связного графа циклического ребра граф остается связным;
2) при удалении ациклического ребра граф становится несвязным.
Первое подтверждается возможностью для любой цепи заменить циклическое ребро цепью из остальных ребер цикла. Второе доказывается от противного: если бы граф оставался связным, то концы удаленного ребра были бы связаны элементарной цепью; возвратив удаленное ребро, получили бы элементарный цикл вопреки тому, что ребро ациклическое. Связный граф без циклов называется деревом. Иначе говоря, дерево - это граф, все ребра которого ациклические. Имеется несколько эквивалентных определений дерева, устанавливающих ряд его характеристических свойств, подробнее рассмотренных ниже:
2. Выберем в дереве произвольную вершину а0 и назовем корнем, или вершиной нулевого яруса. Соседние вершины назовем вершинами первого яруса и т.д. - вершины, соседние вершинам (i - 1)-го яруса, не отнесенные еще ни к одному ярусу, назовем вершинами i-гo яруса. Каждая вершина дерева принадлежит ровно одному ярусу.
Очевидно, что номер яруса совпадает с расстоянием между его вершинами и корнем дерева. В силу свойства (3) каждая вершина i-гo яруса связана ребром ровно с одной вершиной (i - 1)-го яруса и не вязана ребром ни с какой вершиной i-гo яруса (рисунок 5). Такое представление дерева часто является удобным. Оно показывает, в частности, что в конечном дереве всегда существуют концевые вершины (например, вершины последнего яруса, но, возможно, и другие).
![]() |
Рисунок 5 |
Выделение корня в дереве D определяет на множестве его вершин частичный порядок: < β, если
≠ β и элементарная цепь из корня в вершину β содержит
(рисунок 6). Корень
0 является единственным минимальным элементом в этом частично упорядоченном множестве вершин, а все концевые вершины (исключая корень: он может быть, но может и не быть концевой вершиной) - максимальными. Каждая вершина
однозначно определяет корневое поддерево D
, натянутое на множество таких вершин β, что
< β каждом таком поддереве D
(в том числе в D
0 = 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,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 - деревья.
Ребра остова | Комментарий | |
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 |
![]() |
Tест для самоконтроля |