Лекция 20. Плоские графы. Деревья и их свойства

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

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

 

Рис. 1 Деревья шестого порядка.

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

Теорема. Пусть граф Т имеет 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. Пример графа и одного из его остовных деревьев дан на рисунке 2.

Рис. 2. Граф и одно из его остовных деревьев

В общем случае обозначим через 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. На рисунке 3 показана фундаментальная система циклов графа ассоциированная с остовным деревом:

 

Рис. 3. Фундаментальная система циклов графа ассоциированная с остовным деревом:

Можно определить фундаментальную систему разрезов графа G, ассоциированную с данным остовным лесом Т. Покажем, что это действительно можно сделать. По предложению (iv) теоремы 1 удаление любого ребра из Т разбивает множество вершин дерева Т на два непересекающихся подмножества V₁ и V₂. Множество всех ребер графа G, каждое из которых соединяет вершину из V₁ с вершиной из V₂, является разрезом графа G. Множество всех разрезов, полученных таким способом (т. е. удалением по отдельности каждого ребра из Т), называется фундаментальной системой разрезов, ассоциированной с Т. Ясно, что разрезы данной фундаментальной системы должны быть различными и что их число должно равняться коциклическому рангу графа G. Фундаментальной системой разрезов графа, изображенного на рис., ассоциированной с остовным деревом, изображенным на рис, является такая система: {e₁, е₅}, {е₂, е₅, е₇, е₈}, {е₃, е₆, е₇, е₈} и {е₄, е₆, е₈}.