Древовидные графы. 
Геометрическая теория графов

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

Различные определения деревьев

Определение 1. Деревом называется конечный связный граф без циклов.

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

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

Нам понадобится следующая лемма.

Лемма (о висячей вершине). В любом дереве существует висячая вершина.

Доказательство. Рассмотрим некоторую вершину дерева и обозначим ее через Ао . Эта вершина не может быть изолированной, т. е. g (Aq)>1. Если о (А₀)=1, то Ао — искомая висячая вершина. Пусть а (Ао)> 1, тогда вершина Ао имеет смежную вершину, которую мы обозначим через А,. Для вершины А/, а (А/)> 1. Если а (А])=1, то АI — искомая висячая вершина. Если о (А,)>1, то вершина А/ имеет смежную вершину, отличную от А о.

которую мы обозначим через А2 . Продолжая далее этот процесс, мы получим последовательность различных вершин (так как дерево не имеет циклов). Если бы дерево не содержало висячей вершины, то описанный процесс никогда бы не закончился, и мы получили бы бесконечную последовательность^,^,^,… различных вершин. Но так как дерево является конечным графом, описанный процесс будет конечным, и на какомгто шаге мы придем к висячей вершине.

Пусть дерево G имеет п вершин. Подсчитаем количество ребер. В силу леммы в дереве существует висячая вершина. Удалив эту вершину вместе с инцидентным ей ребром, мы получим подграф Gj дерева G, который имеет на одно ребро и на одну вершину меньше, чем G, и сам является деревом. В дереве G/ существует висячая вершина. Удалив ее вместе с примыкающим ребром, получим дерево G;. Продолжая этот процесс разборки, через п — 1 шагов мы получим одну изолированную вершину. Следовательно, исходное дерево содержало п — 1 ребро. Итак, количество ребер дерева на единицу меньше количества его вершин.

Докажем, что если для связного конечного графа G (V, Е) выполняется равенство lvI-1Е/= 1, то G — дерево. Предположим противное, что граф G не является деревом. Тогда в нем содержится цикл, и мы можем удалить некоторое ребро из этого цикла, не нарушив тем самым связность графа. Разрывая подобным образом все циклы, мы получим суграф Gi (V, Ej) графа G, который будет являться деревом и для которого Е_} /< е /. Но так как G; - дерево, то IvI-Ie, I= 1. поэтому IvI-IeI< 1, что противоречит условию.

В силу вышесказанного можно сформулировать следующие определения.

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

Определение 4. Деревом называется конечный минимальный связный граф.

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

Определение 5. Деревом называется конечный связный граф, каждое ребро которого является перешейком.

Пример дерева представлен на рис. 38. В качестве несложного упражнения можно убедиться в корректности еще одного определения.

Рис. 38.

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