Дерево

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

Определение дерева

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

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

Главное свойство: число рёбер

Количество рёбер дерева однозначно определяется количеством его вершин. Это важнейшая формула для задач, где требуется найти число соединений или проверить, может ли данный граф быть деревом.

Здесь \(n\) — число вершин, а \(m\) — число рёбер. Например, дерево из 10 вершин имеет \(10-1=9\) рёбер. Дерево из одной вершины имеет 0 рёбер и тоже считается деревом.

Эту формулу можно получить удалением листьев. Листовая вершина имеет степень 1. Если удалить лист и единственное ребро, инцидентное ему, останется дерево с одной вершиной и одним ребром меньше. Повторяя действие, дойдём до одной вершины. Значит, на каждом шаге число рёбер уменьшается на единицу вместе с числом вершин, поэтому сохраняется равенство \(m=n-1\).

Как решать задачи на соединение вершин

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

1. Обозначьте число объектов через \(n\).
2. Проверьте, что все объекты должны быть связаны в одну сеть.
3. Если циклы запрещены или требуется минимальное число соединений, используйте свойство дерева.
4. Подставьте \(n\) в формулу \(m=n-1\).
5. Если даны конкретные рёбра, проверьте связность обходом или подсчётом компонент.

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

Разобранный пример

Проверка здравого смысла: если подключать компьютеры по одному к уже построенной сети, первый компьютер образует сеть без кабеля, второй требует 1 кабель, третий — ещё 1, и так далее. Для 15 компьютеров получится 14 подключений.

Деревья, компоненты и обход

Если граф не является связным, он распадается на компоненты связности. Пусть в графе \(n\) вершин и \(k\) компонент, причём каждая компонента является деревом. Тогда общее число рёбер равно сумме чисел рёбер в компонентах.

Например, если лес состоит из трёх деревьев и всего содержит 20 вершин, то в нём \(20-3=17\) рёбер. Несвязный граф такого вида называют лесом. Если нужно проверить связность вручную или программно, можно выполнить поиск в ширину: стартуем из одной вершины и смотрим, все ли вершины удалось посетить.

В задачах с таблицей смежности полезно помнить: если граф — дерево, сумма степеней всех вершин равна \(2m=2(n-1)\). Это следует из того, что каждое ребро имеет два конца.