1
$\begingroup$

Suppose $G$ is a DAG with $n$ vertices, and $v$ is a vertex of $G$. What can we say regarding $v$ if the following holds:

A. In all topological sorts, $v$ is at the end of the list.

So my initial answer is that $v$ is the "sink" vertex, but in some case its not always correct, can't seem to find a feature that cant be said on $v$?

B. In all topological sorts, $v$ is at the top of the list.

So this one is the opposite which is the source vertex and has arrows coming out of him and no one points to him.

$\endgroup$
  • 1
    $\begingroup$ 'the "sink" vertex' -- this phrasing implies a DAG has exactly 1 sink vertex. $\endgroup$ – j_random_hacker May 2 '19 at 15:44
  • $\begingroup$ Is topological cue the result of topological sorting on a DAG? Is your graph a DAG? $\endgroup$ – George Vidalakis May 2 '19 at 15:45
  • $\begingroup$ @GeorgeVidalakis yes and yes $\endgroup$ – G95 May 2 '19 at 15:46
  • $\begingroup$ @j_random_hacker topoligical sorting can bring diffrent results, what can I say for on v of question A? $\endgroup$ – G95 May 2 '19 at 15:49
  • $\begingroup$ @GeorgeVidalakis: A sink is just a vertex with no out-edge. Your example DAG has two sinks. $\endgroup$ – j_random_hacker May 2 '19 at 16:23
1
$\begingroup$

A. Let's prove that $v$ will be a vertex which can be reached by every node (it is the mother vertex of the transpose of the graph) by contradiction. Suppose that there is a node $u$ such that $v$ is unreachable by it. Consider every node in the DAG reachable by $u$. There must be at least one node in this set that has no leaving edges. (Otherwise you could start from $u$ and always follow a leaving edge from the current node so after at most $|V| - 1$ steps you would visit an already visited node. But this implies a cycle which isn't allowd in a DAG.) So no other node is reachable by $u$ and $u$ could be last in a topological cue instead of $v$ and we reached a contradiction. As a result $v$ is reachable by every node. This is equivalent with (A)'s statement as a node being reachable by every node can appear only last in any topological cue.

Also $v$ is a sink because if it wasn't there would be at least one edge leaving it so it couldn't be at the end of any topological cue. (A)'s statement implies that $v$ is a sink but the reverse doesn't always hold.

B. $v$ is a mother vertex (every node is reachable by it). The proof is similar.

$\endgroup$

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.