Дерево (граф)

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

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

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

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

Оценки на деревьях тоже особые. Обход в глубину стоит $O(V+E)$, а у дерева $E=V-1$, так что всё дерево обрабатывается за линейное время. Сравните с полным графом: там рёбер порядка $V^2$, и те же алгоритмы тяжелеют в тысячи раз. Экономность дерева — не только красота, но и скорость: поэтому иерархии — каталоги файлов, индексы баз данных, деревья решений — живут именно на этой структуре, а не на «универсальных» графах.

Мини-задача на счётчик. В графе 8 вершин и 7 рёбер, и он связный — сколько в нём циклов? Ни одного: это дерево. А если рёбер восемь? Ровно один независимый цикл: каждое ребро сверх $n-1$ приносит свой цикл. Такая арифметика часто экономит рисование графа целиком — счёт рёбер и проверка связности отвечают раньше картинки.