Minimum Spanning tree subgraph
algorithm, graph, graph-theory, minimum-spanning-tree, tree
Solution
for (a)
I don't really get the question ... can you explain ?
for (b)
I think it's if
for every `e=(u,v)` in `T` if `u in V'` and `v in V'` then `e in E`
then we have `(V′,E′∩T)` is a minimum spanning tree of `G'`.
Coz :
- If some `e` that has `e=(u,v)` in `T` if `u in V'` and `v in V'` but not `in E'`, then `(V′,E′∩T)` is not connected at all. It certainly can't be a spanning tree of `G'`
- If the condition stands, but `(V′,E′∩T)` is not a spanning tree of `G'`, then `G'` has a spanning tree with less cost, let's say it's `Tg`. We can construct a spanning tree `T'` of `G` with less cost than `T`, by: (i) remove every `e=(u,v) , u in V' and v in V' and e in T` from `T` (ii) add every `e=(u,v) , u in V' and v in V' and e in Tg` . The resulting graph is a spanning tree of `G` (because it's connected while having the same number of edges of `T`) and has less cost than `T`. So it can never happen since we already know `T` is a minimul spanning tree of `T`.
Problem
I am going through all the exercises in my book for revision of a class test next week, and i am really confused about this sub-graph question. Currently my thinking leads me to believe that since we already have a minimum spanning tree G therefore since we have sub-nodes present in that minimum spanning tree, a G' has to exist. As far as the condition goes, i'm at a bit of a loss. A graph X′ is a sub-graph of graph X if the node and edge sets of X′ are subsets of the node and edge sets of X respectively. Let us have (V,T) as a minimum spanning tree of G and G′=(V′,E′) be a connected sub-graph of G. (a) Prove that (V′,E′∩T) is a sub-graph of a minimum spanning tree of G′. (b) Under what condition is (V′,E′∩T) a minimum spanning tree of G′? Prove your claim. thanks in advance!