Алгоритм нахождения MST с использованием DFS

Question

У меня есть следующий алгоритм: Для заданного (конечного простого ненаправленного) графа G = (V, E) с положительной весовой функцией по краям:

1. Запускайте DFS (поиск в глубину), пока не найдете ребро, идущее назад или DFS не остановится. Если остановлено, верните G.
2. На круге, построенном обратным краем, найдите самый тяжелый край и удалите его из G.
3. Возврат к 1.

Теперь мне нужно понять, что делает этот алгоритм. Я уже доказал, что алгоритм дает мне связующее дерево G, и я считаю, что это минимальное остовное дерево, но я не могу доказать это. Пожалуйста, помогите мне доказать это.

Answer 1

Докажите, что, когда e - самое тяжелое ребро в цикле G, стоимость MST G - e не больше, чем стоимость MST G.и предположение о e, чтобы построить остовное дерево T 'из G - e со стоимостью (T') ≤ cost (T).) В заключение по индукции на | E |что алгоритм выдает MST.

Answer 2

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