The Gateway to Computer Science Excellence
+3 votes

Let $G=(V,E)$ be a directed graph with $n(\geq 2)$ vertices, including a special vertex $r$. Each edge $e \in E$ has a strictly positive edge weight $w(e)$. An arborescence in $G$ rooted at $r$ is a subgraph $H$ of $G$ in which every vertex $u \in V \backslash \{r\}$ has a directed path to the special vertex $r$. The weight of an arborescence $H$ is the sum of the weights of the edges in $H$.

Let $H^*$ be a minimum arborescence rooted at $r$, and $w^*$ the weight of $H^*$. Which of the following is $NOT$ always true?

  1. $w^* \geq \sum_{u \in V \backslash \{r\}} \min_{(u,v) \in E} w((u,v))$
  2. $w^* \geq \sum_{u \in V \backslash \{r\}} \min_{(v,u) \in E} w((v,u))$
  3. $H^*$ has exactly $n-1$ edges
  4. $H^*$ is acyclic
  5. $w^*$ is less than the weight of the minimum weight directed Hamiltonian cycle in $G$, when $G$ has a directed Hamiltonian cycle
in Graph Theory by Veteran
edited by | 489 views
This was the toughest question!
Ans will be D)
Struggled for 15 minutes eliminated few options I was getting B. Idk how took few examples. Pls, share your approach!

Here it is saying a graph given G

and it has a special vertex r

Now, H is subgraph of graph G and every vertex of H which has a directed edge to r

Now I thought G is a graph like this

Now as H is any subgraph of G, So, A) and B) false , there is always a subgraph which contains minimum weight of the graph

C) false because H may not contain exactly n-1 edges. 

E) False , because H and G can be both same graph (i.e. improper subgraph)

One case definitely there , where it is false

Now D) H is cyclic or not totally depend on ur designing of graph

So, it is not always true (See in the above diagram, if H=G, then It contains a cycle)



@srestha You have to read and understand the question CORRECTLY before solving. Otherwise you are spending time and getting negatives. 

1 Answer

+5 votes

For these questions it is better to get some counter examples by trying small graphs. Consider the following graph:

Now, as per the question, an arborescence is a subgraph with all incoming edges to the special vertex $r.$ So, for the above graph it is just the edge $a-r$ which is of weight $2.$

Now, option A says that if we sum up outgoing the edge weights (minimum weight in case multiple edges exist) of all vertices excluding $r$, the sum will be greater than or equal to the weight of the minimum arborescence. This is true because all the edges in the minimum arborescence will be including as the outgoing edges of the other vertices. 

Now, option B is false. Because instead of outgoing edges we are adding the weights of incoming edges. And these edges are not part of the arborescence. For example, in the above graph, only one vertex $a \in V \backslash \{r\}.$

$ \sum_{u \in V \backslash \{r\}} \min_{(v,u) \in E} w((v,u)) = w(r,a) = 5 >  w^*.$

Options C and D are straightforward TRUE as for minimum arborsecence we only need to consider the incoming edges to $r$ from $n-1$ other vertices thus making it acyclic too. 

For option E, suppose a graph has a directed Hamiltonian cycle and its weight is $\leq$ $w^*.$ Since Hamiltonian cycle on a graph of $n$ vertices must consist of $n$ edges and $H^*$ has only $n-1$ edges and all edge weights being positive, this means there is at least one edge $e'$ in $H^*$ which is having a weight larger than any other edge in Hamiltonian cycle. Is this possible? Consider the below graph:

Here, Hamiltonian cycle is $a - b - c - r - a$ and its weight will be $1+1+2+1 = 5.$

Minimum arborescence (shown by thick edges) has the edges $a-r,b-r,c-r$ and its weight will be $2+100+2 = 104.$ So, we have a counter example for option E. 

So, Correct answer: B, E. 

by Veteran 1 flag:
✌ Edit necessary (Aalok8523 “Sir, you readed option(A) incorrectly in question. That's why you provided explaination for converse of option(A). Please review it because it can effect final answer also.”)

For the hamiltonian cycle example I think we have to consider the edges $a\rightarrow b,b \rightarrow c,c \rightarrow r$, resulting into total $w^{*}=1+1+2=4$ which is less than the weight of the hamiltonian cycle$=5$,

Hence E should be true.

I am considering  $a \rightarrow b,b \rightarrow c,c \rightarrow r$ this directed path to $r$ in the arborescence because it is mentioned in the question :

An arborescence in $G$ rooted at $r$ is a subgraph $H$ of $G$ in which every vertex $u∈V\backslash \{r\}$ has a directed path to the special vertex $r$

A better explanation of why E should be true can be found here 

TIFR answer key Q - B-12

@Arjun sir, please review comment of @Sourajit25. I am also thinking that, example for hamilton cycle provided by you is not counter example for option(E). Please suggest some another example.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,217 questions
59,951 answers
118,172 users