Minimum Spanning Trees Assume that all edge costs in a graph

Minimum Spanning Trees

Assume that all edge costs in a graph G = (V, E) are distinct. Let C be a cycle in the graph, and let edge bar e = (u, v) elementof C be the most expensive edge of C. Prove that bar e cannot belong to any MST of G. Let S proper subset V, S notequalto 0. Let edge bar e = (u, v) be the minimum cost edge with u elementof S and v elementof V\\S (or vice versa). Prove that bar e belongs to every MST of G. Use the previous two part to prove the following statement. Edge bar e = (u, v) does not belong to a minimum spanning tree of graph G if and only if u and v can be joined by a path consisting entirely of edges that are cheaper than bar e. Make sure you prove both directions.

Solution

The way for changing the cost of e to an arbitary values implies as we must know e^|

^{is the most expensive edge in atleast k+1 cycles which all are disjoint except for e itself .}

^{given a graph g edge e}\' and parameters k as:

a)Temporarily delete all edges which are most expensive than the particular selected edge than e^\'

b)select one end of e to a source and other end to be a sink.set all edges capacity to 1 such that all of them are integers without float values.

c)check if there exists a flow of value atleast k+1.flow decomposition will give edge disjoiint paths fom s to t as a flow and converting these paths by adding e^\'

and by this procedure we will have k=k+1 more cycles in which becones the most expensive edge and as since the rest are edge disjoint .We cab=n assure that prpoerty holds well.

b)if minimum cost edge e of a graph is unique then this edge is included in any mst is the given statement

proof:

if e is not included in the mst removing any of the edges in the cycle after adding e to mst will yield a spanning tree of smaller weight.this indicates that minimum cost edge needs to be compulsorily included.