Определение дерева и его свойства

Введение

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

Принято считать, что первым использовал понятие дерева Кирхгофф в 1847 г. при исследовании электрических цепей. Спустя десять лет химик Кэли ввел термин «дерево» при изучении структуры углеводородных соединений и получил первые важные результаты в этом разделе теории графов.

Определение дерева и его свойства

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

Существует несколько эквивалентных определений неориентированного дерева, каждое из которых отражает различные свойства последнего. Приведем некоторые из них.

Теорема. Следующие определения дерева эквивалентны:

1) дерево – это связный граф без циклов;

2) дерево – это связный граф, в котором каждое ребро является мостом;

3) дерево – это связный граф, цикломатическое число которого равно нулю;

4) дерево – это граф, в котором для любых двух вершин существует ровно одна соединяющая их цепь.

Эти утверждения выводятся одно из другого по схеме 1) 2) 3) 4) 5).

Из свойства 3) имеем: или , то есть в любом дереве число ребер на единицу меньше числа вершин.

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

Так как удаление цикловых ребер можно вести разными способами, то один и тот же граф в общем случае имеет несколько остовных деревьев. На рис. 1. представлен граф и три его остовных дерева.

° ° ° ° ° ° ° ° ° ° ° °

° ° ° ° ° ° ° ° ° ° ° °

° ° ° ° ° ° ° ° ° ° ° °

Рис. 1. Граф и его остовные деревья , и

Ребра графа , не вошедшие в его остовное дерево , называются хордами дерева .

Лемма. В графе для любого остовного дерева и любой хорды этого дерева существует единственный цикл, содержащий хорду и не содержащий других хорд.

Доказательство. Пусть . В дереве имеется единственная цепь, соединяющая вершины и . Присоединяя к этой цепи ребро , получим требуемый цикл.