edited by
12,583 views
40 votes
40 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$.

The edge $e$ must definitely belong to:

  1. the minimum weighted spanning tree of $G$

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

  3. each path from $s$ to $t$

  4. the weighted longest path from $s$ to $t$

edited by

10 Answers

Best answer
41 votes
41 votes

The answer should be Option A because edge $e$ is the lightest safe edge connecting $X$ and $Y$ so the minimum spanning tree of $G$ must contain $e$ (Greedy and optimal choice).
While option $(B)$ might seem correct but it is not always true. One such case is when $G$ is not connected therefore there might not be any path between $s$ and $t$.
Since the question is about definitely TRUE, $(B)$ is incorrect and $(A)$ is the only correct option

Lets say $AC =1$, $CD = 2$ ,$BD = 3$ and  $AB=4$

Then if  $s= A$  and  $t= B$ then $AC$  is the lightest edge crossing $X$ and $Y$ where  $X = { A }$  and $Y = { C, B, D}$
But clearly $AC$ is not on the shortest path from $A$ to $B$. The shortest path is $AB = 4$.

edited by
6 votes
6 votes

Answer for 82 b) is option a) A path from s to t in MST.

T is the spanning tree and Eis the edge set of the tree.

Let L denote the set of all paths Pe in T where e is any edge in EG. For g ∈ ET , we define the congestion of g as the number of paths in L in which g is an element:

c(g, T) = |{Pe ∈ L : g ∈ Pe}|. 

We then define the congestion of G embedded onto T as the maximum c(g, T) over all edges g in ET :

c(G : T) = max{c(g, T) : g ∈ ET }. 

The tree congestion of G, denoted t(G), is the minimum value of c(G : T) over all trees T in TG. Similarly, the spanning tree congestion of G, denoted s(G), is the minimum value of c(G : T) over all spanning trees S in SG:

t(G) = min{c(G : T) : T ∈ TG},

s(G) = min{c(G : S) : S ∈ SG}

Please refer to the link 

http://www.math.csusb.edu/reu/dt07.pdf

6 votes
6 votes

The minimum weight edge on any s-t cut is always part of MST. This is called Cut Property. This is the idea used in Prim's algorithm. The minimum weight cut edge is always a minimum spanning tree edge. Why B (the weighted shortest path from s to t) is not an answer? See below example, edge 4 (lightest in highlighted red cut from s to t) is not part of shortest path. ShortestPathCut

5 votes
5 votes

 

Option: (A) the minimum weighted spanning tree of G

Consider the following graph-

Here, (A, D) is the edge e with weight 1.

The shortest path S to T is (S, T) which does not contain e. Therefore, option (B) is false.

Also, we can see that e is not part of every path from S to T. Therefore, option (C) is false.

Similarly, we show that there can be certain graphs where e is part of the shortest path from S to T.

However, we can see that e is the edge with the minimum weight that connects the vertex set X to vertex set Y, therefore, it must always be present in the MST.

Therefore, the correct option is (A).

Answer:

Related questions