3k 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 | 3k views
+1

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.

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$.

by (217 points)
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
+2
Theorem 23.1-Cormen :)
+6

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

by Active (3.8k points)
+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

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. by Boss (10.2k points)
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.
For 82b answer is clearly option B and this concept is used in Link State Routing Algorithm.
by (217 points)
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??

Option: (A) the minimum weighted spanning tree of G

Consider the following graph- Here, (A, D) is the edge e with weight 1.

The shortest path S to T is (S, T) which does not contain e. Therefore, option (B) is false.

Also, we can see that e is not part of every path from S to T. Therefore, option (C) is false.

Similarly, we show that there can be certain graphs where e is part of the shortest path from S to T.

However, we can see that e is the edge with the minimum weight that connects the vertex set X to vertex set Y, therefore, it must always be present in the MST.

Therefore, the correct option is (A).

by Junior (831 points)
0

@Debargha Bhattacharj

AD is nothing but another name of ST according to question. Isnot it??

Actually among option A) and B) both could be true.

But A) is more meaningful and logical than B).

So, A) is best choice. rt??

+1

@srestha

AD is nothing but another name of ST according to question. Isnot it??

I don't think so. Actually, s and t are two specific vertices in the vertex sets X and Y respectively, which, in the figure, I have mistakenly represented using equivalent uppercase letters.

Now, it is mentioned in the question that among all the edges that connect some vertex in X to some other vertex in Y, e is the edge having the minimum weight. In the above example, e is actually the edge AD with weight 1.

Now, using the example of the above graph, we can eliminate option (B), (C) and (D).

0
yes, right.
+1 vote
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
by (55 points)
+1 vote

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.

by (37 points)