Деревья

Основные определения

Дерево представляет собой граф, не содержащий циклов, что упрощает его структуру.

Рис. 4.9 Дерево

Э то связный граф, так как каждая вершина в нем завершает, по крайней мере, одно ребро, и не существует вершин, которые не завершали бы ребро. Вершина, у которой отсутствуют исходящие ребра, называется изолированной точкой. Изолированная точка в дерево входить не может. Более того, дерево с v вершинами обязательно включает v - 1 ребер. Пример дерева показан на рис.4.9

Генерация

Причину наличия в дереве v — 1 ребер можно выяснить, рассмотрев процесс его генерации. Начнем с простого дерева - единственной вершины. Добавляя к нему вершины, можно генерировать более сложные деревья. Всякий раз мы соединяем новую вершину при помощи ребра с какой-либо другой, введенной ранее. Таким образом, на втором этапе у нас уже будет две вершины и соединяющее их ребро.

П редположим, мы сгенерировали дерево, изображенное на рис.4.10 Добавим к нему вершину h. Она является изолированной точкой

Рис. 4.10. Генерация дерева

Чтобы эта точка стала частью дерева, добавим ребро, соединяющее h с некоторой вершиной (на рисунке hf). Если попытаться ввести дополнительное ребро, соединяющее h с какой-либо другой вершиной, то образуется цикл. Другими словами, если вслед за hf мы добавим ребро hg, то получим цикл hfgh, и граф на рис. 4.10 перестанет быть деревом.

Типы вершин

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

• висячая, которая инцидентна только к одному ребру;

• точка ветвления, или узел, инцидентный по крайней мере к двум ребрам.

На рис. 4.10 a, b, e, g - висячие вершины, с, d и f - узлы. Очевидно, их можно рассматривать как часть последовательности ребер, соединяющих другие вершины.

Деревья-орграфы

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

Рис. .4.11. Направленное дерево

В зависимости от направления дуги здесь различают два типа висячих вершин:

• корень, который имеет одну или несколько исходящих дуг и ни одной входящей;

лист, который имеет одну или несколько входящих дуг и ни одной исходящей.

Тип узла также определяется направлением связанной с ним дуги и, кроме того, инциденцией. Выделяются следующие типы узлов:

• корнеподобный, имеющий больше входящих дуг, чем исхо­дящих;

• листоподобный, имеющий больше входящих дуг, чем исхо­дящих;

• связующий, в котором число входящих дуг равно числу

исходящих;

• простой связующий с одной входящей и одной исходящей дугами (инцнденция равна двум).

Корни, листья и все типы узлов изображены на рис.4.11.

Древовидная структура

Направленное дерево - это простая структура орграфа. Еще более простой древовидной структурой является направленное дерево с одним корнем (иногда его называют древовидной структурой с корнем).

К орень рассматривается как источник направленной древовидной структуры. От корня до любого листа легко проследить элементарную последовательность дуг. Число дуг между корнем и листом называется уровнем листа. Аналогично число дуг между корнем и узлом определяет уровень узла.

Рис. 4.11. Древовидная структура

П

Рис.4.12. Древовидная структура с двоичным ветвлением

рактическая ценность древовидной структуры не вызывает сомнений. Примером такого графа может служить схема управления какой-либо организации. Корнем здесь является президент или директор. От корня исходят одна или несколько дуг к заместителям, которые занимают первый уровень. По мере удаления от корня располагаются' более низкие уровни управления. Наконец, в качестве листьев выступают рабочие, которые и завершают эту схему. Древовидная структура показана на рис.4.11.

Двоичное ветвление. Древовидная структура с двоичным ветвлением содержит всего четыре типа вершин:

• один корень — источник этой древовидной структуры;

• листья—направления роста дерева;

• простые узлы, связывающие предшествующий уровень со следующим за ним (они могут появиться на любом уровне);

• п ростые корнеподобные узлы. с одной входящей и двумя исходящими дугами (инциденция равна трем), составляющие единственно возможный другой тип узла.

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

Транзитивные графы

Более простым типом графа является транзитивный граф — связный орграф, в котором могут присутствовать циклы и не мо­гут - петли. Это обеспечивает сохранение транзитивности. На рис. 4.13 изображен транзитивный орграф с корнем.