设G= 为连通图,且e∈E。证明:当且仅当e是G的割边时,e才在G的每棵生成树中。

设G= 为连通图,且e∈E。证明:当且仅当e是G的割边时,e才在G的每棵生成树中。
【正确答案】：证明:G= ,设e=(u,v)∈E
充分性 e是G的割边,反证,若存在某MST T₁,e ∉T₁,在T₁中,u与v之间可达,在(G-{e})中,u与v之间仍可达,则e不是G的割边。矛盾。
必要性 e存在于G的每棵生成树中。若e不是G的割边,则G₁=(G-{e})仍是连通的,G₁的生成树T显然也是G的生成树,但e ∉T,矛盾。

设G= 为连通图,且e∈E。证明:当且仅当e是G的割边时,e才在G的每棵生成树中。

相关题目