Minimum Spanning Tree

MST has the min max edge

My attempt to reconstruct a detailed proof for a remark on Luc Devroye’s note of MST.

Max edge in a spanning tree

Let TT be a spanning tree of G(V,E)G(V,E) and L(T)=max(u,v)T w[u,v]L(T) = max_{(u,v)\in T}\ w[u, v], the longest edge in a spanning tree.

Claim: The minimum spanning tree also minimizes L(T), that is, \text{Claim: The minimum spanning tree also minimizes L(T), that is, }

L(MST)=minall TL(T)L(MST) = min_{all\ T} L(T)




MST\inT, so L(MST) cannot be less than the minimum L(T) of all T’s.


In the figure above, we assume the red arrow is the longest edge in MST. We construct the MST by adding the shortest “bridge” each time we cross two sets, AA and VAV-A. Thus, all other grey edges are longer than or equal to the red edge. These grey edges are in some other spanning trees.

For convenience, take one grey edge and call it (x,y)(x,y) because it’s from some vertex xAx\in A to yVAy \in V-A. If it’s the max edge of its spanning tree, TxT_x. L(Tx)L(MST)L(T_x) \geq L(MST). If it’s not, there exists a max edge (x,y)(x',y') in TxT_x such that (x,y)>(x,y)L(MST)(x',y') \gt (x, y) \geq L(MST). So L(Tx)L(MST)L(T_x) \geq L(MST).


欢迎通过 Twitter 邮件告诉我你的想法
Find me on Twitter or write me an email