2.5k views

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 | 2.5k views
0

Ques has been splitted.. Please check the below URL for part 'b'

https://gateoverflow.in/82129/gate2005-82b

0
can some one plz explain why not answer b if we use dynamic programming to find the shortest path from source to destination..plz explain...
0
The answer is A. We can prove this by a simple contradiction proof.

Suppose the given edge was not part of the minimum spanning tree. Now, since the minimum spanning tree is connected by definition, there exists another path from X to Y and another edge which crosses from set X to set Y which makes this path possible. But, this path's length has to be strictly greater than the previous one because the original edge, by definition, was the minimum. So any MST which doesn't contain that edge will not be minimum.

For 82a: The answer should be Option A because edge $e$ is the lightest safe edge connecting $X$ and $Y$ so the minimum spanning tree of $G$ must contain $e$ (Greedy and optimal choice).
While option $(B)$ might seem correct but it is not always true. One such case is when $G$ is not connected therefore there might not be any path between $s$ and $t$.
Since the question is about definitely TRUE, $(B)$ is incorrect and $(A)$ is the only correct option.

Lets say $AC =1$, $CD = 2$ ,$BD = 3$ and  $AB=4$

Then if  $s= A$  and  $t= B$ then $AC$  is the lightest edge crossing $X$ and $Y$ where  $X = { A }$  and $Y = { C, B, D}$
But clearly $AC$ is not on the shortest path from $A$ to $B$. The shortest path is $AB = 4$.

edited
+1

Though answer is correct but the given explanation is wrong!!

Lets say AC =1 CD = 2 BD = 3 and  AB=4
But clearly AC is not on the shortest path from A to B. The shortest path is AB = 4.

if the source is A, then AC with weight 1 will defnitely a part of shortest path, Shortest path means, there is a shortest path from source to each vertex. so AC will be selected.

PS: I assume that we are talking about Single Source Shortest Path

+1
Make spanning tree for that than find shortest path from source to every other vertex or not ?

Answer prove why b is false.
0
Regarding a part, the one who has explained, says that if we compute weighted shortest path on this above mentioned graph, then AC won't be in the shortest path. he wanted to prove option B wrong.

I just meant to say that, if we compute weighted shortest path and A is the source then AC will be selected in the single source shortest path.
I am not saying that Option B is correct, indeed Option A is correct.
+2
But clearly AC is not on the shortest path from A to B. The shortest path is AB = 4

by this line he want to say since in graph AB= 4 present but we cant take it since mst not contain AB edge.

AB = 7 we get using mst .
0
why not the answer b as it is written there are many edges between vertex set x and y. So there is no question of disconnected graphs?
0
If we use Bellman ford algo ... still will it be the case ??
0
@chandan1223.How could you take t as B inspite of AC is min weight amongst all those edges, so we have to take s=A and t=C
+1
Theorem 23.1-Cormen :)
+3

First 15 mins of this video explain this concept beautifully.

0

IS it the cut property of MST ??

Answer for 82 b) is option a) A path from s to t in MST.

T is the spanning tree and Eis the edge set of the tree.

Let L denote the set of all paths Pe in T where e is any edge in EG. For g ∈ ET , we define the congestion of g as the number of paths in L in which g is an element:

c(g, T) = |{Pe ∈ L : g ∈ Pe}|.

We then define the congestion of G embedded onto T as the maximum c(g, T) over all edges g in ET :

c(G : T) = max{c(g, T) : g ∈ ET }.

The tree congestion of G, denoted t(G), is the minimum value of c(G : T) over all trees T in TG. Similarly, the spanning tree congestion of G, denoted s(G), is the minimum value of c(G : T) over all spanning trees S in SG:

t(G) = min{c(G : T) : T ∈ TG},

s(G) = min{c(G : S) : S ∈ SG}

http://www.math.csusb.edu/reu/dt07.pdf

+1
could someone explain this in an easier way?
+1

I think answer to B part is option B.

(A)----5---(B)----5---(C)
|                     |
|----------7----------|

So in this example, A-C Shortest path is 7. But that will not be the path included in minimum spanning tree. Because spanning tree would be A->B->C

0
Yes you are true but acc. to question congestion (ato c ) is max  weight among  edges lies from a to c. Therefore for a to c in MST  congestion=5.

From a to c in weighted shortest path congestion = 7.

But you may be true in some cases when direct path is less than MST
For 82b answer is clearly option B and this concept is used in Link State Routing Algorithm.
0
the answer is A not B , the shortest path doesnt guarantee minimum congestion path.
+1

I think answer to B part is option B.

(A)----5---(B)----5---(C)
|                     |
|----------7----------|

So in this example, A-C Shortest path is 7. But that will not be the path included in minimum spanning tree. Because spanning tree would be A->B->C

0
Can anybody explain what is congestion here??

The minimum weight edge on any s-t cut is always part of MST. This is called Cut Property. This is the idea used in Prim's algorithm. The minimum weight cut edge is always a minimum spanning tree edge. Why B (the weighted shortest path from s to t) is not an answer? See below example, edge 4 (lightest in highlighted red cut from s to t) is not part of shortest path.

0
Shouldn't minimum weight edge 'e' be directly connected to s and t? As mentioned in the question that 'e' is minimum among those edges that have one vertex in X and another vertex in Y. Please feel free to correct me if I am wrong.

1
2