5.3. Ориентированные или корневые деревья

Вершина v ориентированного графа называется корнем графа G, если из вершины v существует ориентированный путь ко всем остальным вершинам графа

Например, в графе на рис. 5.6 корнем является вершина. Очевидно, что если граф имеет корень, то он квазисильно связный. В следующей теореме мы доказываем, что и из «квазисильной связности» следует существование корня.

Теорема Ориентированный граф G имеет корень тогда и только тогда, когда он квазисильно связный.

Доказательство.

Необходимость очевидна.

Достаточность. Рассмотрим вершины графа G. Поскольку граф G — квазисильно связный, существует вершина из которой есть ориентированные пути к вершинам . По той же причине существует вершина из которой есть ориентированные пути к вершинам Очевидно, что вершина связана также ориентированными путями через вершину с вершинами и Продолжая рассуждать подобным образом, придем к тому, что существует вершина из которой есть ориентированные пути к вершинам Очевидно, что вершина — корень, поскольку она связана через вершину с вершинами

Ориентированный граф G называется деревом, если лежащий в его основе неориентированный граф также является деревом.

Ориентированный граф G называется ориентированным или корневым деревом, если он является деревом и имеет корень. Вершины графа G с нулевой полустепенью исхода называются листьями.

Примером ориентированного дерева является граф, приведенный на рис. 5.8. Вершина в нем является корнем, и притом единственным.

В следующей теореме даются эквивалентные характеризации ориентированных деревьев.

Теорема 5.4. Пусть G — ориентированный граф на вершинах. Тогда следующие утверждения эквивалентны:

1) G — ориентированное дерево;

2) В графе G имеется вершина , из которой есть только один ориентированный путь в любую другую вершину графа

Рис. 5.8. Ориентированное дерево.

3) Граф G — квазисильно связный и теряет это свойство при удалении из него любой дуги;

4) Граф G — квазисильно связный и имеет такую вершину , что

5) Граф G не имеет циклов (не обязательно контуров) и содержит такую вершину , что .

6. Граф -квазисильно связный без циклов.

Доказательство.

Корень графа G обладает требуемыми свойствами.

Очевидно, что граф G — квазисильно связный. Допустим, что это свойство не теряется при удалении из графа G дуги . Тогда существует такая вершина , что из нее имеются ориентированные пути к вершинам и и о, не использующие дугу (и, и). Таким образом, в графе G имеется по два ориентированных пути из вершины к вершине v, а также из вершины к вершине v, что противоречит утверждению 2.

Поскольку граф G — квазисильно связный, он имеет корень . Поэтому для всякой вершины справедливо неравенство Предположим, что для некоторой вершины v справедливо, что Тогда существуют две заходящие в вершину а дуги, например Таким образом, существуют два различных пути из вершины к вершине v, один — через дугу а другой — через дугу Поэтому при удалении одной из этих дуг получившийся граф будет иметь корень и, следовательно, останется квазисильно связным. Это противоречит утверждению 3, следовательно,

Наконец, никакая дуга не может заходить в , поскольку в противном случае после удаления этой дуги из G граф имел бы все-таки корень , а значит, был квазисильно связным. Это снова противоречит утверждению 3. Поэтому

Сумма полустепеней захода в графе G равна Поэтому по теореме 5.1 граф G имеет дугу. Поскольку граф G связный, то по теореме он является деревом и, следовательно, ациклическим.

. Поскольку сумма полустепеней захода в графе G равна он имеет дугу. Так как граф G не имеет циклов, то по теореме 2.2 он является деревом. Поэтому из вершины к любой другой вершине в графе G существует единственный путь. Такой путь должен быть ориентированным, иначе хотя бы одна из вершин пути должна иметь полустепень захода, превышающую 1, что противоречит п. 5. Таким образом, вершина — корень графа G. Поэтому по теореме 5.3 граф G — квазисильно связный.

. Поскольку граф — квазисильно связный, то по теореме 5.3 он имеет корень. Однако из того, что он связный и не имеет циклов, следует, что граф G — дерево.

Подграф ориентированного графа G называется ориентированным остовом графа G, если он является ориентированным деревом и содержит все вершины G. Например, подграф, образованный дугами , является ориентированным остовом графа, изображенного на рис. 5.6.

Мы знаем, что граф G имеет остов в том и только в том случае, когда он связный. Соответствующее утверждение для случая ориентированных графов дается в следующей теореме:

Теорема 5.5. Ориентированный граф G имеет ориентированный остов тогда и только тогда, когда граф G — квазисильно связный.

Доказательство.

Необходимость. Если граф G имеет ориентированный остов, то очевидно, что корень ориентированного дерева будет корнем и в графе G. Поэтому по теореме 5.3 граф квазисильно связный.

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

Применение ориентированных деревьев в топологическом исследовании электрических цепей рассматривается в гл. 13. Двоичным деревом является ориентированное дерево, полустепень исхода каждой вершины которого не превышает 2. Двоичным деревом, например, является граф на рис. 5.9.

Рис. 5.9. Двоичное дерево.

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

1) — вес вершины

2) — длина пути из корня дерева в

3) сумма , называемая длиной взвешенных путей, — минимальна.

Более общая задача возникает в описываемом ниже случае. Множество таких слов, среди которых никакое не является началом другого, называется префиксным кодом. Очевидно, что если последовательность букв образована конкатенацией слов (сцеплением цепочек символов) префиксного кода, его можно разложить на отдельные слова префиксного кода путем разбора слева направо. Например, если префиксный код образует набор 001, 01, 10, 11, а последовательность 1011001000 образована из его слов, то она легко раскладывается на слова 10, 11, 001 и 000.

Пусть — алфавит из букв, а Т - такое ориентированное дерево, что

1) полустепень исхода каждой вершины не превышает

2) каждая исходящая из вершины дуга связана с буквой алфавита таким образом, что никакие две дуги не соответствуют одной букве. Тогда всякий лист v можно связать со словом, образованным конкатенацией, букв в том порядке, в котором они появляются на пути к листу v от корня. Легко убедиться в том, что слова, связанные таким образом с листьями, образуют префиксный код. Например, ориентированному дереву на рис. 5.9 соответствует следующий префиксный код: Задача состоит в том, чтобы для данного и длин построить, используя буквы алфавита префиксный код, длины слов которого составляют . Этот и некоторые связанные с ним вопросы рассматриваются в разд. 15.2 и 15.3.