6,414 views
43 votes
43 votes

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$

5 Answers

Best answer
38 votes
38 votes

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.

edited by
12 votes
12 votes

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:

Related questions