edited by
12,603 views
40 votes
40 votes

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:

  1. the minimum weighted spanning tree of $G$

  2. the weighted shortest path from $s$ to $t$

  3. each path from $s$ to $t$

  4. the weighted longest path from $s$ to $t$

edited by

10 Answers

3 votes
3 votes
For 82b answer is clearly option B and this concept is used in Link State Routing Algorithm.
1 votes
1 votes
A) Since it is the minimum weighted edge it will automatically be selected in the MST

B) We suppose that from s to t there is a vertex involved s-->a-->t now s-->a is the edge with the max weight, and s-->t by other path has a comparatively cheaper path, so the least weighted edge might now always be included

C) Explanation to B solves this also

D) This is also not always possible as there can be paths with comparatively expensive weights which do not include this path
1 votes
1 votes

Correct answer : A

Explanation:-

Option A: e is the minimum weight edge among all the edges connecting X and Y, so there may be some other edge having weight less than e but belonging to X or Y. However, some edge connecting X and Y has to be included in the MST (otherwise the MST will become disconnected) and this edge will be e because it is the minimum among all the edges connecting X and Y.

Option B: There are two ways to view this option -

i) The path(s) between s and t containing e may not be the shortest path(s) between s and t

ii) The shortest path between s and t may not necessarily contain e.

This is because a path s->x->y->t connecting s and t, (where x->y is an edge connecting the partitions X and Y, s->x is a path from s to x and similarly y->t is a path from y to t) is not depending solely upon x->y. It is also depending upon s->x and y->t. Now even if we minimize x->y by choosing e, there is no guarantee that the other two paths are also minimized. So the minimum path will not necessarily contain e

Option C: e is not the only edge containing X and Y and hence a path from s to t can contain another edge.

Option D: Again, there can be paths from s to t which do not contain e but are more expensive.

Answer:

Related questions