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

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.

---

nice explaination

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.

Answer 5

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 6

Lets understand this question in simple way first thing in the question they have mentioned that congestion means weight of an edge means whatever the weight of an edge is that is called the congestion according to question now second thing told in question is that " The congestion on a path is defined to be the maximum of the congestions on the edges of the path" this line means that whatever the path is from one vertex to another suppose s to t then congestion is the max of all edges weight for example lets suppose a path S - A - B - T then congestion on the path SABT is the MAX of edge weights S to A ,  A to B and B to T . Now We know MST minimum spanning tree picks up minimum edges first to construct the graph so the path given by MST will have the (max congestion = max of all minium edges from any path S to T) so that means mst will pick all min edges to construct graph so maximum of all these min edges will always be a path of minimum congestion though there can be a graph such that it equals MST or there can be a graph where weighted shortest path can also be answer but since in question its asked "always such a path of minimum congestion" so MST is the answer  Option A