Минимальное остовное дерево, содержащее заданное ребро после удаления краев

Question

Это часть подготовки к экзамену. Я знаю, что есть что-то делать с алгоритмом Макс-поток, но я был бы рад за подсказку:

Пусть G=(V,E) неориентированного связный граф, и пусть w:E->R весовой функции, e края и k > 0. Опишите алгоритм, который определяет, можно ли удалить из графика не более k ребер, так что e будет принадлежать минимальному остовному дереву нового графика.

Я считаю, что остовное дерево - это идеальное совпадение. Но как сделать его минимальным, содержащим e и нужным количеством других ребер?

Answer 1

Подсказка: для каждого ребра e существует пучок с минимальным весом, содержащий e тогда и только тогда, когда не существует пути между конечными точками e, состоящими из ребер (строго), более легких, чем e.