Уровень вершины

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

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

Корень дерева — вершина, от которой начинается дерево. У корня нет родительской вершины, потому что выше него в выбранной структуре ничего нет. От корня удобно начинать отсчёт уровней.

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

Родитель и потомки — вершины, связанные отношением подчинения. Родитель расположен на один уровень выше, а его непосредственные потомки, или дети, — на один уровень ниже. Такое описание помогает читать дерево сверху вниз.

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

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

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

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

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

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

Как определить уровень вершины

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

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

Разбор задач

Задача 1

Условие: в дереве корень A соединён с B и C, а вершина B соединена с D. Определите уровни B, C и D, считая уровень корня равным нулю.

1. Корень A имеет уровень 0 по условию.
2. До B и C от A ведёт по одному ребру, поэтому каждая из этих вершин имеет уровень 1.
3. До D нужно пройти два ребра: A—B и B—D. Значит, уровень D равен 2.

Ответ: B — уровень 1, C — уровень 1, D — уровень 2.

Задача 2

Условие: вершина X находится на уровне 3 и является родителем вершины Y. На каком уровне находится Y?

1. Y является непосредственным ребёнком X, значит, между ними есть одно ребро.
2. При движении от родителя к ребёнку уровень увеличивается на единицу.
3. Вычисляем: 3 + 1 = 4.

Ответ: вершина Y находится на уровне 4.

Задача 3

Условие: корень R соединён с A и B; A соединена с C и D; D соединена с E. Уровень корня принят за 1. Найдите уровни всех вершин и объясните, почему C и D имеют одинаковый уровень.

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

Ответ: R — 1, A — 2, B — 2, C — 3, D — 3, E — 4. Одинаковый уровень C и D объясняется одинаковой длиной их путей от корня.

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

Считать вершины вместо рёбер. Ученик может посчитать все точки на пути и получить число на единицу больше. Проверьте себя: уровень равен количеству переходов между вершинами.

Забыть о начале нумерации. Иногда корень принимают за 0, а иногда за 1. Перед решением найдите это правило в условии и используйте его до конца.

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

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

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

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

Уровни пригодятся при изучении деревьев, иерархических структур и алгоритмов обхода дерева. Например, с их помощью можно описывать расположение папок, подчинение объектов и порядок движения по структуре.

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

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