Глава 7. ДЕРЕВЬЯ

1. Введение

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

Определения. Нижеследующие определения неориентированного дерева, как легко показать, эквивалентны друг другу. (См. задачу 7.1.)

Неориентированное дерево есть:

(i) связный граф, содержащий вершин и ребер, либо

(ii) связный граф, не имеющий циклов, либо

(iii) граф, в котором каждая пара вершин соединена одной и только одной простой цепью.

Если неориентированный граф с вершинами, то остовным деревом (или, короче, остовом) графа называется всякий остовный подграф графа являющийся деревом (в смысле приведенного выше определения). Например, если граф, показанный на рис. 7.1а, то граф на рис. 7.16 является остовом графа как и граф, изображенный на рис. 7.1в. Из сформулированных выше определений вытекает, что остов графа можно также рассматривать как минимальный связный остовный подграф графа где «минимальность» понимается в том смысле, как говорилось в гл. 2, т. е. никакое собственное подмножество ребер этого остова не образует связный остовный подграф графа

Понятие дерева как математического объекта было впервые предложено Кирхгофом [36] в связи с определением фундаментальных циклов, применяемых при анализе электрических цепей. Приблизительно десятью годами позже Кэли [5] вновь (независимо от Кирхгофа) ввел понятие дерева и получил большую часть первых результатов в области исследования свойств деревьев.

Ориентированное дерево (называемое также древовидностью) определяется аналогичным образом.

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

На рис. 7.2 показан граф, который является ориентированным деревом с корнем в вершине

Рис. 7.1а.

Рис. 7.1б. Остов графа

Рис. 7.1в. Другой остов графа

Из приведенного определения следует, что ориентированное дерево с вершинами имеет дуг и связно. Также очевидно, что не всякий ориентированный граф содержит остовное ориентированное дерево. Это подтверждает граф, изображенный на рис. 7.3.

Следует отметить, что неориентированное дерево можно преобразовать в ориентированное: надо взять его произвольную вершину в качестве корня и ребрам приписать такую ориентацию,

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

Рис. 7.3. Граф без ориентированного остовного графа.

чтобы каждая вершина соединялась с корнем (только одной) простой цепью. Обратно, если ориентированное дерево, то где В — множество дуг дерева без учета их ориентации, является неориентированным деревом.

«Генеалогическое дерево», в котором вершины соответствуют лицам мужского пола, а дуги ориентированы от родителей к детям, представляет собой хорошо известный пример ориентированного дерева. Корень в этом дереве соответствует «основателю» рода (лицу, родившемуся раньше остальных).

В настоящей главе приводится алгоритм порождения всех остовных деревьев произвольного неориентированного графа и даются методы прямого построения кратчайших остовных деревьев во взвешенном графе (в котором веса приписаны дугам). Кратчайшее остовное дерево (SST) графа находит, очевидно, применение при прокладке дорог (газопроводов, линий электропередач и т. д.), когда необходимо связать точек некоторой сетью так, чтобы общая длина «линий связи» была минимальной. Если точки лежат на евклидовой плоскости, то их можно считать вершинами полного графа с весами дуг, равными соответствующим «прямолинейным» расстояниям между концевыми точками дуг. Тогда, поскольку «разветвление» дорог допускается только в заданных точках, SST графа будет как раз требуемой сетью дорог, имеющей наименьший вес.

Если же «разветвление» дорог можно производить и «вне» заданных точек, то возможна и более «короткая» (с меньшей стоимостью) сеть. Нахождение такой сети дорог представляет собой хорошо известную задачу Штейнера. Краткому обсуждению этой задачи посвящен последний раздел данной главы.