Собственность соседних покрывающих деревьев

Question

Мне нужно показать, что при наличии связанного графа с различными весами для каждого ребра каждое остовное дерево (кроме минимального остовного дерева) имеет смежное остовное дерево с меньшим весом. w(T')

Я застрял в доказательстве того, что каждый отдельный ST, который является смежным с MST, имеет смежное связующее дерево (MST, действительно). Как я могу показать это с любым не-MST смежным остовным деревом?

Answer 1

Доказательство алгоритма Крускала отвечает на ваш вопрос. http://people.qc.cuny.edu/faculty/christopher.hanusa/courses/634sp12/Documents/KruskalProof.pdf

Пусть T будет вашим MST, а N будет вашим не связующим деревом. Поскольку N!=T, найдите ребро e в T минимального веса, которого нет в N.

N + e имеет цикл, где e является частью цикла, и в цикле должно быть a e', так что wt(e)

Итак, построим N'=N-e'+e. Очевидно, вес (N1)