Определения и свойства.

Остовные деревья минимальной стоимости.

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

Остовным деревом графа называется свободное дерево , содержащее все вершины графа .

Теорема 1. (Свойства свободных деревьев)

1. Каждое свободное дерево, имеющее n вершин (n≥1), имеет ровно n-1 ребро.

2. При добавлении в любое свободное дерево нового ребра образуется цикл.

Определение 2. Пусть - помеченный граф, для каждого ребра его метка (стоимость) равна . Стоимостью остовного дерева

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

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

Теорема 2. (Свойство остовных деревьев минимальной стоимости).

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

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

Рассмотрим произвольное остовное дерево , имеющее минимальную стоимость. В частности, для него

(1)

Добавим к дереву ребро , получим , - граф с циклом. Цикл содержит ребро , соединяющее и , а также некоторое ребро , соединяющее и . (рис. 5.1.1)

Причем, по выбору ребра , справедливо .

Рис. 5.1.1.

Удалим ребро из дерева .

Так как удаление ребра привело к разрыву цикла, то - свободное дерево, содержащее все вершины , следовательно - остовное дерево графа , содержащее , стоимость которого . Однако, выбирая в (1) , получим . Противоречие. Значит допущение неверно. Теорема доказана.

Существуют различные способы построения остовных деревьев минимальной стоимости. Многие из них основаны на теореме 2. Далее будут рассмотрены два таких алгоритма.