Дерево как особый вид графа

Дерево как особый вид графа

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

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

Из чего состоит дерево

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

Часть дерева	Что это
Корень	главная, самая верхняя вершина
Ветвь	линия от вершины к нижней вершине
Лист	вершина без продолжения вниз

Где встречаются деревья

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

Диск Документы Школа Фото Музыка

Здесь «Диск» — это корень, а «Школа», «Фото» и «Музыка» — листья, ведь внутри них в нашем примере больше ничего нет. Деревом изображают также родословную семьи, устройство государства и перебор вариантов в задаче с несколькими решениями. Уровни дерева показывают, насколько глубоко вложена вершина: корень находится на верхнем уровне, его части — на следующем, и так далее. Чем больше уровней, тем подробнее дерево описывает устройство объекта.

Чем дерево отличается от обычного графа

Не каждый граф является деревом. У дерева есть несколько обязательных свойств.

• в дереве нет циклов — нельзя вернуться в вершину по кругу;
• между двумя любыми вершинами существует ровно один путь;
• есть выделенная главная вершина — корень;
• дерево всегда связно: до каждой вершины можно дойти.

Благодаря этим свойствам по дереву очень удобно искать путь: он всегда единственный, и заблудиться невозможно. Именно поэтому деревом удобно описывать перебор вариантов: каждая ветвь — это отдельный возможный выбор, а лист — готовый результат. Двигаясь от корня к листьям, можно перечислить все варианты по очереди, ничего не пропустив и не повторив дважды.

Правило. Если в графе есть замкнутый путь (цикл), это уже не дерево. Дерево всегда связно и не имеет петель и кругов, поэтому путь между вершинами единственный.

Кратко о главном

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