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

В прошлом параграфе мы условились называть деревом связный граф без циклов. Требований всего два, но вместе они дают неожиданно много: не глядя на чертёж, можно сказать, сколько в дереве рёбер, найдётся ли в нём вершина с единственным ребром и что случится, если убрать хотя бы одну связь. Разберём эти свойства по порядку — они пригодятся и в схеме водопровода, и в дереве случайного опыта.

Между двумя вершинами — только одна дорога

Дерево связно, значит, из любой вершины по рёбрам можно добраться до любой другой. Спросим строже: а сколькими способами? Пусть из вершины X в вершину Y ведут два разных маршрута. Пройдём по первому туда, по второму обратно — получится замкнутый путь, то есть цикл. А циклов в дереве нет. Противоречие, значит, маршрут только один.

Теорема. Любые две вершины в дереве соединены единственной цепью.

Вот чем дерево удобно на практике: дорогу между двумя точками не приходится выбирать, она единственная. По той же причине вода из водонапорной башни доходит до каждого дома ровно одним путём, а не двумя.

Свойство 1. Убрали ребро — потеряли связность

Первое свойство звучит так: стоит выбросить из дерева любое ребро, и граф перестаёт быть связным. Докажем его от противного. Предположим, что мы выбросили ребро AB, а граф всё же остался связным. Тогда из A в B по-прежнему ведёт какая-то цепь — на рисунке 1, а она показана зелёным. Теперь поставим ребро AB обратно: перед нами снова исходное дерево, но зелёная цепь вместе с этим ребром замкнулась в цикл (рис. 1, б). А в дереве циклов не бывает — противоречие.