Деревья и листья

Связность без циклов

Дерево — связный неориентированный граф без циклов. Между любыми двумя его вершинами существует ровно один простой путь. Существование следует из связности; если бы путей было два, их расхождение и последующее соединение образовали бы цикл.

В дереве из $n$ вершин ровно $n-1$ ребро. Обратное утверждение требует условия: связный граф с $n-1$ рёбрами — дерево, но несвязный граф с таким числом рёбер может содержать цикл. Одинокая вершина без рёбер тоже является деревом.

Лист, корень и родитель

Лист в неориентированном дереве — вершина степени 1. Любое конечное дерево с двумя и более вершинами имеет хотя бы два листа: ими заканчивается самый длинный простой путь. Если выделить корень, появляется иерархия родителей и детей. В корневом дереве лист часто определяют как вершину без детей; это соглашение отдельно учитывает одноэлементное дерево.

Три примера

1. У дерева с 7 вершинами 6 рёбер. Удаление любого ребра разделит его на две компоненты: другого пути между концами нет.
2. У звезды из центра и четырёх листьев пять вершин, четыре ребра и четыре листа. Между двумя листьями путь проходит через центр.
3. Полное двоичное дерево, где у каждой внутренней вершины ровно два ребёнка, с тремя внутренними вершинами имеет четыре листа. Всего семь вершин и шесть рёбер.

Связь с вероятностью

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

Ошибки

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