2
$\begingroup$

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?

$A)w^* \geq \sum_{u \in V \backslash \{r\}} \min_{(u,v) \in E} w((u,v))$

$B)w^* \geq \sum_{u \in V \backslash \{r\}} \min_{(v,u) \in E} w((v,u))$

$C)H^*$ has exactly $n-1$ edges

$D)H^*$ is acyclic

$E)w^*$ is less than the weight of the minimum weight directed Hamiltonian cycle in $G$, when $G$ has a directed Hamiltonian cycle


I tried like this 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

enter image description here

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)

$\endgroup$
  • $\begingroup$ Is there any difference between option A) and B)?? $\endgroup$ – Srestha Jun 8 at 15:30
  • $\begingroup$ Yes, see the answer below. $\endgroup$ – paulinho Jun 8 at 15:56
  • $\begingroup$ If the answer is correct and you are satisfied with it, please accept the answer. Otherwise, do specify what needs to be improved/any lingering concerns you have. $\endgroup$ – paulinho Jun 8 at 17:12
2
$\begingroup$

Paulinho is correct that A is true and B is false.

In fact all other options are true (which is good, since it means there is only one correct answer to the question).

First, C is true because in a minimum arborescence every vertex has at most one outgoing edge (and $r$ has none). To see this, suppose $x$ has two outgoing edges in the arborescence, to $y$ and $z$. Since there is a directed path from $y$ to $r$ we can remove the edge $xz$ and every vertex still has a path to $r$, giving an arborescence of smaller weight since $w(xz)>0$. Similarly if $r$ has an outgoing edge we can remove it without breaking any paths to $r$. Since clearly every vertex except $r$ must have at least one outgoing edge, there are exactly $n-1$ edges. It also follows that there are no cycles. Suppose there is a cycle in the arborescence. If it includes $r$, $r$ has an outgoing edge, which we proved couldn't happen. If not, there is some path from a vertex on the cycle to $r$. At the point where this path leaves the cycle, there are two outgoing edges, one along the cycle and one along the path, but again we know this can't happen.

Finally, if there is a Hamilton cycle in the graph, we can take all edges in the cycle except the one leaving $r$. This is an arborescence, and its weight is strictly less than the cycle, since we removed an edge. (This demonstrates why paulinho's counterexample isn't valid - the edge leaving $r$ is superfluous.)

$\endgroup$
2
$\begingroup$

Statement $A$ is true: it is proposing that the minimum arborescence weight of the graph is greater than the sum of the minimum outgoing weights of each vertex. This is true because for every vertex $v \in V \backslash \{r\}$, the minimum arborescence must contain at least one directed edge from $v$ to some other vertex. Otherwise, $v$ is not connected to the rest of the graph and there exists no directed path from $v$ to $r$, a contradiction.

Statement $B$ is false: it is proposing that the minimum arborescence weight of a graph is greater than the sum of the minimum ingoing weights of each vertex. Consider the graph made of three vertices, $v_1, v_2, v_3$ and directed edges $w(v_2 \rightarrow v_1) = 1, w(v_3 \rightarrow v_1) = 1, w(v_3 \rightarrow v_2) = 5$. The minimum arborescence has root $v_1$, is comprised of the edges $\{ v_3 \rightarrow v_1, v_3 \rightarrow v_2 \}$, and has weight $2$. Meanwhile, the sum of the minimum ingoing weights of each vertex are $5 + 1 = 6$. The idea here is that, while there must be outgoing edges from each vertex in the arborescence, there need not ingoing edges to each vertex.

Statement $C$ is false: consider a graph with $n$ vertices, $\{v_0, v_1 ,\cdots v_{n - 1} \} $ such that there is a directed edge from $v_i \implies v_{(i + 1) \text{ mod } n}$. This is just a very simple cyclic graph with $n$ vertices. Choose any arbitrary $v_i$ as $r$, and we have a minimum arborescence rooted at that vertex. But this minimum arborescence (which is also the graph itself) contains $n$ edges.

Statements $D$ and $E$ are also false, using the same counterexample from above. However, note that if statement $E$ instead "$w^*$ is less than or equal to the weight of the minimum directed Hamiltonian cycle," then this would be true. This is because the Hamiltonian cycle itself is an arborescence, so any minimum arborescence must have a lesser or equal weight to it.

$\endgroup$
  • $\begingroup$ what is "arborescence"?? I might be wrong for this term $\endgroup$ – Srestha Jun 8 at 15:53
  • $\begingroup$ The only definition of it I know is yours: a collection of directed edges $D$ in a graph such that there exists a directed path from each vertex in the graph to a vertex $r$ using only edges in $D$. $\endgroup$ – paulinho Jun 8 at 15:55
  • $\begingroup$ how will it be look like? Is my diagram not correct? $\endgroup$ – Srestha Jun 8 at 16:05
  • $\begingroup$ The arborescence of that graph has four edges, comprised of those from each vertex that is not $r$ to vertex $r$. $\endgroup$ – paulinho Jun 8 at 16:09
  • 1
    $\begingroup$ Take the four leftmost vertices (they form a square). Notice how there is an edge from each of those vertices directly to $r$. Those four edges form an arborescence. $\endgroup$ – paulinho Jun 8 at 16:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.