University of Texas, Dallas - CS 6363sol6

Document Content and Description Below

Assignment #6: 1. 23.1-2; 23.1-3; 23.1-4 Solutions: 23.1-2: The set A are the blue edges; edge (u, v) is the red edge. The cut is marked in blue. 6 23.1-3: When an edge of a spanning tree is... removed from the tree, it creates two disconnected components of the tree. The nodes corresponding to these two trees corresponds to a cut in the original graph. We do this with the edge (u, v) (= (E, H)) in the tree as shown below; A B I C H E G F D 4 4 8 7 2 2 1 9 A B I C H E G F D 4 7 11 8 4 8 7 2 2 1 10 14 9 6 For this cut, the edge (u, v) is a light edge; else exchanging the light edge crossing this cut with edge (u, v) will provide a better tree which contradicts optimality of this tree. [Show More]

Last updated: 1 year ago

Preview 1 out of 6 pages