CODEWITHSUNDEEP
algorithmdata-structuresgraphtreeminimum-spanning-tree
user14722846
user14722846

Reputation:

Graph and MST, Some Facts and Validity

My notes tell me that the first and last is false. I need some idea of how to understand the validity of these sentences in a more simple and concise manner.

Suppose M is an MST (minimum spanning tree) of the Weighted Graph - GR.

  1. Let A be a vertex of GR then M-{A} is also MST of GR-{A}.

  2. Let A be a leaf of M then M-{A} is also MST of GR-{A}.

  3. If e is a edge of M then (M-{e}) is a forest of M1 and M2 trees such that for M_i, i=1,2 is a MST of Induced Graph GR on vertexes T_i.

Upvotes: 0

Views: 157

Answers (1)

trincot
trincot

Reputation: 349956

  1. Let A be a vertex of GR, then M-{A} is also MST of GR-{A}.

This is false.

If A is not a leaf, then M-{A} is not a connected graph, and so it cannot be a MST.

In more detail: A has at least two neighbors, and the single path (MST property) that exists between two of them includes A. If A is removed, then there is no more path between those two other vertices.

  1. Let A be a leaf of M, then M-{A} is also MST of GR-{A}.

This is true.

As A is a leaf, M-{A} is a connected graph, and has one fewer edge than M: it does not have the edge e that connects with A in M.

Now assume that M-{A} is not a MST of GR-{A}. We know that M-{A} is a connected graph, and has no cycles -- otherwise M would not be an MST. So if it is not an MST, it must be that its weight is not minimised. Then there is a different graph P that is a MST of GR-{A}. But then P+e would have less total weight than M, but still be a spanning tree of GR. So then M could not have been a MST of GR. This is a contradiction, and so the original statement is true.

  1. If e is a edge of M then M-{e} is a forest of M1 and M2 trees such that for Mi, i=1,2 is a MST of the induced graph GR on vertexes Ti.

This is true. Your notes are wrong on this one.

Let's assume that Mi (for either i=1,2) is not a MST of the induced graph on vertexes Ti. We know that Mi is not disconnected (the removal of e creates exactly 2 connected graphs), and that it has no cycles (otherwise M would have had those as well). So if it is not a MST, then the reason would be that its weight is not minimised, and another graph Pi is a MST on that induced graph, and has less total weight than Mi.

If you would then reintroduce the edge e, and so connect Pi with M3-i, we would have a spanning tree for GR which would have less weight than M, and so M is not a MST. This is again a contradiction and so the original statement is true.

Upvotes: 1

Related Questions