«Учебник по дискретной математике. Деревья и их простейшие свойства»

Деревом называется связный граф без контуров (а значит, и без циклов). Граф (несвязный), состоящий из нескольких деревьев иногда называют лесом.

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

Докажем сейчас следующую достаточно важную теорему.

Теорема. Если граф G является деревом, то число его ребер (т) и число его вершин (п) связаны соотношением т = п – 1.

Доказательство этой теоремы проведем по индукции по числу вершин. Если данный граф содержит всего 2 вершины, то в нем только 1 ребро, и нужное соотношение выполнено. Пусть наше утверждение выполнено для любого дерева, число вершин которого строго меньше п, Докажем его для дерева G, содержащего п вершин. Возьмем висячую вершину дерева G и удалим ее из графа (вместе с единственным ребром, выходящим из этой вершины). Тогда новый граф также является деревом: новый граф не содержит контуров (циклов), он остается связным. (Если бы новый граф оказался несвязным, то какие-то две вершины графа G были бы связаны между собой через удаленную (висячую) вершину. В этом случае степень этой висячей вершины была бы больше или равна 2, что невозможно). Таким образом, новый граф является деревом, и по индукционному предположению для него число ребер меньше числа вершин на единицу. Так как число вершин и число ребер нового графа отличается от числа вершин и ребер “старого” графа G на единицу, то для графа G также выполнено то же самое соотношение. Таким образом, индукция проведена, и теорема доказана.

На самом деле верно и обратное утверждение, которое является частью более общей теоремы, отражающей простейшие свойства дерева.

Теорема. Следующие 4 условия равносильны:

• граф G является деревом;
• число ребер (т) и число вершин в графе (п) связаны соотношением т = п – 1;
• любые две вершины в графе могут быть связаны (простым) путем, и этот путь единствен;
• граф G связен и не содержит контуров.

Заметим, что генеалогическое дерево (в котором вершины графа – это некоторый человек и его прямые предки, а смежные вершины – это люди, связанные родством: мать и ее ребенок или отец и его ребенок) деревом в смысле теории графов не является (так как оно обязательно должно содержать циклы: некоторые предки данного человека должны иметь общего предка).

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