Обоснование алгоритма

В силу свойства 6 из теоремы 1 построенный подграф G1(X, E1) является деревом, поэтому k = p –1. Доказательство минимальности каркаса G1(X, E1) разобьем на два этапа. Пусть сначала G(X, E) – полный граф, у которого веса всех ребер различны, и пусть G2(X, E2) – минимальный каркас графа G. Если E2 ¹ E1, то рассмотрим el – первое из ребер множества E1, не принадлежащее E2. В графе  в силу свойства 6 теоремы 1 существует единственный простой цикл m. Цикл m содержит ребро e0ÏE1. Граф G3(X, E3), где , не содержит циклов и имеет n – 1 ребро, поэтому он является деревом. Множество {e1, e2, …, el-1, e0} содержится в E2 и поэтому не содержит циклов. Тогда в силу рассмотренного выше алгоритма m(e0) > m(el). Отсюда следует, что суммарный вес дерева G3(X, E3) меньше веса дерева G2(X, E2). Это противоречит минимальности каркаса G2, поэтому E2 = E1 и G1(X, E1) – единственный минимальный каркас графа G.

Пусть теперь G(X, E) – произвольный нагруженный связный граф. Если m(e1) = m(e2), то сделаем замену

m(e1) ® m'(e1) = m(e1) + e,

m(e2) ® m'(e2) = m(e2) + 2e,

взяв такое e, чтобы сохранились соотношения весов m(e1) и m(e2) с другими весами. Сделаем граф G полным, добавив такие ребра di, что . В полученном графе единственным минимальным каркасом будет каркас, полученный с помощью рассмотренного алгоритма. Легко видеть, что этот каркас будет минимальным и в исходном графе G(X, E).

На рис.4 изображены нагруженный граф G и его минимальный каркас G1.

Рис. 4

ЛИТЕРАТУРА

1. Белоусов А.И., Ткачев С.Б. Дискретная математика: Учебник для ВУЗов / Под ред. В.С. Зарубина, А.П. Крищенко.– М.: изд-во МГТУ им. Н.Э. Баумана, 2001.– 744 с. (Сер. Математика в техническом университете; Вып XIX).

2. Горбатов В.А. Фундаментальные основы дискретной математики. Информационная математика.– М.: Наука, Физматлит, 2000.– 544 с.– ISBN 5-02-015238-2.