Q82a

MCQMarks unknown

Let $s$ and $t$ be two vertices in a undirected graph $G=(V,E)$ having distinct positive edge weights. Let $[X,Y]$ be a partition of $V$ such that $s \in X$ and $t \in Y$ . Consider the edge $e$ having the minimum weight amongst all those edges that have one vertex in $X$ and one vertex in $Y$ . 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$

Loading…