Алгоритм Краскала

Алгоритм построения кратчайшего дерева для графа G(X, U) состоит в следующем:

1. Выбираем самое короткое ребро графа U₁, затем ребро U₂, затем самое короткое из оставшихся;

2. Из оставшихся ребер выбираем самое короткое ребро U₃ так, чтобы оно не образовывало цикла с выбранными ребрами;

3. Продолжаем эту процедуру. На k-м к выбранным ребрам U_{1, …,} U_к-1 добавляем самое короткое ребро из оставшихся │ U│ -(к-1) ребер так, чтобы оно не образовывало цикла с выбранными ребрами;

4. При k=n-1 процесс заканчивается. Получим граф без циклов с (n-1)-м ребром. На основании теоремы 1 (пункт 2) построенный граф есть дерево, обозначим его T(n-1).

Докажем, что построенное по этому графу дерево T(n-1) кратчайшее.

1.Сначала предположим что G – полный граф, и длины всех его ребер различны. Для доказательства воспользуемся методом от противного. Предположим, что построенное T(n-1) дерево не кратчайшее и имеется отличное от него кратчайшее дерево T. В этом существует две возможности:

а) T и Т(n-1) не имеют общих ребер. Присоединим к дереву Т ребро U₁Є Т(n-1). В этом случае согласно пункту 4 теоремы 1 в получившемся графе имеется цикл, одним из ребер которого является U₁. Выбросим из этого цикла любое ребро U’≠ U₁.В результате этой операции получим частичное дерево Т', которое отличается от Т одним ребром: u’ заманено U₁. Но l(U₁)< l(U'), т.к. U₁ – кратчайшее ребро. Следовательно, l(T')< l(T) т.е. Т не кратчайшее дерево;

б) Т и Т(n-1) имеют общие ребра U₁, U₂, …, U(k-1). Пусть U_к есть первое ребро, принадлежащее Т(n-1), но не принадлежащее Т.

Рассмотрим граф, который получится присоединением к дереву Т ребра U_к, т.е. . В соответствии с пунктом 4 теоремы 1 в нем есть цикл μ, причем μ содержит ребро U’, не принадлежащее Т(n-1), т.к. в противном случае дерево Т(n-1) содержало бы цикл, что противоречит определению дерева.

Удалив из цикла μ ребро U’, получим дерево , отличающееся от Т одним ребром: U' заменено на U_k. Но l(U_k)< l(U’), т.к. в противном случае на k-м шаге при построении дерева Т(n-1) в него включили бы ребро U’. Следовательно, l(Т')< l(Т), т.е. Т – не кратчайшее дерево.

2. Пусть G(X, U)- неполный граф, но его ребра имеют разную длину. Пусть l(U)=L –сумма длин всех ребер графа G. Присоединим к G столько новых ребер, сколько требуется для получения полного графа. Припишем каждому вновь построенному ребру длину l_j> L.

В полученном полном графе построим кратчайшее дерево Т(n-1).

На основании теоремы 2 в графе G есть кратчайшее дерево, длина которого не превосходит L. Частичное дерево графа G будет являться частичным деревом для построенного полного графа. Поэтому ни одно новое ребро в кратчайшее дерево входить не может. Следовательно, для построения кратчайшего частичного дерева в графе G можно пользоваться алгоритмом Краскала.

3. Предположим теперь, что некоторые ребра графа G(X, U) имеют одинаковую длину. Пусть Δ – минимальная ненулевая разность длин ребер. Обозначим , где N=│ U│. Пусть l₁, …, l_m – все значения длин ребер графа; k_j принимают значение l_j. Занумеруем ребра графа в порядке увеличения длины. Затем изменим длину ребра графа следующим образом: . В получившемся графе длины всех ребер различны. Выберем с помощью алгоритмов Краскала кратчайшее частичное дерево. Проведенное изменение длин ребер графа обладает тем свойством, что если в исходном графе , то и в графе с ребрами измененной длины . Следовательно, кратчайшее частичное дерево в новом графе будет кратчайшим и в старом.

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

Пример

Требуется построить газопровод, соединяющий 10 городов (рис.1.). Возможные соединения городов обозначены ребрами, длины которых l(X_i, X_j), представляющие собой стоимость строительства газопровода на участке (X_i, X_j), заданы и обозначены на графе. Как построить самый дешевый газопровод?

Задача сводится к отысканию частичного дерева заданного графа, общая длина ребер которого минимальна. Воспользуемся алгоритмом Краскала.

Частичное дерево должно содержать (n-1) ребер, т.е. 9. общее число ребер исходного графа .

Рис..1

Заданные длины ребер удобно поместить в следующую симметрическую таблицу, в которой достаточно заполнить один из углов – верхний или нижний по отношению к главной диагонали (рис.3.2.2). На пересечении строки X_i и столбца X_j стоит число, равное длине дуги (X_i, X_j), т.е. l(X_i, X_j). Число заполненных клеток равно числу ребер графа. Следуя алгоритму, выбираем самые короткие ребра U₁=(X₁, X₂), U₂=(X₄, X₆), l(U₁)=l(U₂)=1.

Рис. 2.

Отметим это, зачеркнув выбранные числа в таблице и пометив выбранные ребра на графе жирной чертой. Наименьшее из оставшихся чисел в таблице есть 2, т.е. длина дуги (X₁, X₃). Выбираем в качестве U₃ ребро (X₁, X₃), т.к. оно не образует цикла с выбранными ребрами. Вновь делаем отметку в таблице и на графе и т.д. Получим в результате U₄=(X₉, X₁₀), U₅=(X₁, X₁₀), U₆=(X₄, X₅), U₈=(X₈, X₁₀), U₇=(X₂, X₅), U₉=(X₇, X₆).

Длина последнего выбранного ребра равна 9, т.к. ребра графа с меньшими длинами 6, 7, 8 не могут являться ребрами дерева. Сумма длин ребер построенного дерева L=34. Стоимость строительства самого дешевого газопровода по исходным данным составляет 34 денежные единицы.