Оптимальность алгоритма обратного удаления

Располагая свойством цикла, можно легко доказать, что алгоритм обратного удаления строит минимальное остовное дерево. Базовая идея аналогична доказательствам оптимальности двух предыдущих алгоритмов: алгоритм обратного удаления добавляет ребро только в том случае, если это оправданно согласно.

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

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

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

Рассмотрим ребро e с максимальной стоимостью в C, которое будет первым обнаружено этим алгоритмом. Это ребро должно быть удалено, потому что его удаление не приведет к потере связности графа, но это противоречит поведению алгоритма обратного удаления.

Хотя эта тема далее рассматриваться не будет, сочетание свойства сечения (4.17) со свойством цикла (4.20) наводит на мысль, что здесь действует еще более общая закономерность.

Любой алгоритм, который строит остовное дерево посредством включения ребер, соответствующих свойству сечения, и удаления ребер, соответствующих свойству цикла (в совершенно произвольном порядке), в конечном итоге сформирует минимальное остовное дерево.

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