§ 38. Прадерево. Дерево

Прадерево. Прадеревом с корнем называется граф если:

3) граф не содержит контуров.

Иначе говоря, существует единственная вершина в которую не заходит ни одна дуга; в каждую другую вершину заходит в точности одна дуга; граф не имеет контуров. На рис. 163 представлено прадерево.

Вершина висячая, если Будучи графом без контуров, прадерево всегда обладает порядковой функцией. На рис. 164 и 165 даны возможные порядковые функции прадерева на рис. 163.

Бифуркант. Прадерево называется бифуркантом, если

Пример бифурканта приведен на рис. 166.

Частичное прадерево графа. Пусть частичный граф без петель графа . Если прадерево с

(кликните для просмотра скана)

корнем то этот частичный граф называют частичным прадеревом с корнем

Например, можно показать, что существует шесть частичных прадеревьев графа на рис. 167 с корнем А.

Используя результаты из [8], дадим метод пересчета прадеревьев.

Рис. 166.

Рис. 167.

Рассмотрим булеву матрицу соответствующую графу и определим матрицу

и матрицу

Для каждого обозначим через А минор матрицы получающийся вычеркиванием в ней -й строки и столбца. Тогда значение минора дает число прадеревьев с корнем Например, для графа на рис. 167 имеем

Число прадеревьев с корнем А (рис. 168) равно

Очевидно, что для этого графа существуют частичные прадеревья только с корнем А.

Рис. 168.

Ветвление. Граф, все связные компоненты которого — прадеревья, называют ветвящимся. Пример такого графа приведен на рис. 169.

Дерево. Неориентированный граф называется деревом, если для него выполняется одно из условий (эквивалентных между собой)

Рис. 169.

1) связный и не содержит циклов;

2) Н содержит ребер и содержит циклов

3) Н связный и содержит ребер;

4) Н не содержит циклов, а добавление одного ребра между любыми двумя вершинами приводит к появлению одного и только одного цикла;

5) Н связный, а удаление любого ребра делает его несвязным;

6) любая пара вершин соединена единственной цепью.

Пример дерева приведен на рис. 170

Частичное дерево графа G. Рассмотрим неориентированный граф связный тогда и только тогда, когда он допускает частичный граф являющийся деревом. Это дерево называют частичным деревом графа

Рис. 170

Рис. 171

Для построения частичного дерева графа достаточно найти ребро, удаление которого не нарушает связности графа; если такого ребра нет, то граф — дерево; если ребро найдется, то удаляем его и процедура повторяется.

Рис. 172.

Рис. 173.

Например, на рис. 171 указан порядок удаления ребер, приводящий к дереву.

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

где булева матрица графа

Величина любого минора (см. стр. 219) дает искомое число (так как граф симметрический).

Пример. На рис. 172 и 173 изображены соответственно Имеем

Рис. 174.

Тогда

Эти восемь деревьев представлены на рис. 174.

УПРАЖНЕНИЯ

(см. скан)