Hi, Please help me to solve following problems
Let *G *= (*V; E;w*) be a weighted undirected graph whose edges are colored either red or green. That is *E *= *Er [ Eg *and *Er \ Eg *= *;*, where *Er *are the red edges and *Eg *are the green edges. Assume that all edge weights are distinct (so that the minimum spanning tree is unique). Also assume that there is at least one green edge. Suppose that the minimum spanning tree, *T*0, consists entirely of red edges. Let *T*1 be the minimum-cost tree among the spanning trees that have exactly one green edge. (a) Show, by giving an example, that *T*1 does not necessarily include the lowset-cost green edge. (b) Prove that *T*1 can be obtained from *T*0 by swapping a red edge for a green edge. That is, there exists a green edge (*u; v*) and a red edge (*x; y*) such that *T*1 = * T*0 *[ f*(*u; v*)*g ยก f*(*x; y*)*g*. Thanks -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
