2. Экстремальное дерево

Неориентированный связный граф без циклов называется деревом. При составлении дерева используется минимальное число ребер, чтобы граф был связным. Дерево на множестве п вершин всегда содержит т = п – 1 ребер. При включении в дерево любого дополнительного ребра образуется цикл. Построим все неизоморфные деревья с пятью вершинами:

Дерево может строиться на подмножестве вершин графа. Если же дерево содержит все вершины неориентированного графа, то оно называется покрывающим деревом или остовом графа.

Часто требуется связать п пунктов наиболее экономичным способом, например, провести линию электросвязи, проложить путепровод, построить газопровод и т.д. с наименьшей длиной или, например, создать в поселке канализационную систему с максимальным использованием средств частных инвесторов. Тогда эти пункты можно рассматривать как вершины графа, связи между пунктами как ребра, расстояния между пунктами или финансовые инвестиции в определенные связи между пунктами как вес ребер. Т.е. задача сводится к минимизации или максимизации суммарного веса ребер дерева: F* = extr{c_ij}, где c_ij – сумма весов ребер каждого из всех неизоморфных покрывающих деревьев, которые можно построить на множестве вершин исходного графа.

Алгоритм построения экстремального дерева

1. Записать таблицу весов всех возможных связей между n вершинами, которые должны войти в экстремальное дерево.

2. Составить план расположения n вершин дерева.

3. При минимизации (максимизации) суммарного веса ребер дерева выбрать ребро с наименьшим (наибольшим) весом и включить его в создаваемый остов графа.

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

Замечание: Если имеется несколько ребер с одинаковым минимальным (максимальным) весом, то выбирается любое, при этом задача может иметь альтернативные решения.

5. Если в граф включено n – 1 ребро, то задача решена, иначе перейти к п.4.

Пример 1. Заданы расстояния в километрах между 8-ю городами Украины:

	Киев	Винница	Житомир	Ровно	Полтава	Сумы	Харьков	Чернигов
Киев		256	131	318	336	346	478	140
Винница			125	312	593	602	734	396
Житомир				187	468	477	609	271
Ровно					655	664	805	458
Полтава						261	141	477
Сумы							190	350
Харьков								608
Чернигов								

Построить экстремальное дерево с минимальной суммарной длиной ребер.

Решение.

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

	Киев	Винница	Житомир	Ровно	Полтава	Сумы	Харьков	Чернигов
Киев		2 56	131 2	318	336 7	346	478	140 3
Винница			125 1	312	593	602	734	396
Житомир				187 5	468	477	609	271
Ровно					655	664	805	458
Полтава						261	141 4	477
Сумы							190 6	350
Харьков								608
Чернигов								

2. Строим план вершин графа

3. Согласно пп. 3 – 4 алгоритма строим дерево, учитывая минимальные расстояния между городами, указанными в таблице.

Примечание. В дерево не включены связи: Киев-Винница (7₁), Полтава-Сумы (7₂), Житомир-Чернигов (7₃), Винница-Ровно (7₄), Киев-Ровно (7₅) – т.к. соответствующие им ребра приводят к появлению циклов.

Т.о., минимальный вес ребер экстремального дерева F*_min = 125 + 131+ 140 + 141+ 187 + 190 + 336 = 1250 км. #

Пример 2. а) Стоимость прокладки коммуникаций между шестью пунктами в млн. руб. приведена в таблице:

	1	2	3	4	5	6
1		12	8	12	11	14
2			6	2	13	7
3				6	4	11
4					10	8
5						15
6						

Построить связывающее эти пункты дерево с минимальным общим объемом затрат.

б) В предположении, что указанный в таблице вес – грузопассажирские потоки между пунктами, составить дерево максимальных потоков, установить совокупный максимальный поток между этими пунктами.

Решение.

а)		1	2	3	4	5	6
	1		12	8 5	12	11	14
	2			6 3 	2 1	13	7 4
	3				6 3	4 2	11
	4					10	8
	5						15
	6						

Составляем искомое дерево, отмечая последовательность включаемых в него ребер (в ходе построения дерева получаем альтернативные решения):

F*_min = 2 + 4 + 6 + 7 + 8 = 27 млн. руб.

б)		1	2	3	4	5	6
	1		1 2	8	12 4	11 5	14 2
	2			6	2	13 3	7
	3				6	4	11
	4					10	8
	5						15 1
	6						

F*_max = 15 + 14 + 13+ 12 + 11 = 65 ед. грузопотока. #

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