2.Описание решения

Алгоритм Прима получает в точности минимальное решение. Это нужно доказать.

Для доказательства нам потребуется очень простое утверждение:

Если к дереву добавить ребро, то в дереве появится цикл, содержащий это ребро.

Действительно, пусть добавлено ребро (u,v) – «добавлено» означает, что ребро – новое, что раньше его в дереве не было. Поскольку дерево является связным графом, то существует цепь C(u,…,v) из нескольких ребер, соединяющая вершины u и v. Добавление ребра (u,v) замыкает цепь, превращая ее в цикл.

Теорема. Алгоритм Прима получает минимальное остовное дерево.

Доказательство. Результатом работы алгоритма является набор из n-1 ребер. Они не образуют цикла, ибо на каждом из n-1 шагов соединялись вершины разного цвета, т.е. ранее не связанные. Это граф связный, потому что после проведения 1-го ребра осталось n-1 разных цветов, …, проведения (n-1)-го ребра остался один цвет, т.е. одна компонента связности. Итак, полученный набор ребер образует связный граф без циклов, содержащий n-1 ребер, т.е.n вершин. Следовательно, граф есть остовное дерево. Осталось доказать, что оно имеет минимальную длину.

Пусть {l1, l2, …, ln-1} ребра остовного дерева в том порядке, как их выбирал алгоритм, т.е.li<=li-1. Предположим для простоты доказательства, что все ребра сети имеют разную длину, т.е.

l1<l2<…<ln-1 (1)

Если полученное дерево не минимально, то существует другое дерево, задаваемое набором из n-1 ребер {d1,d2,…,dn-1}, такое что сумма длин di меньше суммы длин li. С точностью до обозначений

d1<d2<…<dn-1 (2)

Может быть l1=d1, l2=d2 и т.д., но так как деревья разные, то в последовательностях (1) и (2) найдется место, где ребра отличаются. Пусть самое левое такое место – k, так что lк!=dк (k может равняться единице, это не испортит доказательства). Поскольку lк

выбиралось по алгоритму самым малым из необразующих цикла с ребрами l1, l2, …, lк-1, то lк<dк. Теперь добавим к дереву (2) ребро lк; в нем появится цикл, содержащий ребро lк и, может быть, какие-то (или все) ребра из l1, l2, …, lк-1, но они сами не образуют цикла, поэтому в цикле будет обязательно ребро d из набора dк, …, dn-1, причем d>lк. Выбросим из полученного графа с одним циклом ребро d; мы снова получим дерево, но оно будет на d-lк короче минимального, что невозможно. Полученное противоречие доказывает теорему для сети со всеми разными ребрами.

Если не предполагать, что все ребра разные, то в доказательстве могло бы получиться, что lк=dк, и нам пришлось бы двигаться дальше по последовательностям (1) и (2), пока бы мы не нашли lк+m<dк+m. Это усложняет доказательство, но не меняет заключения

Алгоритм построения кратчайшего дерева:

Пусть задан граф G = (V,E) , ребрам которого приписаны некоторые веса (стоимости). Требуется построить его остовное дерево T(V,E) минимального веса.

1. Вначале все вершины графа считаются непомеченными. Выбираем любую вершину, с которой будем строить дерево минимального веса, и помечаем ее знаком + .

2. Выбираем все ребра, соединяющие V-любую непомеченную вершину с U- любой помеченной. Среди этих ребер находим ребро, имеющее минимальный вес.

3. Выполняем следующие действия:

а) ребро (V,U) , имеющее минимальный вес, добавляем к дереву T;

б) вершину U помечаем знаком + .