Деревья

Ненаправленный граф называется деревом, если он является связным и не содер- жит циклов. Например, два графа на рис. 3.1 являются деревьями. Строго говоря, деревья составляют простейшую разновидность связных графов: удаление любого узла из дерева приведет к нарушению его связности.

Для рассмотрения структуры дерева T удобно представить некоторый узел r как корень дерева. По сути, дерево «цепляется» за узел r, а остальные его ветви свисают вниз под действием силы тяжести. А если выражаться точнее, каждое ребро T «ори- ентируется» в направлении от r; для каждого из остальных узлов v родительским называется узел u, который непосредственно предшествует v на пути из r; узел w называется дочерним по отношению к v, если v является родительским узлом для w. В более общей формулировке узел w называется потомком v (а v — предком w), если v лежит на пути от корня к w; узел х называется листовым (или просто листом), если у него нет потомков. Таким образом, две диаграммы на рис. 3.1 изображают одно и то же дерево T — те же пары узлов, соединенные ребрами, но правая диа- грамма представляет дерево, полученное в результате назначения узла 1 корнем T.

Корневые деревья относятся к числу фундаментальных объектов в теории про- граммирования, потому что они представляют концепцию иерархии. Например, кор- невое дерево на рис. 3.1 может служить представлением организационной структуры небольшой компании с 9 работниками: работники 3 и 4 подчиняются работнику 2; работники 2, 5 и 7 подчиняются работнику 1 и т. д. Многие сайты имеют иерархиче- скую структуру для упрощения навигации. Например, на типичном сайте кафедры информатики главная страница является корневой; страница Люди (и Учебные кур- сы) является дочерней по отношению к корневой; страницы Преподаватели и Сту- денты являются дочерними по отношению к странице Люди; домашние страницы профессоров являются дочерними по отношению к странице Преподаватели и т. д.

Для наших целей определение корня дерева T может концептуально упростить ответы на некоторые вопросы по поводу T. Например, если имеется дерево T с n уз- лами, сколько ребер оно имеет? У каждого узла, отличного от корня, имеется одно ребро, ведущее «наверх» по направлению к родителю; и наоборот, каждое ребро ведет вверх ровно от одного некорневого узла. Это позволяет очень легко доказать следующий факт.

(3.1) Каждое дерево из n узлов содержит ровно n - 1 ребро.

Более того, истинно и следующее — более сильное — утверждение, хотя здесь его доказательство не приводится.

(3.2) Допустим, G — ненаправленный граф с n узлами. Если истинны любые два из следующих утверждений, то автоматически выполняется и третье.

(i) Граф G является связным.

(ii) Граф G не содержит циклов.

(iii) Граф G содержит n - 1 ребро.

А теперь обратимся к роли деревьев в фундаментальной алгоритмической идее обхода графа.

3.2.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Деревья:

  1. 3.11.10. Облако и Дерево
  2. О друзьях-деревьях
  3. Дерево упало
  4. Построение дерева целей.
  5. Над деревьями
  6. И НА КАМНЯХ РАСТУТ ДЕРЕВЬЯ
  7. ИДЕЯ 41 ДЕРЕВО, СПОСОБНОЕ ВЫДЕРЖАТЬ УРАГАН
  8. Глава 12 О ТОМ, КАК ТВОРИТ ДЕРЕВО
  9. Призыв к пробуждению от Красных Деревьев
  10. Предложение №2 Полазай по своему дереву
  11. Пример 1.