GATE CSE 2005 | Question: 82b

Question

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

Let the weight of an edge $e$ denote the congestion on that edge. The congestion on a path is defined to be the maximum of the congestions on the edges of the path. We wish to find the path from $s$ to $t$ having minimum congestion. Which of the following paths is always such a path of minimum congestion?

• A. a path from $s$ to $t$ in the minimum weighted spanning tree

• B. a weighted shortest path from $s$ to $t$

• C. an Euler walk from $s$ to $t$

• D. a Hamiltonian path from $s$ to $t$

Comments

what is the meaning of the line?

Which of the following paths is always such a path of minimum congestion?

---

Congestion means → Crowding. Here edge cost = congestion size. We need the path with minimum crowding, i.e. among all the paths from $s$ to $t$, pick the path having the value of congestion the least. This path may not be the shortest path (i.e. the sum of weights of the edge weights in the path may be large), but every individual edge weight which is maximum of all other edge weights must be the least possible. 

---

here i will try to give some idea between a and b.
here, how they defined congestion:-
they are defineing edge weight as the congestion.(same as some time we defined edge weight as distance).
now assume we have a path from x-y  so there will be one edge in between these path whose weight will be maximum that will be congestion of this path.
------------------------------------------------------------------------------------------
how MST form by talking always small small weight .and recursivly we will keep on combining small small weight edge untill we are not getting the MST.
but how MSP(minimum shortest path form).
it try to create always distance between two vertices.it care about only the end result .
it tells their is a path of length x between y to z.without caring about what type of edge it include in between .

------------------------------------------------------------------------------------------------
now if you understood above idea
x----------y(a path and there are 100crore edge in between and each are having weight 1).

and there are also a edge between x-y which is of 5000 weight.
-----------------------------------------------------------------------------------------------

now what shortest path will do it will take one edge of 5000 weight.

and what mst does it will take all 100 crore edge where each edge are having weight one
-----------------------------------------------------------------------------------------
from here you can conclude.
a correct.

Answer 1

Here answer should be A.

Here, shortest path will give $6$.
Spanning tree contains edges of weights $2$,$3$,$4$ so congestion in this case is $ \max (2,3,4)$, that is, $4$. For path $s$ to $t$, overall congestion is $\max(3,4) =4$ but total weight is $7$.

Option $C$ and $D$ are I think not related to this question.

Comments

edge congestion means interconnected network so here the s and t is a vertex which is connect with every vertex???????????????

---

@akan

they are jus telling us to assume the weights as congestion thats ol

nothing else to be infered from that

---

This is a beautiful question where you can witness the fact that in case of applying single src shortest path between two nodes, we are looking at the sum of edge weights along the path between the nodes as the deciding factor, whereas in the question above at any particular instant we look at the crossing edges and decide which one is the minimum so that every edge weight along the path is trying not to raise the upper bound (which increases congestion) even though reaching the destination may require a large number of edges.

Answer 2

This is also based upon the cut property of the spanning trees.

For the property, I refer you to theorem 23.1 of Cormen 3rd edition.

Consider I have below scenario where I have two components, X and Y and vertex s lies in X and vertex t lies in Y.

I have recursively further divided the component of X into two more components X1 and X2 having vertex A and B respectively.

Consider congestion of edge S-A=3,S-B=2, A-T=5 and B-T=2.

At every step, I choose light edge (minimum weight edge which joins two distinct components of the graph)

So, first I select edge S-B. Then I select edge B-T and this path to T from S via B is of minimum congestion. And this is nothing but how your spanning tree algorithm works. 

Answer-(A)

Answer 3

Option A is Correct Only.

Answer 4

Since every edge has distinct edge weights. So, the edge with minimum weight will definitely be present in MST.