Деревья
Ненаправленный граф называется деревом, если он является связным и не содер- жит циклов. Например, два графа на рис. 3.1 являются деревьями. Строго говоря, деревья составляют простейшую разновидность связных графов: удаление любого узла из дерева приведет к нарушению его связности.
А если выражаться точнее, каждое ребро T «ори- ентируется» в направлении от r; для каждого из остальных узлов v родительским называется узел u, который непосредственно предшествует v на пути из r; узел w называется дочерним по отношению к v, если v является родительским узлом для w.
В более общей формулировке узел w называется потомком v (а v — предком w), если v лежит на пути от корня к w; узел x называется листовым (или просто листом), если у него нет потомков.
Корневые деревья относятся к числу фундаментальных объектов в теории про- граммирования, потому что они представляют концепцию иерархии. Например, кор- невое дерево на рис. 3.1 может служить представлением организационной структуры небольшой компании с 9 работниками: работники 3 и 4 подчиняются работнику 2; работники 2, 5 и 7 подчиняются работнику 1 и т. д.
Многие сайты имеют иерархиче- скую структуру для упрощения навигации. Например, на типичном сайте кафедры информатики главная страница является корневой; страница Люди (и Учебные кур- сы) является дочерней по отношению к корневой; страницы Преподаватели и Сту- денты являются дочерними по отношению к странице Люди; домашние страницы профессоров являются дочерними по отношению к странице Преподаватели и т. д.
Для наших целей определение корня дерева T может концептуально упростить ответы на некоторые вопросы по поводу T.
Например, если имеется дерево T с n уз- лами, сколько ребер оно имеет? У каждого узла, отличного от корня, имеется одно ребро, ведущее «наверх» по направлению к родителю; и наоборот, каждое ребро ведет вверх ровно от одного некорневого узла. Это позволяет очень легко доказать следующий факт.
(3.1) Каждое дерево из n узлов содержит ровно n − 1 ребро.
Более того, истинно и следующее — более сильное — утверждение, хотя здесь его доказательство не приводится.
(3.2) Допустим, G — ненаправленный граф с n узлами. Если истинны любые два из следующих утверждений, то автоматически выполняется и третье.
- Граф G является связным.
- Граф G не содержит циклов.
- Граф G содержит n − 1 ребро.
А теперь обратимся к роли деревьев в фундаментальной алгоритмической идее
обхода графа.
- Алгоритмы, которые работают бесконечно
- Бесконечные пространства выборки
- Независимые события
- Конечные вероятностные пространства
- Простой рандомизированный план
- Планы и их продолжительность
- Анализ алгоритмов маркировки
- Достижение линейного ожидаемого времени выполнения
- Структура данных для хранения подквадратов
- Оформление отчета по практике по ГОСТу 2021/2022
- Оформление ВКР по ГОСТу
- Как составить бизнес-план своими силами
- Оформление эссе по ГОСТу
- Оформление презентации по ГОСТу
- Оформление статьи по ГОСТу
- Оформление дипломной работы по ГОСТ 2021/2022
- Оформление курсовой работы по ГОСТу
- Оформление контрольной работы по ГОСТу