Дерево: четыре определения

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

Все четыре описывают одно и то же множество графов:

1. Между любыми двумя вершинами ровно один путь.
2. Граф связный и $m = n - 1$.
3. Граф ациклический и $m = n - 1$.
4. Граф связный и ациклический.

Полезно уметь переходить между ними: в задаче дадут одно, а пользоваться удобнее другим.

Почему они совпадают

Из 2 следует 1. Связность даёт хотя бы один путь между любыми двумя вершинами. Осталось показать, что не бывает двух.

Пусть между $u$ и $v$ есть два разных пути. Пройдя туда одним и обратно другим, получаем цикл. Но связный граф на $n$ вершинах требует не меньше $n-1$ ребра, а цикл на $k$ вершинах содержит $k$ рёбер — то есть одно «лишнее» по сравнению с деревом на тех же вершинах. Тогда на оставшиеся вершины рёбер не хватит, и граф окажется несвязным. Противоречие.

Из 4 следует 3. Меньше $n-1$ ребра связный граф иметь не может. Больше — тоже: добавление любого ребра в связный граф на $n-1$ ребре замыкает цикл, а граф ациклический.

Из 3 следует 2. Будем добавлять рёбра по одному, не создавая циклов. Каждое такое ребро соединяет два куска, которые ещё не были соединены, то есть уменьшает число компонент ровно на единицу. Начали с $n$ компонент, добавили $n-1$ ребро — осталась одна. Граф связный.

Из 1 следует 4. Ровно один путь между любыми двумя вершинами — это связность. Ацикличность тоже: будь цикл, любые две его вершины соединялись бы двумя путями, по дуге в одну сторону и в другую.

Круг замкнулся, все четыре эквивалентны.

Что из этого следует

Лист — вершина степени 1. В любом дереве с $n \ge 2$ листьев хотя бы два: сумма степеней равна $2(n-1) < 2n$, значит не все степени могут быть не меньше двух.

Удаление любого ребра разбивает дерево на две компоненты. То есть каждое ребро дерева — мост.

Добавление любого ребра создаёт ровно один цикл. Тот, что проходит по единственному пути между концами нового ребра.

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

Подвешенное дерево

Дерево само по себе не имеет верха и низа. Но большинство задач становятся проще, если объявить одну вершину корнем и считать, что остальные висят под ней.

После этого появляются понятия: родитель, дети, предки, потомки, глубина, поддерево.

Главное свойство подвешенного дерева: путь между двумя вершинами — это подъём до их наименьшего общего предка и спуск обратно. Горизонтальных участков не бывает. Именно поэтому подвешивание так упрощает задачи про пути.

Корень выбирается произвольно, если условие не диктует иного. Обычно берут вершину 1.

Хранение дерева одним массивом

Подвешенное дерево полностью описывается массивом родителей: $p_v$ — вершина, соседняя с $v$ и более близкая к корню.

vector<int> parent(n, -1);   // parent[root] = -1

Это $O(n)$ памяти вместо $O(n + m)$ и, что важнее, очень удобная форма: подъём к корню — цикл while (v != -1) v = parent[v];.

Массив родителей заполняется одним обходом в глубину от корня. Из него же при необходимости восстанавливается обычный список смежности.

Как распознать дерево в условии

Прямая формулировка «дано дерево» встречается часто, но не всегда. Признаки, которые значат то же самое:

• «$n$ городов и $n-1$ дорога, между любыми двумя есть путь»;
• «связный граф без циклов»;
• «из любого города в любой другой ведёт единственный маршрут»;
• «иерархия», «структура подчинения», «файловая система».

Заметить это стоит обязательно: на дереве работают алгоритмы, которые в общем графе либо медленнее, либо не существуют вовсе — например, поиск диаметра двумя обходами.