theorem of graph theory

 THEOREM 1:

Let T_0 be minimum cost spanning tree in G. then every in- tree edge in T_0 must be a minimum cost edge in the fundamental cut set associated with it. 

Proof:

 Let (X;(X)) ̅ be the fundamental cut set associated with the in- tree edge(i;j)in T_0. So, (i;j)is the only in-tree edge in  (X;(X)) ̅, and deletion of (i; j) from T_0disconnects it into smaller trees, one spanning the nodes in X, and the other spanning the nodes in X ̅.

  Suppose a minimum cost edge in the cut set (X;(X)) ̅ is an out-of-tree edge (p; q) and not (i; j) 

  i, e.,         c_pq<c_ij  .

then replacing, (i; j) in T_0 by (p; q) leads to spanning tree T_1  with cost = cost of T_0-(c_ij- c_pq) < cost of T_0, 

contradicting, the optimality of T_0   

hence (i; j) must be minimum cost edge in the fundamental cut set (X;(X)) ̅ associated with it in T_0.

THEOREM 2:

Let T_0 be minimum cost spanning tree in G. then every in- tree edge must be a minimum cost edge in the fundamental cut set associated with it

Proof:

            Let (p; q) be out-of-tree edge. If there is an in-tree-edge (i; j) on the fundamental cycle of (p; q) satisfying c_pq<c_ij, replacing (i; j) in T_0  by (p; q) leads to new spanning tree with cost = cost of T_0-(c_ij- c_pq) < cost of T_0,

          contradicting, the optimality of T_0. 

           So, c_pq must be ≧ the cost of every in-tree edge in the fundamental cycle of (p; q). 

 THEOREM 3:

  Any spanning tree in G satisfying every out of -tree edge has maximum cost in its fundamental cycle wrt that tree is a minimum cost spanning tree. 

Proof:

           Let T_1,T_2 be two distinct spanning trees in G satisfying, we will now prove that the cost of   T_1 and T_2 must be equal. 

Classify the edges in T_1∪T_2 into 3 classes. The T_1- edges are those which are in 

T_1  but not in T_2. The T_2  - edges are those in T_2   but not in T_1. The T_1 T_2- edges are those which are in both T_1 and T_2.

Since T_1  and T_2 are distinct, both of the sets of T_1- T_2- edges are non-empty.

Select any T_2- edges, say (r; s). let ρ_1  be the unique path in T_1 between r, s.

Then C_1={(r;s)}∪ρ_1 is the fundamental cycle of (r; s) wrt T_1.

          All the edges on ρ_1are in T_1, and at least one of them is not in T_2, a   otherwise T_2 contains the entire simply cycle C_1, a contradiction since T_2 is a tree. So, there are some T_1- edges on ρ_1. since T_1 satisfies, all these T_1- edges on ρ_1  have cost coefficients  ≦ c_rs. 

Claim:

         At least one of the T_1- edges on ρ_1  have cost coefficients  ≦ c_rs. 

We will prove the claim by contradiction. Suppose each  T_1- edges on ρ_1has cost < c_rs. Let (p; q) be T_1- edges on ρ_1. So,  c_pq<c_rs. (p; q) is an out-of-tree edges for T_2 , let s_pqbe the unique path between p and q in T_2. since T_2  satisfies (9.1) each edge (i; j) on s_pqsatisfies c_ij≦ c_pq< c_rs.   Hence s_pq does not contain the edge (r; s). replace theT_1- edge (p; q) on  ρ_1  by the path s_pq, but continue denoting it by the same symbol ρ_(1.) If there are other T_1- edge remaining on ρ_1,  carry out the same procedure for them. When this process is completed, the path ρ_1gets converted into path from r to s, not containing the edge (r; s), but completely completed contained in T_2, call it ρ at this stage. So, T_2contains the edge (r; s), and the path  ρ from r to s not containing the edge (r; s), a contradiction since T_2 is a tree. So, the claim must be true. 

So,at least one of the T_2- edges on ρ_1  has cost = c_rs

Suppose,it is (j_1,j_2 ).  replace (j_1,j_2 )  from  T_2  by (r; s).

This leads to a new spanning tree T_1 with the same cost as T_1, but it has one more edge in common with T_2.and it can be verified that it also satisfies. (9.1). if T_1^'  and T_2  are distinct, repeat this process again with them. After each repetition we get another spanning tree satisfying (9.1) and having the same cost as T_1, but containing one more edge in common with  T_2. So, after at most n-1 repetitions of this process it must leads to T_2. hence T_1and  T_2 have the same cost. 

There are only a finite number of spanning trees in G, and hence a minimum cost spanning tree exists in G. if T_0 is a minimum cost of spanning tree, it satisfies (9.1) by theorem 9.2. but we have just proved that any pair of spanning trees satisfying (9.1) have same cost. hence every spanning tree in G satisfying (9.1) is a minimum cost spanning tree.

THEOREM 4:

Let F be the set (possibly empty) of edges in a forest in G. let  (X;(X)) ̅ be cut in G containing none of the edges from F.  (p; q) is a minimum cost edge in the cut (X;(X)) ̅. Consider the problem of finding a minimum cost tree among the spanning trees of G containing all the edges in F. there is a minimum cost spanning tree for this problem which contains the edge (p; q). 

Proof:

           Since G is connected and F is the set of edges in a forest, there exists spanning trees of G which contain all the edges in F; let done. Suppose (p; q)∉ T_0 . let C be the fundamental cycle of (p; q) wrt T_0. since C is a cycle and it contain the edges (p; q) from the cut (X;(X)) ̅, it must contain at least another edge, (r; s)  from  (X;(X)) ̅. By the hypothesis (X;(X)) ̅,contain no edges from F, so (r; s)  ∉ F and since (p; q) is a minimum cost edge in (X;(X)) ̅ , c_pq≦ c_rs. Let T_1 be the spanning tree obtained by replacing (r; s) in T_0 with (p; q). since (r; s)  ∉ F, T_1 contains all the edges in F, and also the edge (p; q). if c_pq< c_rs. The cost of T_1 would be < cost of T_0,  contradicting the definition of T_0  . so, c_pq  must be equal c_rs, andT_1 is also a minimum cost one among the spanning tree of G containing all the edge in F, and it contains (p; q) proving the theorem. 

THEOREM 5:

  Let  F⊂A be the set of edges in a forest in a connected undirected network G. let C be a simple cycle in G, and (r; s) a maximum cost edge among those edges in C not among in F. Consider the problem of finding a minimum cost spanning tree among the spanning trees of G containing all the edges in F. there is a minimum cost spanning tree for this problem which not contain (r; s).

Proof:

          Let T_0   be a minimum cost spanning tree in G among those containing all the edges in F. if (r; s)∉ T_0   we are done. Suppose T_0 contains (r; s). 

Let (X;(X)) ̅ be the fundamental cut set of (r; s)  wrt T_0 . so, (r; s) is the only in-tree arc in (X;(X)) ̅ contains (r; s) from C , it must contain at least one other edge from C , suppose it is (p; q) is an out-of-tree edge on C and since, (p; q)∉F we have, c_rs> c_pq,cost of  T_1<cost of T_0, contradicting the definition of T_0   . so, we must be having  c_rs= c_pq , and   T_1is a minimum cost spanning tree among those containing all the edges in F, and does not contain (r; s).