Вероятность и статистика · Графы и деревья

Деревья и листья

Связный граф без циклов, единственный путь и подсчёт рёбер.

6 минут на чтениеЗаданий для самопроверки: 3

Чему научимся

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

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

План рассуждения и проверка понимания

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

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

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

Схема к теме

Наглядная модель: Деревья и листья

Связный граф без циклов, единственный путь и подсчёт рёбер.

Деревья и листья → дерево
Деревья и листья → лист
Деревья и листья → единственный путь

Схема связывает понятие «Деревья и листья» с его ключевыми признаками. Вывод: Свяжите определение, условия и обозначения: тогда формула станет краткой записью уже понятной идеи.

Проверка пониманияОбъясните тему своими словами

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

В хорошем объяснении есть:

Назван единственный старый путь между концами нового ребра.
Новое ребро замыкает этот путь и не может создать второй независимый цикл.

Связность без циклов

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

В дереве из $n$ вершин ровно $n-1$ ребро. Обратное утверждение требует условия: связный граф с $n-1$ рёбрами — дерево, но несвязный граф с таким числом рёбер может содержать цикл. Одинокая вершина без рёбер тоже является деревом.

Лист, корень и родитель

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

Три примера

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

Связь с вероятностью

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

Ошибки

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

Формула, смысл и ограничения

Главные формулы с расшифровкой

|E|=|V|-1

Формула словами: Для конечного непустого дерева: связного неориентированного графа без циклов.

От формулы к наблюдению

Попробуйте самостоятельно

Измените параметры и сопоставьте расчёт с результатами случайного эксперимента.

Лаборатория: Дерево вероятностей

От простого к сложному

Проверьте себя

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

Открываем задание…

Источники и соглашения

Объяснения и задачи — авторские. Источники помогают проверить определения, условия и школьную привязку. Обозначения и параметризация указаны в статье.