1
$\begingroup$

I am not sure how to go about this exactly. My attempt is find the pick an arbitrary node and run DFS, ordering each node by order of discovery. After this, You can orient each of edges so it pointing from lower order to higher order. Now I know this will create a path from one node to another, but doesn't guarantee a path from the other back to the initial. Is there any way to modify my algorithm so that it it would strongly connected and not just connected.

$\endgroup$
0
1
$\begingroup$

Well the idea of dfs is quite good all you need to orient all edges away from the vertex that discovered them.

You will have a path from the root to each vertex since the graph is connected and the dfs will visit all vertices.

Claim. From each vertex you can reach the root.

Proof. Let $\mathcal{C}$ be the strongly connected components of the resulting graph. Let $\mathcal{G}$ be the DAG resulting from contracting the vertices in each component in $\mathcal{C}$. Also, let $C_0 \in \mathcal{C}$ be the strongly connected component containing $r$. We have to prove that $C_0$ is the only component in $\mathcal{C}$ and hence, it contains all the vertices in the graph. Assuming otherwise, all components must be reachable from $C_0$ in $\mathcal{G}$, since all vertices are reachable from $r$ in $G$. choose $C$ to be a component in $\mathcal{C}$ that is the end of a longest path $P$ from $C_0$ in $\mathcal{G}$. Let $C'$ be the component previous to $C$ on that path. There is an edge from a vertex in $C'$ to a vertex in $C$. But this edge is not a bridge, hence, there must be an edge leaving $C$ and directed from $C$ to outside $C$ (since such an edge must have been discovered the first time we visited $C$). If this edge goes to a component $C''$ not on $P$, we could have extended $P$ to $C''$ resulting in a longer path wich is a contradiction. On the other hand, if it goes to a component on $P$, it forms a cycle, which contradicts the assumption that $\mathcal{G}$ is the DAG over the SCCs of the graph we build from $G$ and hence cannot have cycles. Hence, $\mathcal{C}$ cannot have more than one component, namely $C_0$.

$\endgroup$
4
  • 1
    $\begingroup$ Coud you expand on "If v doesn‘t have an edge to a vertex with smaller order, then the edge entering v is a bridge"? I don't yet see what rules out the possibility that v has edges only to higher-numbered vertices, but can reach a lower-numbered vertex through at least one of them. $\endgroup$ Dec 23 '19 at 0:18
  • 1
    $\begingroup$ @j_random_hacker Oh, I am so sorry, the proof was not correct. But I still think the solution is correct, since the DFS seems to highlight an euler-tour as a subgraph. I updated the proof. I hope it is fine now. $\endgroup$ Dec 23 '19 at 1:26
  • $\begingroup$ Thanks, this looks better. I had to think about the claim that some edge leaving $C$ is necessarily directed from $C$ to outside $C$: Suppose to the contrary that all such edges are directed the other way, and there is at least 1 such edge. Call these edges $F$. Let $uv$ be the edge from $C'$ to $C$. ... $\endgroup$ Dec 30 '19 at 13:40
  • $\begingroup$ ... After visiting $v$, DFS will not backtrack to a vertex it discovered before $u$ until it has visited all vertices reachable from $v$, which includes at least all vertices in $C$ and their neighbours, so each edge in $F$ is discovered at the end of a directed path starting at $v$ -- which must have left $C$ before returning via the edge in $F$. Since $|F|\ge 1$, some edge leaves $C$. $\endgroup$ Dec 30 '19 at 13:40

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