Деревья

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

Теорема. Связный граф является деревом тогда и только тогда, когда число его вершин на единицу больше числа его ребер, т.е. .

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

Далее доказательство проведем индукцией по числу вершин п. При п = 1 число ребер равно 0 и утверждение верно. Предположим оно верно при любом количестве вершин, меньшем п. Рассмотрим граф G с п вершинами. Среди них есть висячая. Рассмотрим подграф G', порожденный множеством остальных вершин. Для него по индукционному предположению .

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

Свойства деревьев.

1. Любые две вершины дерева можно соединить путем. Если это простой путь, то он единственный.

2. Если для некоторого дерева G V(G) ? 2, то оно имеет не менее двух висячих вершин.