= Strong orientation
{wiki}
A <strong orientation> is an <orientation of a graph> with <strong connectivity>: for every ordered pair $(u,v)$ of <vertices>, there is a <directed path> from $u$ to $v$. A length-zero <directed path> permits $u=v$. Ordinary <connectivity (graph theory)> of the underlying <undirected graph> is necessary, but does not ensure this two-way <reachability> after directions are chosen. The acyclic $D_1$ is not a <strong orientation>; the cyclic $D_2$ is, since a journey can continue around its <directed cycle>.
Attach a new <vertex> $D$ to that <triangle in a graph> by the single <edge> $CD$. This <edge> is a <bridge in a graph>. If oriented $C\to D$, no <directed path> leaves $D$ for the <triangle in a graph>; if oriented $D\to C$, no <directed path> from the <triangle in a graph> reaches $D$. Neither choice gives a <strong orientation>, even when the <triangle in a graph> itself is cyclically oriented. By contrast, the four-<vertex> <cycle graph> has the <strong orientation>
$$
A\to B\to C\to D\to A.
$$
Following this <directed cycle> reaches any requested <vertex> in at most three steps. Removing any one of its undirected <edges> leaves a <graph path> through all four <vertices>, so it has no <bridge in a graph>.
\Image[/graph-strong-orientation-bridge-obstruction-versus-cycle.png]
{title=A <bridge in a graph> obstructs a <strong orientation>, while a bridgeless <cycle graph> admits one}
For more than one <vertex>, a <strong orientation> cannot also be an <acyclic orientation>: <directed paths> from $u$ to $v$ and back give a nonempty <closed directed walk>, from which removing repeated portions leaves a <directed cycle>. A <directed graph> containing one <directed cycle> need not have <strong connectivity>, as the attached $D$ shows.
Back to article page
