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