Оптимальность алгоритмов Крускала и Прима

Теперь мы можем легко доказать оптимальность алгоритмов Крускала и Прима. Оба алгоритма включают ребро только в том случае, когда это включение оправдывается свойством сечения (4.17).

(4.18) Алгоритм Крускала строит минимальное остовное дерево графа G.

Доказательство. Рассмотрим любое ребро e = (v, w), добавленное алгоритмом Крускала. Пусть S — множество всех узлов, к которым существует путь из v непосредственно перед добавлением e. Очевидно, v Ѯ S, но и w Ѯ S, так как добавление e не приводит к созданию цикла.

Более того, никакое ребро из S в V S еще не было обнаружено, так как любое такое ребро может быть добавлено без создания цикла, а значит, было бы добавлено алгоритмом Крускала.

Следовательно, e — ребро с минимальной стоимостью, у которого один конец принадлежит S, а другой — V S, и, согласно (4.17), оно принадлежит минимальному остовному дереву.

Итак, если нам удастся показать, что результат (V, T) алгоритма Крускала действительно является остовным деревом графа G, то дело будет сделано. Очевидно, (V, T) не содержит циклов, поскольку алгоритм проектировался для предотвращения создания циклов.

Кроме того, если граф (V, T) не был связным, то существовало бы непустое множество узлов S (не равное всему множеству V ), такое, что не существует ребра из S в V S. Но это противоречит поведению алгоритма: мы знаем, что поскольку граф G является связным, между S и V S существует как минимум одно ребро, и алгоритм добавит первое из таких ребер при его обнаружении.

Алгоритм Прима строит минимальное остовное дерево графа G.

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

В самом деле, при каждой итерации алгоритма существует множество S Ӭ V, на базе которого было построено частичное остовное дерево, и добавляется узел v и ребро e, которые минимизируют величину mine=(u, v):uѮS ce.

По определению e является ребром с минимальной стоимостью, у которого один конец принадлежит S, а другой — V S, поэтому по свойству сечения (4.17) оно присутствует в каждом минимальном остовном дереве.

Также тривиально показывается, что алгоритм Прима строит остовное дерево графа G — а следовательно, он строит минимальное остовное дерево.

Узнай цену консультации

"Да забей ты на эти дипломы и экзамены!” (дворник Кузьмич)