Доказательство оптимальности для нового алгоритма, который находит минимальное остовное дерево

Question

Ниже приведен алгоритм, который находит минимальное остовное дерево:

MSTNew(G, w)
   Z ← empty array
   for each edge e in E, taken in random order do
       Z ← Z ∪ e
       if Z has a cycle c then
           let e be a maximum-weight edge on c
           Z ← Z − e
   return (Z)

Всегда ли этот алгоритм возвращает оптимальное решение MST?

---

Я бы сказал, да. Это похоже на замаскированный алгоритм Крускала - своего рода.

Будучи довольно новым для теории графов, я действительно не имею большой идеи, кроме этого. Есть ли у кого-нибудь идеи или советы?

Answer 1

Да, IMO алгоритм выводит минимальное связующее дерево.

Неофициальное доказательство:

На каждой итерации мы удаляем только то ребро, которое является самым дорогим ребром в цикле. Такое ребро никогда не может быть включено в MST (посредством аргумента обмена). Таким образом, мы всегда исключаем те ребра, которые никогда не могут быть частью MST.

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

Тем не менее, обратите внимание, что этот алгоритм будет крайне неэффективным, поскольку на каждой итерации вы не только проверяете циклы (как в Крускале), но также ищите максимальное преимущество в цикле.