Урок 19. Деревья

Вероятность и статистика, 7 класс · Введение в теорию графов · ~45 минут

🎯 Что ты узнаешь

• Что такое дерево в теории графов (спойлер: оно без листьев и веток в обычном смысле)
• Почему у дерева из n вершин всегда ровно n − 1 рёбер
• Где деревья встречаются: генеалогическое дерево, дерево вариантов, файлы на компьютере
• Как с помощью дерева удобно перебирать все возможности

📖 Разбираемся в теме

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

📌 Запомни: Дерево — это связный граф без циклов. То есть все вершины соединены, но «лишних» рёбер, замыкающих кольцо, нет.

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

🤔 А знаешь ли ты? В информатике деревья — одна из самых главных структур. Папки и файлы на твоём компьютере устроены как дерево: одна главная папка, внутри неё папки поменьше, внутри них — файлы. И никаких циклов: папка не может лежать сама в себе.

Магическое свойство дерева

Посчитай на рисунке 1 вершины и рёбра. Вершин: А, Б, В, Г, Д, Е — это 6. Рёбер: А–Б, А–В, Б–Г, Б–Д, В–Е — это 5. Замечаешь? Рёбер ровно на одно меньше, чем вершин.

📌 Запомни: У дерева с n вершинами всегда ровно (n − 1) рёбер. Ни больше, ни меньше.

Почему именно столько? Подумай так: чтобы связать одну вершину с уже построенной частью дерева, нужно ровно одно новое ребро. Начинаем с одной вершины (0 рёбер), каждая следующая добавляет +1 ребро. Для n вершин понадобится (n − 1) рёбер. Если добавить лишнее ребро — появится цикл (и это уже не дерево). Если убрать ребро — дерево распадётся на части (станет несвязным).

💡 Лайфхак: Быстрый тест: если граф связный и в нём ровно (n − 1) рёбер — это дерево. Если связный, но рёбер больше — где-то прячется цикл.

⚠️ Частая ошибка: Не каждый граф с (n − 1) рёбрами — дерево! Нужно ещё, чтобы он был связным. Например, граф с циклом-треугольником и одной отдельной вершиной имеет 4 вершины и 3 ребра, но это не дерево: он несвязный и с циклом.

⏱ Попробуй сам: В дереве 10 вершин. Сколько в нём рёбер? А если в дереве 8 рёбер — сколько вершин?

Деревья из жизни

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

Дерево вариантов. Самое полезное для нашего предмета! Когда нужно перебрать все возможные исходы, их удобно «развесить» по веткам дерева. Например, бросаем монетку дважды: первый бросок — две ветки (орёл / решка), от каждой — ещё по две. Всего на концах — 4 листочка, это 4 возможных исхода.

Видишь, как удобно? По дереву сразу видно все 4 исхода: ОО, ОР, РО, РР. Ничего не пропустишь и не сосчитаешь дважды.

✍️ Разбор примеров

Пример 1. Является ли граф деревом, если в нём 7 вершин, он связный, и в нём 6 рёбер?

Решение. Связный — да. Рёбер 6 = 7 − 1 = (n − 1). Оба условия выполнены: связный и (n − 1) рёбер. Это дерево.

Ответ: да, это дерево.

Пример 2. В дереве 12 вершин. Сколько рёбер?

Решение. Рёбер = n − 1 = 12 − 1 = 11.

Ответ: 11 рёбер.

Пример 3. В дереве 15 рёбер. Сколько вершин?

Решение. Рёбра = n − 1, значит n = рёбра + 1 = 15 + 1 = 16.

Ответ: 16 вершин.

Пример 4. Граф: вершины А, Б, В; рёбра А–Б, Б–В, В–А. Это дерево?

Решение. Граф связный, но рёбра образуют треугольник — это цикл! А в дереве циклов быть не может. К тому же рёбер 3, а должно быть n − 1 = 2.

Ответ: нет, это не дерево (есть цикл).

Пример 5. Построй дерево вариантов: мороженое бывает двух вкусов (ваниль В, шоколад Ш), а стаканчик — двух видов (вафельный ваф, бумажный бум). Сколько разных вариантов «вкус + стаканчик»?

Решение. Первый уровень — выбор вкуса (2 ветки). От каждого вкуса — выбор стаканчика (ещё по 2 ветки). На концах: В-ваф, В-бум, Ш-ваф, Ш-бум — 4 варианта.

Ответ: 4 варианта (В-ваф, В-бум, Ш-ваф, Ш-бум).

Пример 6. Можно ли убрать одно ребро из дерева так, чтобы оно осталось деревом?

Решение. Нет. У дерева ровно (n − 1) рёбер — это минимум, чтобы связать все вершины. Уберёшь любое ребро — граф распадётся, станет несвязным, а значит, перестанет быть деревом.

Ответ: нельзя — дерево станет несвязным.

💡 Запомни главное

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

📝 Домашнее задание

1. В дереве 20 вершин. Сколько в нём рёбер?
2. В дереве 30 рёбер. Сколько вершин?
3. Граф связный, в нём 8 вершин и 10 рёбер. Может ли он быть деревом? Объясни.
4. Нарисуй какое-нибудь дерево из 5 вершин. Проверь, что рёбер 4.
5. Нарисуй своё генеалогическое дерево из 7 вершин: ты, мама, папа и четверо бабушек-дедушек. Сколько рёбер получилось?
6. Построй дерево вариантов: подбрасывают монетку три раза. Сколько всего исходов на концах веток?
7. Объясни, почему граф с циклом не может быть деревом.
8. ⭐ В семейном кафе предлагают комплексный обед: суп (борщ или щи), второе (котлета или рыба) и напиток (сок или компот). Построй дерево вариантов и сосчитай, сколько разных обедов можно собрать. Сколько «листьев» (концов веток) у твоего дерева?