5.13. Деревья

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

Вершины степени 1 в дереве называются листьями или висячими вершинами. Ребро, инцидентное концевой вершине, будем называть концевым ребром графа.

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

Среди графов n-го порядка (с n вершинами) без кратных ребер полный граф имеет наибольшее количество ребер, а дерево (n-го порядка) - наименьшее. Дерево содержит минимальное количество ребер, необходимое для того, чтобы граф был связным.

Теорема 1. Если граф G является деревом, то число его ребер m и число его вершин n связаны соотношением .

Теорема 2. При удалении любого ребра дерева оно распадается на связные компоненты, являющиеся либо изолированными вершинами, либо деревьями.

Теорема 3. Любые две вершины в графе могут быть связаны (простым) путем, и этот путь единствен.

При добавлении в дерево любого нового ребра в нем образуется простой цикл, и оно перестает быть деревом.

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

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

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

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

Центр дерева — множество вершин графа, для которых эксцентриситет вершины минимален, т.е равен радиусу графа, может состоять из одной или из двух смежных вершин.

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

Пример 5.7. Найти центр, диаметр и радиус графа, изображенного на рис. 35

Сначала удаляются листья-вершины v₁, v₃, v₇, v₈, являющиеся вершинами первого типа. Потом удаляются вновь образованные листья v₂, v₆ – вершины второго типа. Центром дерева являются вершины v₄, v₅. Диаметр графа равен 5, а радиус равен 3.

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

-существует один корень дерева,

-остальные вершины (за исключением корня) распределены среди непересекающихся множеств, и каждое из множеств является корневым деревом; (деревья называются поддеревьями данного корня).

Различают концевой узел (лист, терминальная вершина) и узел ветвления — неконцевой узел.

Уровень узла (номер яруса)— длина пути от корня до узла. Уровень корня дерева равен 0, уровень любого другого узла на единицу больше, чем уровень корня ближайшего поддерева дерева, содержащего данный узел. Наибольшее значение k называется высотой дерева.

Если из вершины v корневого дерева выходят дуги, то вершины на концах этих дуг называются сыновьями, а сама вершина отцом. Вершины, не имеющие сыновей, являются листьями.