The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+22 votes
1.8k 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$

asked in Algorithms by Veteran (59.6k points)
edited by | 1.8k 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...

4 Answers

+20 votes
Best answer

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

answered by (217 points)
edited by
+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.
+1
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
0
Theorem 23.1-Cormen :)
0

First 15 mins of this video explain this concept beautifully.

+6 votes

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}

Please refer to the link 

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

answered by Active (4.1k 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
+3 votes
For 82b answer is clearly option B and this concept is used in Link State Routing Algorithm.
answered 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??
+2 votes

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

answered by Loyal (9k points)
Answer:

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

40,748 questions
47,471 answers
145,584 comments
62,234 users