1
$\begingroup$

We have a directed graph G where X is some vertex. For some vertex called S in graph G, if S has a path from X, it's also true that X has a path from S or $ X \leftrightarrow S$. Write a solution that shows any directed graph has atleast 1 vertex that satisfies these conditions.

What I don't understand is isn't it possible to have a directed graph with vertices that are not strongly connected? i.e. we can draw a graph such that there is a directed path from X to S but not from S to X which would make them reachable but not strongly connected? Would this still be defined as a directed graph or a DAG? Any tips or solutions on how to tackle this problem as I am genuinely lost. Thanks.

EDIT:

To clear it up this is what I meant;

Every digraph 𝐺 has a vertex X such that for any vertex S in the graph S, if there is a path from X to S , then there is a path from S to X. So $ X \leftrightarrow S$.

$\endgroup$
11
  • $\begingroup$ First of all, "strongly connected vertex" is not a standard term. Graphs can be strongly connected, not vertices. Second, consider that one option for a vertex that satisfies these conditions is a vertex $x$ such that there are no paths from $x$ to any other vertices at all - then "for every vertex $s$ with a path from $x$" translates to "for every vertex $s$ that is $x$". $\endgroup$ Commented Apr 30, 2023 at 19:28
  • $\begingroup$ Something in this question is missing and needs to be clarified, because there are extremely simple directed graphs that give counterexamples, as I am sure you could discover yourself. $\endgroup$
    – Lee Mosher
    Commented Apr 30, 2023 at 19:28
  • $\begingroup$ @LeeMosher No, it is a true statement, you are just not carefully reading the condition. $\endgroup$ Commented Apr 30, 2023 at 19:29
  • $\begingroup$ Huh... I read it again and it's false to me. Perhaps the sentence structure is throwing me off. $\endgroup$
    – Lee Mosher
    Commented Apr 30, 2023 at 19:33
  • 1
    $\begingroup$ @MishaLavrov my apologies I edited it. $\endgroup$ Commented Apr 30, 2023 at 20:03

1 Answer 1

1
$\begingroup$

First, to clarify some terminology:

  • A directed graph can be strongly connected if there is a path from every vertex to every other vertex. We can also define strongly connected components of a graph to be maximal subgraphs that are strongly connected. It is not correct to talk about a "strongly connected vertex". (The closest reasonable thing to this is "a vertex that is its own strongly connected component", which is not what we want in this problem.)
  • A directed graph is acyclic if it has no cycles; a directed acyclic graph is called a dag. All dags are directed graphs, but not all directed graphs are dags.

In this problem, we want to show that every directed graph has a vertex $x$ such that for all other vertices $s$, if there is a path from $x$ to $s$, then there is also a path from $s$ back to $x$. As a special case:

  • If a directed graph is strongly connected, then any vertex in the graph can be picked to be $x$, because all possible paths we might want exist.
  • If a directed graph is acyclic, then we cannot have nontrivial instances of paths going from $x$ to $s$ and from $s$ back to $x$; that would be a cycle. What we are looking for is a vertex $x$ such that there is no path from $x$ to any other vertex $s \ne x$; then the condition is satisfied trivially. (Exercise: every dag contains at least one such vertex.)

There is an important interaction between the two definitions at the beginning of this answer. For any directed graph $G$, we can define its condensation to be the directed graph $H$ whose vertices are the strongly connected components of $G$; for every pair of strongly connected components with some edge from one to the other, there is an edge in $H$. This is illustrated well on Wikipedia; I am borrowing that image to use below:

enter image description here

This can be used to solve the problem in general. Given a directed graph $G$, first find its condensation $H$; $H$ will always be acyclic, and there will always be a vertex in $H$ with no edges to any other vertex in $H$. That vertex corresponds to a set $X$ of vertices in $G$; check that every vertex $x \in X$ satisfies the condition we want.

It is also possible to solve the problem without using the language of condensations, though I think that language sheds some light on what is going on. Pick any vertex $x$ for which the set of vertices reachable from $x$ is as small as possible, and prove that such a vertex $x$ satisfies the condition we want.

$\endgroup$
2
  • $\begingroup$ I don’t understand how the set of X is the set of vertices we want if essentially X is a set of sink vertices? $\endgroup$ Commented Apr 30, 2023 at 22:17
  • $\begingroup$ Any vertex in $X$ can be the vertex we want. If $s$ is reachable from $x \in X$, then $s \in X$ as well, and so $x$ is reachable from $s$. $\endgroup$ Commented Apr 30, 2023 at 22:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .