2
$\begingroup$

For an undirected connected graph $G=(V,E)$ given as adjacency list I want to find a directed strongly connected graph $G=(V,E')$ where each $e' \in E'$ is either $(u,v)$ or $(v,u)$ if we look at its original $e=\{u,v\}$. Also we're assuming there are no bridges in the given graph G (which I'm checking before hand).

$\endgroup$
7
  • 2
    $\begingroup$ "Transform" is vague. You could add a new vertex that has an edge to and from every other vertex of the graph or, if the graph is connected, you could just replace each undirected edge $\{u,v\}$ with the two directed edges $(u,v)$ and $(v,u)$... but I doubt that's what you want as this would be trivial. Can you edit your question with a formal definition of your problem? $\endgroup$
    – Steven
    Nov 7 '19 at 13:55
  • $\begingroup$ Yeah, you are right, sorry. By transform I meant, every undirected edge {u, v} can either be transformed into (u, v) or (v, u), but not both. $\endgroup$
    – user106782
    Nov 7 '19 at 17:24
  • $\begingroup$ Then this is not possible in general. Think of a disconnected graph. If the graph has to be connected then think of a tree. $\endgroup$
    – Steven
    Nov 7 '19 at 17:26
  • $\begingroup$ I formalized the problem. Sorry I didn't find time to do this earlier. Is any more information needed? $\endgroup$
    – user106782
    Nov 8 '19 at 17:02
  • $\begingroup$ Iteratively do the following: 1) find a cycle $C$ in $G$, 2) orient the edges of $C$ in an arbitrary but consistent direction w.r.t. $C$, 3) Orient the chords of $C$ in an arbitrary direction. 4) identify the vertices in $C$ (ignoring self-loops but possibly creating parallel edges). If there are two or more vertices left in $G$ then there must still be a cycle (otherwise there was a bridge in $G$), therefore you will eventually be left with a single vertex. When this happens, all edges in the original graph $G$ must have been assigned a direction and you are done. $\endgroup$
    – Steven
    Nov 8 '19 at 18:04
3
$\begingroup$

The idea is that if we find a cycle in $G$, then we can orient its edges so that the nodes in the cycle will be all strongly connected. The cycle can then be collapsed into a single node. If the graph had no bridges the new graph will also have no bridges and this procedure can be repeated. Eventually, you will be left with a single node, meaning that the whole graph is a single strongly connected component, as desired.

More precisely, you can iteratively do the following:

  • Find a cycle $C $in $G$;

  • Orient the edges of $C = \langle u_1, u_2, \dots, u_k, u_{k+1} = u_1 \rangle$ in an arbitrary but consistent direction w.r.t. $C$. For example, for $i=1, \dots, k$ orient $(u_i, u_{i+1})$ towards $u_{i+1}$;

  • Orient the chords of $C$ in an arbitrary direction.

  • Identify the vertices in $C$, possibly creating parallel edges (but ignoring self-loops). This means replacing $u_1, \dots, u_k$ with a new super-vertex $\overline{u}$. For every edge $(x,y)$ where $x \in C$ and $y \not\in C$, add a new edge $(\overline{u}, y)$.

  • Repeat until a single vertex is left in $G$.

Notice that if there are two or more vertices left in $G$ then there must still be a cycle (otherwise there is a bridge that was also bridge in the original graph). This means that you will eventually be left with a single vertex. When this happens, all edges in the original graph $G$ must have been assigned a direction and you are done.

If you think of using the above algorithm while performing a single DFS visit to discover the cycles to contract, then all the cycles $C$ will be of the form $\langle u_1, \dots, u_k, u_{k+1} = u_1 \rangle$, where for $i=1,\dots,k-1$, $u_{i}$ is the parent of $u_{i+1}$ in the DFS tree, and $(u_k, u_1)$ is a back-edge. If you use the above choice for the orientation of the edges of $C$, then this is equivalent to this simpler algorithm:

  • Perform a DFS visit of $G$ from an arbitrary vertex $r$ to obtain a tree $T$.
  • Orient all the edges of $T$ away from $r$.
  • Orient the edges not in $T$ towards $r$ (notice that this is well defined since there will be no edges between two nodes at the same depth in $T$).

You can also give a direct proof that the orientation $G'$ computed by this second algorithm is a strongly-connected graph. It is clear that there is a path from $r$ to any other vertex in $G'$. The following claim implies the converse.

Claim: Let $(u,v)$ be an edge of $T$, with $u$ being the parent of $v$. There is a path from $v$ to $u$ in $G'$.

Proof: Since $(u,v)$ is not a bridge, there must be a cycle of the form $C = \langle u_1 = u, u_2 = v, u_3, \dots, u_k, u_{k+1} = u_1 \rangle$. Let $i$ be the smallest index in $\{1, \dots, k\}$ such that $u_i$ lies in the subtree $T_v$ of $T$ rooted at $v$ and $u_{i+1} \not\in T_v$ (this edge must always exist). Since $u_i \in T_v$, there is a (possibly empty) directed path $P$ from $v$ to $u_i$ in $G'$. Since $u_{i+1}$ is an ancestor of $v$ and $u_{i+1} \not\in T_v$, $u_{i+1}$ must be an ancestor of $u$ (possibly $u$ itself). This means that there is a (possibly empty) directed path $Q$ from $u_{i+1}$ to $u$ in $G'$. Finally, $(u_i, u_{i+1})$ is not a tree edge, hence it is directed towards $u_{i+1}$. This means that $P \circ (u_i, u_{i+1}) \circ Q$ is a path from $v$ to $u$ in $G'$ (where $\circ$ denotes concatenation). $\quad\square$

$\endgroup$

Your Answer

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