Деревья

Ненаправленный граф называется деревом, если он является связным и не содер- жит циклов. Например, два графа на рис. 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 ребро.

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

обхода графа.