a) Consider
green 1
________________
red 1 | | green 2
| |
*imagine diagonals* with red 500 and red 2.
Could not explain better without diagram...
hope it's clear
b) Make a spanning tree of red.
Now modify the weights of green as = original weight - max weight of the red
that can be replaced on adding this in the cycle formed.
Include the min wt green edge.
Proof trivial
-Rohit
On Sat, Apr 3, 2010 at 11:38 PM, shruti s <[email protected]> wrote:
> 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]<algogeeks%[email protected]>
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
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.
