Minimum Spanning tree subgraph

Question

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!

Answer 1

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 :

1. 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'
2. 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.

Answer 2

(a) As I mentioned in a comment (V', E' ∩ T) may contain more than one component. In general, a minimal spanning tree of G' will need more edges. The question is whether there's ever some edge already given in E' ∩ T that can ever go unused. So, we can rephrase the question as the existence of a minimal spanning tree (V', T') for G' such that E' ∩ T ⊂ T'.

Here's a proof that uses Kruskal's algorithm and its proof of correctness. The enumeration of edges by weight in Kruskal's algorithm is not deterministic. Although edges are sorted by weight, the enumeration in non-deterministic on edges of equal weight. Yet for every spanning tree, there's some monotonic enumeration of the edges that yields the minimal spanning tree (V,T). Let E_x be the set of all edges of weight x. For an ordering, pick any order such that all edges in E_x ∩ T come before those in E_x \ T. None of the edges in E_x ∩ T form a cycle in the step in Kruskal's algorithm where they are examined, because they appear in the ultimate minimal spanning tree. It doesn't matter what order they appear in, either, since the order wouldn't change the non-existence of a cycle. Then, all the edges in E_x \ T are discarded because they would form cycles, since they don't appear in T. Thus there's always some ordering for the edges E that yields the minimal tree (V,T).

For the next step, we run Kruskal's algorithm again on G' using an ordering that would yield our given minimal spanning tree of G. Call this tree (V', T'). The key property here is that when we do this, all the edges in E' ∩ T are added before any other edges. To the contrary, suppose that some edge t ∈ E' ∩ T would be rejected in the run on G' because it formed a cycle. That would mean that some chain C had already formed a connection between two components that edge t was the first to connect when computing (V,T). If so, that same chain would have connected those components in the original run, which they did not. Now consider the state of the Kruskal's algorithm on G' at the point immediately after adding the edge in E_x ∩ T to the tree-in-progress. Anything that Kruskal's algorithm adds afterward is added on, so that E_x ∩ T ⊂ T'.

(b) This part is mostly a corollary to part (a), namely, the observation that the edge set E' ∩ T is always a valid state at some point of a run of Kruskal's algorithm. Thus, if the algorithm is done at that point, that is, the set of edges is exhausted, then E' ∩ T is exactly the edges of the minimal spanning tree. The condition is that the algorithm ends when it's in this state, thus when (V', E' ∩ T) is connected, the Kruskal's algorithm terminates and (V', E' ∩ T) is a minimal spanning tree. Conversely, if (V', E' ∩ T) is a minimal spanning tree, then it's necessarily connected.

Answer 3

Part 'a' follows almost immediately from the observation that a minimum spanning tree (such as (V,T)) is indeed minimal! Here's a sketch of one part of the proof:

Assume for contradiction that (V′,E′∩T) is not minimal. This would mean that there is some e in E′∩T that we could remove while still preserving its connectivity. That would imply that e could also be removed from T, which it clearly cannot be, because T is minimal.

For Part 'b', I think lavin has offered a decent solution. Hope this helps some.

Answer 4

i offer an informal tl;dr version for the impatient :) eh9 deserves the bounty

a - there exists some spanning tree for v' formed by T's intersection with all the edges v' could have. E' ∩ T is necesarily a subset of this

b - the condition is when (V', E' ∩ T) is connected. any non minimal edges and cycles in E' are discarded by the intersection with T, and any the remaining minimal connected graph is a MST