5.4-5 Проверьте, что отношение «быть достижимым из» является (для неориентированного графа) отношением эквивалентности. Какие из трёх свойств, входящих в определение отношения эквивалентности, справедливы для отношения достижимости в ориентированном графе?

5.4-6 Нарисуйте неориентированную версию графа рис. 5.2 (а) и ориентированную версию графа рис. 5.2 (б).

5.4-7* Как можно представить гиперграф с помощью двудольного графа, изображая отношение инцидентности в гиперграфе отношением смежности в двудольном графе? (Указание: вершинами двудольного графа должны быть вершины гиперграфа, а также гиперрёбра гиперграфа.)

5.5. Деревья

Как и слово «граф», слово «дерево» также употребляется в нескольких родственных смыслах. В этом разделе мы даём определения и рассматриваем свойства нескольких видов деревьев. В разделах 11.4 и 23.1 мы вернёмся к деревьям и рассмотрим способы их представления в программах.

5.5.1. Деревья без выделенного корня

Как мы говорили в разделе 5.4, дерево (без выделенного корня, free tree) определяется как связный ациклический неориентированный граф. Если неориентированный граф является ациклическим, но (возможно) несвязным, его называют лесом (forest); как и положено, лес состоит из деревьев (являющихся его связными компонентами). Многие алгоритмы обработки деревьев применимы и к лесам. На рис. 5.4 (а) изображено дерево; на рис. 5.4 (б) изображён лес. Лес рисунка 5.4 (б) не является деревом, так как не связен. Граф на рисунке 5.4 (в) не является ни деревом, ни даже лесом, так как в нём есть цикл.

В следующей теореме указано несколько важных свойств деревьев.

Теорема 5.2 (Свойства деревьев). Пусть G = (V, Е) - неориентированный граф. Тогда следующие свойства равносильны:

1.G является деревом (без выделенного корня).

2.Для любых двух вершин G существует единственный соединяющий их простой путь.

3.Граф G связен, но перестаёт быть связным, если удалить любое его ребро.

Рис. 5.4 (а) Дерево без выделенного корня, (б) Лес. (в) Граф, содержащий цикл, не является ни деревом, ни лесом.

Рис. 5.5 Два простых пути изав»

4- Граф G связен и \Е\ = \V\ - 1.

5.Граф G ациклический и \Е\ = \V\ - 1.

6.Ераф G ациклический, но добавление любого ребра к нему порождает цикл.

Доказательство. (1) => (2): Поскольку дерево связно, для любых двух вершин существует соединяющий их путь; выкинув из него лишнее, можем считать, что этот путь простой. Пусть есть два разных простых пути р\ и р2 из некоторый вершины и в другую вершину v (рис. 5.5). Посмотрим, где эти пути расходятся; пусть w - последняя общая вершина перед разветвлением, ахну - различные вершины, следующие за w в путях р\ и р2. Двигаясь по первому пути, дождёмся момента, когда путь вновь пересекается со вторым в некоторой вершине z. Рассмотрим участок р первого пути от w до z (через х) и участок второго пути р" от w до z (через у). Пути р и р" не имеют общих вершин (не считая концов), поскольку z было первой вершиной на пути р\ после w, попавшей в р2. Поэтому мы получаем цикл (состоящий из р и обращения пути р").

(2)=> (3) Граф, очевидно, связен. Пусть (и, v) - любое его ребро. Если после его удаления граф останется связным, то в нём будет путь, соединяющий и и v - второй путь, что противоречит предположению.

(3)(4) По условию, граф связен, поэтому \Е\ \V\ - 1 (упр. 5.44). Докажем, что \Е\ \V\ - 1, рассуждая по индукции. Связный граф с п = 1, 2 вершинами имеет га - 1 рёбер. Пусть граф G имеет га 3 рёбер и для графов с меньшим числом рёбер наше неравенство уже доказано. Удаление ребра разбивает граф G на k 2 связ-

ных компонент (на самом деле на две, но это нам не важно). Для каждой из компонент выполнено условие (3). Индуктивное предположение гарантирует, что общее число рёбер в них не больше -- 2. Значит, до удаления ребра было не более \V\ - 1

рёбер.

(4)=> (5) Пусть граф связен и \Е\ = \V\-1. Покажем, что граф не имеет циклов. Если цикл есть, удаление любого ребра из цикла не нарушает связности (можно пройти по остающейся части цикла). Будем повторять это до тех пор, пока не останется связный граф без циклов (дерево). Как мы уже знаем, для дерева число рёбер на единицу меньше числа вершин - но по предположению то же соотношение было и до удаления рёбер, так что удалить мы ничего не могли и с самого начала не было циклов.

(5)=> (6) Пусть граф G не имеет циклов и \Е\ = \V\ - 1. Пусть G имеет к связных компонент; они по определению являются деревьями. Мы знаем, что в каждой из них число рёбер на единицу меньше числа вершин, поэтому общее число рёбер на к меньше числа вершин. Значит, к = 1 и граф представляет собой дерево. В нём любые две вершины могут быть соединены простым путём (мы уже знаем, что (1) => (2)), и потому добавление любого ребра порождает цикл.

(6)=> (1) Пусть граф является ациклическим, но добавление любого ребра порождает цикл. Надо показать, что он связен. В самом деле, рассмотрим две произвольные вершины и и v. Мы знаем, что добавление ребра (и, v) порождает цикл. В этом цикле должно встречаться ребро (и, v), поскольку до его добавления цикла не было - но только один раз, и остальная часть цикла соединяет и и v, что и требовалось.□

5.5.2. Деревья с корнем. Ориентированные деревья

Дерево с корнем, или корневое дерево (rooted tree), получается, если в дереве (связном ациклическом неориентированном графе) выделить одну из вершин выделена, назвав её корнем (root). Вершины корневого дерева по-английски называются также «nodes». На рисунке 5.6 (а) показано корневое дерево с 12 вершинами и корнем 7.

Пусть ж - произвольная вершина корневого дерева с корнем в г. Существует единственный путь из г в ж; все вершины, находящиеся на этом пути, мы называем предками (ancestors) вершины ж. Если у является предком ж, то ж называется потомком (descendant) у. Каждую вершину мы считаем своим предком и потомком. Предки и потомки вершины ж, не совпадающие с ж, называются собственными предками (proper ancestors) и собственными потомками (proper descendants) вершины ж. [Эта терминология не вполне удачна: фра-