§ 55. Деревья

Определения и обозначения

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

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

Корень дерева — выделенная вершина, от которой задают расположение остальных вершин по уровням. Вершины, расположенные дальше от корня, образуют следующие уровни; направление «от корня» позволяет говорить о родителях и потомках. Выбор корня нужен, чтобы представить дерево как иерархию.

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

Как это устроено

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

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

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

В дереве из n вершин ровно n − 1 ребро. Это можно обосновать построением: начнём с одной вершины и будем присоединять к ней новые вершины, каждый раз одним ребром, иначе возникнет цикл; для n вершин понадобится n − 1 такое присоединение. Если связать дополнительным ребром уже соединённые вершины дерева, между ними есть путь, и новое ребро замкнёт его в цикл.

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

Основные признаки и элементы дерева

Используйте таблицу как последовательность проверок: сначала выясните, связен ли граф, затем ищите циклы. Число рёбер служит полезной проверкой, но не заменяет первые два условия. Корень и листья определяют уже после того, как разобрались со структурой дерева.

Разбор задач

Задача 1. Граф из пяти вершин и четырёх рёбер

Условие: изобразить граф из пяти вершин и четырёх рёбер и проверить, является ли он деревом. Число рёбер равно n − 1, но этого пока недостаточно для ответа. Выберем простой пример: вершины A, B, C, D, E и рёбра AB, AC, BD, CE.

1. Нарисуем A в центре, соединим её с B и C, затем соединим B с D, а C — с E.
2. Проверим связность: от A можно попасть к B и C, от них — к D и E, значит, доступны все вершины.
3. Проверим циклы: каждый из четырёх рёбер добавляет новую вершину к уже построенной части, поэтому замкнутого маршрута не образуется.

Ответ: выбранный граф является деревом, потому что он связен и не содержит циклов. Если бы при тех же пяти вершинах и четырёх рёбрах граф распался на части, он деревом бы не был. Следовательно, совпадение числа рёбер с n − 1 нужно сочетать с проверкой структуры.

Задача 2. Связный граф из семи вершин

Условие: найти число рёбер в связном графе из семи вершин и объяснить, почему он является деревом, если циклов в нём нет. Здесь уже известны связность и отсутствие циклов, то есть оба основных условия определения дерева. Остаётся применить свойство о числе рёбер.

1. Обозначим количество вершин через n: по условию n = 7.
2. Для дерева используем формулу: число рёбер равно n − 1.
3. Подставим значение: 7 − 1 = 6 рёбер; связность и отсутствие циклов подтверждают, что граф — дерево.

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

Задача 3. Корень, уровни, родители, потомки и листья

Условие: для дерева из задачи 1 выбрать корень, отметить уровни, родителей, потомков и листья, а затем добавить ребро и определить, что изменилось. Возьмём A за корень: это выбор для иерархического представления, а не изменение самого графа. В исходной схеме ветви идут от A к B и C, затем — к D и E.

1. Запишем уровни: A — нулевой, B и C — первый, D и E — второй.
2. У B родитель A и потомок D; у C родитель A и потомок E. Вершины D и E — листья, поскольку у них нет детей.
3. Добавим ребро DE. Между D и E уже был путь D—B—A—C—E, поэтому новое ребро вместе с ним образует цикл.

Ответ: корень — A, листья — D и E; после добавления ребра граф перестаёт быть деревом, поскольку в нём появился цикл. Вершины и старые рёбра никуда не исчезают, но к прежнему пути добавляется ещё один маршрут между D и E. Число рёбер теперь больше n − 1.

Типичные ошибки

Ошибка: считать любой граф с n − 1 ребром деревом. Такое рассуждение привлекает простотой подсчёта, но граф может не быть связным или содержать цикл. Проверьте связность и отсутствие циклов отдельно, прежде чем делать вывод.

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

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

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

Связь с другими темами

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

Что запомнить

• Дерево — связный граф без циклов.
• Между любыми двумя вершинами дерева проходит ровно один путь.
• В дереве из n вершин n − 1 ребро.
• Добавление ребра к дереву создаёт цикл.
• Удаление любого ребра дерева нарушает связность.
• Корень задаёт иерархию, уровни и отношения между вершинами.