Let s and t be two vetices
Let s and t be two vetices in a undirected graph G=(V,E) having distinct positive edge weights. Let [X,Y] be a partition of V such that s Î X and T Î Y. Consider the edge e having the minimum weight amongst all those edges that have one vertex in X and one vertex in Y.
(I) The edge e must definitely belong to:
(a) the minimum weighted spanning tree of G
(b) the weighted shortest path from s to t
(c) each path from s to t
(d) the weighted longest path from s to t
(II) Let the weight of an edge e denote the congestion on that edge. The congestion on a path is defined to be the maximum of the congestions on the edges of the path. We wish to find the path from s to t having minimum congestion. Which one of the following paths is always such a path of minimum congestion?
(a) a path from s to t in the minimum weighted spanning tree
(b) a weighted shortest path from s to t
(c) an Euler walk from s to t
(d) a Hamiltonian path from s to t
|
Linear Mode
