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