Зарегистрируйтесь для доступа к 15+ бесплатным курсам по программированию с тренажером

Деревья Теория графов

В этом уроке мы изучим еще один вид графов — древовидные. Именно этот вид графов активно используется в программировании — он связан с алгоритмами сортировки и поиска.

Деревья

Деревья — это связные графы без циклов. Их часто применяют в математике и информатике. Вот так они выглядят:

eyJpZCI6IjY4NjUyNmJhOTc1MWE4MGYxMDMxMTk0MzFkNjY0NmMxLnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=d21bf39ebfce567e79fce49e8f7fdf7fc5e50b51c138b03c4645ff91dc4682ba

Как видно из примера, у деревьев определенная древовидная ветвистость, откуда они и получили свое название.

Благодаря связности и отсутствию циклов у деревьев есть ряд свойств:

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

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

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

Листья и индукция

С древовидными графами работает механизм индукции — это значит, что по каждому дереву с вершинами можно перемещаться с шагом ребро.

Для этого нам понадобится лист в дереве — вершина, которая находится на концах каждого дерева.

Разберем следующую теорему: у каждого дерева с хотя бы двумя вершинами есть хотя бы два листа. Докажем это утверждение.

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

Обсудим, почему это работает именно так:

  • У конечных точек не может быть других соседей на пути, поскольку это создало бы цикл, что невозможно в дереве

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

Воспользуемся индукцией, чтобы доказать, что каждое дерево с вершинами имеет ребро.

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

По гипотезе индукции имеет ребер. Чтобы получить из было удалено одно ребро, у должно быть ребер. Таким образом, результат индукции верен. Такую же технику можно использовать в доказательствах с участием других деревьев.

Альтернативные определения деревьев

Любое из свойств дерева используют, чтобы переформулировать определение дерева.

Для графа эквивалентны следующие утверждения:

  1. — дерево

  2. Каждая пара вершин графа соединена ровно одним путем

  3. связно, и удаление любого ребра разъединяет его

  4. У нет циклов, и добавление любого ребра создает цикл

  5. — связный граф с вершинами и ребрами

  6. — ациклический граф с вершинами и ребром

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

Леса

Если мы уберем связность из определения дерева, то получим лес — граф, в котором нет циклов. Он состоит из нескольких компонентов — деревьев:

eyJpZCI6IjVjZmJkMzNjOGJiZjhlNmRmNzlmZDU3MmE3NDM4YzE1LnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=3094e409ccb1d15628a261b8fb5162d2c7e0643ed54654e05007091ef1cd45f7

Деревья и леса — двучленные, то есть у них нет циклов.

Выводы

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

Еще есть бинарные деревья, в которых у каждой вершины не более двух дочерних вершин. Бинарные деревья важны во многих алгоритмах информатики, таких как поиск, сортировка и разбор выражений.


Аватары экспертов Хекслета

Остались вопросы? Задайте их в разделе «Обсуждение»

Вам ответят команда поддержки Хекслета или другие студенты

Об обучении на Хекслете

Для полного доступа к курсу нужен базовый план

Базовый план откроет полный доступ ко всем курсам, упражнениям и урокам Хекслета, проектам и пожизненный доступ к теории пройденных уроков. Подписку можно отменить в любой момент.

Получить доступ
1000
упражнений
2000+
часов теории
3200
тестов

Открыть доступ

Курсы программирования для новичков и опытных разработчиков. Начните обучение бесплатно

  • 130 курсов, 2000+ часов теории
  • 1000 практических заданий в браузере
  • 360 000 студентов
Отправляя форму, вы принимаете «Соглашение об обработке персональных данных» и условия «Оферты», а также соглашаетесь с «Условиями использования»

Наши выпускники работают в компаниях:

Логотип компании Альфа Банк
Логотип компании Aviasales
Логотип компании Yandex
Логотип компании Tinkoff

Используйте Хекслет по-максимуму!

  • Задавайте вопросы по уроку
  • Проверяйте знания в квизах
  • Проходите практику прямо в браузере
  • Отслеживайте свой прогресс

Зарегистрируйтесь или войдите в свой аккаунт

Отправляя форму, вы принимаете «Соглашение об обработке персональных данных» и условия «Оферты», а также соглашаетесь с «Условиями использования»
Изображение Тото

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