Деревья

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

Деревом называется связный граф, не содержащий циклов. Любой граф без циклов называется ациклическим (или лесом). Таким образом, компонентами леса являются деревья. На рисунке 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 удаление любого ребра из Т разбивает множество вершин дерева Т на два непересекающихся подмножества V₁ и V₂. Множество всех ребер графа G, каждое из которых соединяет вершину из V₁ с вершиной из V₂, является разрезом графа G. Множество всех разрезов, полученных таким способом (т. е. удалением по отдельности каждого ребра из Т), называется фундаментальной системой разрезов, ассоциированной с Т. Ясно, что разрезы данной фундаментальной системы должны быть различными и что их число должно равняться коциклическому рангу графа G. Фундаментальной системой разрезов графа, изображенного на рис., ассоциированной с остовным деревом, изображенным на рис, является такая система: {e₁, е₅}, {е₂, е₅, е₇, е₈}, {е₃, е₆, е₇, е₈} и {е₄, е₆, е₈}.

Глава 5. Планарность и двойственность

Планарные графы

Будем говорить, что граф укладывается на поверхности S, если его можно так нарисовать на S, что никакие два его ребра не пересекаются. Граф называется планарным, если его можно уложить на плоскости; плоский граф — это граф, уже уложенный на плоскости. Например, кубический граф, показанный на рисунке 35а, планарный, поскольку он изоморфен плоскому графу, изображенному на рисунке 35б.

Рисунок 35 (а, б)

Очевидно, что если граф имеет петли или параллельные ребра, то ни в какой из его планарных укладок нельзя изобразить все ребра в виде отрезков прямых линий. Здесь, естественно, возникает вопрос: для каждого ли планарного графа G существует укладка, в которой все ребра могут быть изображены в виде отрезков прямых? Как устанавливается в следующей теореме, ответ на данный вопрос – положительный.

Теорема 4. Для каждого простого планарного графа существует планарная укладка, в которой все ребра графа можно изобразить в виде отрезков прямых линий.▪

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

Допустим, что мы положили сферу на плоскость. Назовем точку соприкосновения южным полюсом, а диаметрально противоположную точку на сфере — северным полюсом N. Пусть P — произвольная точка на сфере. Тогда точка Р', в которой прямая, соединяющая точки N и Р пересекает плоскость, называется стереографической проекцией точки P на плоскости. Очевидно, что между точками на сфере и их стереографическими проекциями на плоскости существует взаимно-однозначное соответствие.

Теорема 5. Граф G укладывается на плоскости тогда и только тогда, когда он укладывается на сфере.

Доказательство. Пусть G' — укладка графа G на сфере. Положим сферу на плоскость так, чтобы северный полюс не был ни вершиной, ни точкой на ребре укладки G'.

Тогда образ G' в стереографической проекции — это укладка графа G на плоскости, поскольку ребра укладки G' пересекаются только в своих концевых вершинах, а между точками на сфере, и их образами в стереографической проекции существует взаимно однозначное соответствие. Обратное доказывается аналогично. ▪

Два основных непланарных графа, называемые графами Куратовского, представлены на рисунке 36. Один из них К₅ — полный граф на пяти вершинах, а другой — К_{3, 3}. Называем эти графы основными непланарными графами потому, что они играют основополагающую роль в характеризации планарности.

Рисунок 36 (а – К₅, б – К_{3, 3})