Экстремальное дерево графа

Определение 12.2. Конечный связный неориентированный граф без циклов называется деревом.

Примеры.На рисунке 12.7 представлены примеры деревьев:

Рис.12.7.а

Рис.12.7.б

Дерево, имеющее n вершин, включает в себя n–1 ребро. При составлении дерева используется минимальное число ребер, чтобы граф был связным. При включении в дерево любого дополнительного ребра возникнет цикл. Дерево может быть частью неориентированного графа. Любая совокупность ребер графа попарно связанных отношением смежности и инцидентности и соответствующие им вершины образует дерево графа. Если такое дерево графа содержит все вершины графа, то оно называется покрывающим деревом или остовом графа.

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

Алгоритм решения задачи:

1) Составить план n вершин дерева.

2) Составить таблицу весов всех возможных связей между вершинами.

3) Выбрать ребро с наименьшим (наибольшим) весом и включить в дерево.

4) На следующем шаге рассмотреть минимальное по весу ребро из оставшихся и, если оно не образует цикл с ранее включенными ребрами, то добавить к дереву. Если имеется несколько таких ребер, то выбирается любое, при этом задача имеет альтернативное решение.

5) Построение заканчивается после разбора n–1 ребра.

Задача. Телевизионная компания планирует подключение к своей кабельной сети пяти новых районов. На рисунке 12.8 показана структура планируемой сети и расстояния (в км) между районами и телецентром. Необходимо спланировать наиболее экономичную кабельную сеть.

Рис 12.8

Решение задачи сводится к построению экстремального дерева графа.

Занесем данные задачи в следующую таблицу:

Далее, действуя по указанному алгоритму, построим экстремальное дерево графа (рис. 12.9):

Рис. 12.9

Найдем минимальную длину кабеля (км).

Ответ: .