# GATE2005-82b

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

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?

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

2. a weighted shortest path from $s$ to $t$

3. an Euler walk from $s$ to $t$

4. a Hamiltonian path from $s$ to $t$

19

Yes, (A) is the correct answer.
To make this question understand in layman language, there are many toll gates from electronic city to Bangalore airport.
The condition to pay the toll is, that I have to pay the amount equal to the maximum of all the amounts charged by any of the toll gates

Path 1 - There is only one toll gate from electronic city to Airport, and that toll gate charges 60 rs.
Path 2 -  There are 10 toll gates on the another way from electronic city to airport, and all of the toll gates charge 8-8 rupees only or may be not more than 10 rs by any toll gate.

My aim is to the save the money then i will take path 2, as i have to pay maximum 10 rs only.

0
can somebody tell me what does congestion mean in this question
0

say s=A and t=C,

Path with minimum congestion is the directly given edge.

If in minimum spanning tree if AC edge is not included then the path with minimum congestion will be A-D-F-C which is not minimum. So option a is wrong and option b is correct.

0

@sunil,in question it is mentioned that "Let s and t be two vertices in a undirected graph G=(V,E) having distinct positive edge weights".

0
When we apply Prim's algorithm, we are basically finding the path of least congestion. That's because we are always choosing the lightest (least congested) edge and so we are guaranteed to find the least congested path from the starting vertex to every other vertex.
0
Can someone please explain what a congestion is?

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.

edited
0

Consider the following graph

In this case minimum weight spanning tree is  s - a - b - t and s -a is the minimum weighted edge but the minimum congestion path from s to t is s - t having congestion 11. Shouldn't the answer be option B?

1
In mst a to b should not included ...

Mst for Ur graph will be...

s-a  , s-t and t-b

Use kruskal for clear picture !
0
You are right, i was finding the mst incorrectly, thanks.
0
edge congestion means interconnected network so here the s and t is a vertex which is connect with every vertex???????????????
0
@akan

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

nothing else to be infered from that
1
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.

Option A is Correct Only.

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.

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

## Related questions

1
4.2k 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 ... tree of $G$ the weighted shortest path from $s$ to $t$ each path from $s$ to $t$ the weighted longest path from $s$ to $t$
Let $G(V,E)$ be an undirected graph with positive edge weights. Dijkstra’s single source shortest path algorithm can be implemented using the binary heap data structure with time complexity: $O\left(|V|^2\right)$ $O\left(|E|+|V|\log |V|\right)$ $O\left(|V|\log|V|\right)$ $O\left(\left(|E|+|V|\right)\log|V|\right)$
We are given $9$ tasks $T_1, T_2, \dots, T_9$. The execution of each task requires one unit of time. We can execute one task at a time. Each task $T_i$ has a profit $P_i$ and a deadline $d_i$. Profit $P_i$ is earned if the task is completed before the end of the $d_i^{th}$ unit ... $} & \text{$7$} & \text{$3$} \\\hline \end{array}$ What is the maximum profit earned? $147$ $165$ $167$ $175$
We are given $9$ tasks $T_1, T_2, \dots, T_9$. The execution of each task requires one unit of time. We can execute one task at a time. Each task $T_i$ has a profit $P_i$ and a deadline $d_i$. Profit $P_i$ is earned if the task is completed before the end of the ... gives maximum profit? All tasks are completed $T_1$ and $T_6$ are left out $T_1$ and $T_8$ are left out $T_4$ and $T_6$ are left out