В этом уроке мы изучим еще один вид графов — древовидные. Именно этот вид графов активно используется в программировании — он связан с алгоритмами сортировки и поиска.
Деревья
Деревья — это связные графы без циклов. Их часто применяют в математике и информатике. Вот так они выглядят:
Как видно из примера, у деревьев определенная древовидная ветвистость, откуда они и получили свое название.
Благодаря связности и отсутствию циклов у деревьев есть ряд свойств:
- В любом дереве есть ровно один путь из каждой вершины в каждую другую. Например, если есть два пути к вершине, то их можно объединить, чтобы получить цикл
- У деревьев наименьшее количество ребер, которое только может быть у графа. При этом они остаются связными. Каждое ребро дерева — режущее, значит, не лежит в цикле
- У деревьев наибольшее число ребер, которое может быть у графа без циклов. Добавление любого ребра к дереву создает ровно один цикл. Например, если добавить ребро между вершинами
u
иv
, то получится цикл, включающий реброuv
и путь. Он гарантированно существует междуu
иv
Листья и индукция
С древовидными графами работает механизм индукции — это значит, что по каждому дереву с n
вершинами можно перемещаться с шагом n-1
ребро.
Для этого нам понадобится лист в дереве — вершина, которая находится на концах каждого дерева.
Разберем следующую теорему: у каждого дерева с хотя бы двумя вершинами есть хотя бы два листа. Докажем это утверждение.
Рассмотрим любой путь максимальной длины в дереве. Поскольку у дерева две вершины и оно связное, этот путь должен существовать. У обеих конечных точек этого пути степень 1
в дереве. Их единственные соседи — вершины, которые располагаются перед ними на пути.
Обсудим, почему это работает именно так:
- У конечных точек не может быть других соседей на пути, поскольку это создало бы цикл, что невозможно в дереве
- У конечных точек не может быть других соседей вне пути, поскольку тогда мы могли бы использовать такого соседа для расширения пути. Только это невозможно, так как у пути уже максимальная длина
Воспользуемся индукцией, чтобы доказать, что каждое дерево с n
вершинами имеет n - 1
ребро.
Предположим, что все деревья на n
вершинах содержат n - 1
ребро. Пусть T
— дерево на n + 1
вершинах. У T
есть лист v
. У графа T - v n
вершин. При этом он является деревом, потому что удаление вершины не может создать цикл, а удаление листа не может разорвать граф.
По гипотезе индукции T - v
имеет n - 1
ребер. Чтобы получить T - v
из T
было удалено одно ребро, у T
должно быть n
ребер. Таким образом, результат индукции верен. Такую же технику можно использовать в доказательствах с участием других деревьев.
Альтернативные определения деревьев
Любое из свойств дерева используют, чтобы переформулировать определение дерева.
Для графа T
эквивалентны следующие утверждения:
T
— дерево- Каждая пара вершин графа
T
соединена ровно одним путем T
связно, и удаление любого ребра разъединяет его- У
T
нет циклов, и добавление любого ребра создает цикл T
— связный граф сn
вершинами иn-1
ребрамиT
— ациклический граф сn
вершинами иn-1
ребром
Доказательство любой части этого определения включает аргументы, аналогичные тем, которые мы приводили выше. Существуют и другие способы комбинирования свойств деревьев для получения альтернативных характеристик деревьев.
Леса
Если мы уберем связность из определения дерева, то получим лес — граф, в котором нет циклов. Он состоит из нескольких компонентов — деревьев:
Деревья и леса — двучленные, то есть у них нет циклов.
Выводы
У деревьев много применений, особенно в информатике. В ней основное внимание уделяется деревьям с корнями. В таких деревьях одна вершина обозначается как корень, и от нее дерево растет наружу. При корнях нужно рассматривать вершины как родителей других вершин, как в семейном дереве.
Еще есть бинарные деревья, в которых у каждой вершины не более двух дочерних вершин. Бинарные деревья важны во многих алгоритмах информатики, таких как поиск, сортировка и разбор выражений.

Остались вопросы? Задайте их в разделе «Обсуждение»
Вам ответят команда поддержки Хекслета или другие студенты
Для полного доступа к курсу нужен базовый план
Базовый план откроет полный доступ ко всем курсам, упражнениям и урокам Хекслета, проектам и пожизненный доступ к теории пройденных уроков. Подписку можно отменить в любой момент.