Дерево

Определение. Граф

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

Определение. Дерево

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

Ключевое свойство дерева: между любыми двумя вершинами существует ровно один путь.

Свойства дерева

Свойство 1. Если дерево имеет $n$ вершин, то в нём ровно $n - 1$ рёбер.

$E = n - 1$

Свойство 2. Между любыми двумя вершинами дерева существует единственный путь.

Свойство 3. Висячая вершина (лист) — вершина, соединённая ровно с одним ребром. В любом дереве с более чем одной вершиной есть хотя бы одна висячая вершина.

Правило умножения

Если путь (или процесс) состоит из $k$ последовательных шагов, и на каждом шаге есть $m$ вариантов выбора, то общее число исходов равно:

$N = m^k$

Например, бинарное дерево (на каждом шаге 2 ветви) с 3 уровнями даёт $2^3 = 8$ исходов.

Обозначения

Символ	Название	Описание
$n$	Число вершин	Количество точек графа
$E$	Число рёбер	Количество линий графа
$m$	Число ветвей на шаге	Вариантов выбора на каждом уровне
$k$	Число шагов	Количество уровней дерева

Пример 1. Число рёбер дерева

Сколько рёбер в дереве с 7 вершинами?

Дано: дерево, $n = 7$ вершин.

Формула: $E = n - 1$.

Подстановка: $E = 7 - 1 = 6$.

Ответ: в дереве 6 рёбер.

Пример 2. Число исходов бинарного дерева

Сколько исходов даёт бинарное дерево с 3 уровнями?

Дано: бинарное дерево, на каждом шаге $m = 2$ ветви, уровней $k = 3$.

Формула: $N = m^k$.

Подстановка: $N = 2^3 = 8$.

Ответ: 8 исходов.

Пример 3. Дерево вариантов монеты

Сколько исходов у эксперимента «бросить монету 4 раза»? Постройте дерево вариантов.

Дано: 4 броска монеты, на каждом шаге 2 исхода (О или Р).

Формула: $N = m^k$, где $m = 2$, $k = 4$.

Подстановка: $N = 2^4 = 16$.

Ответ: 16 исходов. Дерево имеет 4 уровня, на каждом уровне число вершин удваивается: 2, 4, 8, 16.

Важно!

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