37. Деревья

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

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

Рисунок 32

В следующей теореме перечислены некоторые простые свойства деревьев.

Теорема 2. Пусть граф Т имеет n вершин. Тогда следующие утверждения эквивалентны: (i) Т является деревом; (ii) Т не содержит циклов и имеет n — I ребер; (iii) Т связен и имеет n — 1 ребер; (iv) Т связен и каждое его ребро является мостом; (v) любые две вершины графа Т соединены ровно одной простой цепью; (vi) Т не содержит циклов, но, добавляя к нему любое новое ребро, мы получаем ровно один цикл.

Доказательство. Если n = 1, утверждение очевидно. Предположим поэтому, что п > 2.

(i) =>(ii). По определению Т не содержит циклов; тогда удаление любого ребра разбивает Т на два графа, каждый из которых является деревом. По индуктивному предположению число ребер в каждом из этих деревьев на единицу меньше числа вершин. Отсюда выводим, что полное число ребер графа Т равно n — 1.

(ii) => (iii). Если граф Т несвязен, то каждая его компонента представляет собой связный граф без циклов. Из предыдущей части доказательства следует, что число вершин в каждой из компонент больше числа ее ребер на единицу. Значит, полное число вершин графа Т больше полного числа его ребер по крайней мере на 2, а это противоречит тому, что Т имеет n — 1 ребер.

(iii) => (iv). Удаление любого ребра приводит к графу с n вершинами и n — 2 ребрами, который не может быть связным.

(iv) =>(v). Так как Т связен, то каждая пара его вершин соединена по крайней мере одной простой цепью. Если же данная пара вершин соединена двумя простыми цепями, то они замыкаются в цикл, а это противоречит тому, что каждое ребро в Т является мостом.

(v)=>(vi). Если T содержит цикл, то любые две вершины этого цикла соединены по крайней мере двумя простыми цепями. Добавим теперь к графу Т какое-то ребро е. Тогда мы получим цикл, поскольку инцидентные ребру е вершиныуже соединены в Т простой цепью.

(vi)=>(i). Предположим, что Т несвязен; тогда добавление любого ребра, соединяющего вершину одной компоненты с вершиной другой компоненты, не приводит к образованию цикла. ▪

Следствие. Пусть G — лес с п вершинами и k компонентами; тогда G имеет п — k ребер.

Доказательство. Применим к каждой компоненте графа G предложение (ii) теоремы 1. ▪

Заметим, что по лемме о рукопожатиях сумма степеней всех n вершин дерева равна удвоенному числу его ребер(2n — 2); отсюда следует, что при n> 2 дерево, имеющее n вершин, всегда содержит не менее двух висячих вершин. Известно, что в связном графе G удаление одного ребра, принадлежащего некоторому выбранному циклу, не нарушает связности оставшегося графа. Применим эту процедуру к одному из оставшихся циклов, и так до тех пор, пока не останется ни одного цикла. В результате получим дерево, связывающее все вершины графа G; оно называется Остовным деревом (или остовом, каркасом) графа G. Пример графа и одного из его остовных деревьев дан на рисунке 33.

Рисунок 33

В общем случае обозначим через G произвольный граф с n вершинами, m ребрами и k компонентами. Применяя описанную выше процедуру к каждой компоненте G, получим в результате граф, называемый остовным лесом. Число удаленных в этой процедуре ребер называется циклическим рангом (или цикломатическим числом) графа G и обозначается через γ(G). Очевидно, что γ (G) = m — n + k и является неотрицательным целым числом.

Таким образом, циклический ранг дает меру связности графа: циклический ранг дерева равен нулю, а циклический ранг циклического графа равен единице, удобно также определить коциклический ранг (или ранг разреза) графа G как число ребер в его остовном лесе; коциклический ранг обозначается через χ(G) и равен n — k.

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

Теорема 3. Если Т — остовный лес графа G, то (i) всякий разрез в G имеет общее ребро с Т; (ii) каждый цикл в G имеет общее ребро с дополнением Т.

Доказательство. (i) Пусть С* — разрез графа G, удаление которого разбивает одну из компонент G на два подграфа H и К. Поскольку Т — остовный лес, в нем должно содержаться ребро, соединяющее вершину из H с вершиной из К; это и есть требуемое ребро.

(ii) Пусть С — цикл в графе G, не имеющий ни одного общего ребра с дополнением Т; тогда С содержится в Т, что невозможно. ▪

C понятием остовного леса 7 графа О тесно связано понятие Фундаментальной системы циклов, ассоциированной с Т. Оно определяется следующим образом: если добавить к Т любое не содержащееся в нем ребро графа G, то по предложению (vi) теоремы 1 получим единственный цикл; множество всех циклов, получаемых таким способом (т. е. путем добавления по отдельности каждого ребра из G, не содержащегося в Т), называется Фундаментальной системой циклов, ассоциированной с T. В том случае, когда нас не интересует, какой остовный лес рассматривается, мы говорим о фундаментальной системе циклов графа G. Ясно, что циклы данной фундаментальной системы должны быть различными и что их число должно равняться циклическому рангу графа G. На рисунке 34 показана фундаментальная система циклов графа ассоциированная с остовным деревом:

Рисунок 34

Можно определить фундаментальную систему разрезов графа G, ассоциированную с данным остовным лесом Т. Покажем, что это действительно можно сделать. По предложению (iv) теоремы 1 удаление любого ребра из Т разбивает множество вершин дерева Т на два непересекающихся подмножества V1 и V2. Множество всех ребер графа G, каждое из которых соединяет вершину из V1 с вершиной из V2, является разрезом графа G. Множество всех разрезов, полученных таким способом (т. е. удалением по отдельности каждого ребра из Т), называется фундаментальной системой разрезов, ассоциированной с Т. Ясно, что разрезы данной фундаментальной системы должны быть различными и что их число должно равняться коциклическому рангу графа G. Фундаментальной системой разрезов графа, изображенного на рис., ассоциированной с остовным деревом, изображенным на рис, является такая система: {e1, е5}, {е2 ,е5, е7 ,е8}, {е3, е6, е7, е8} и {е4, е6, е8}.

< Предыдущая		Следующая >