= Orientation of a graph
= Orientations of a graph
{synonym}
A choice of direction for each edge of an undirected <graph>, producing a <directed graph>.
An <orientation of a graph> keeps the same <vertex set> and the same individual <edges>. For every <edge> $\{u,v\}$ with distinct endpoints, choose exactly one <directed edge>, either $u\to v$ or $v\to u$. Replacing it by both arrows is a different construction: it doubles the <edges> and permits travel both ways along that connection. In an <orientation of a graph>, the return journey must use another route.<Graph Theory by Reinhard Diestel/The Basics (author-hosted chapter preview)>[§1.10, printed p. 28: an orientation retains the vertex and edge sets and assigns initial and terminal endpoints]{ref}
All examples below use finite <simple graphs>: no <self-loops> and no <multiple edges>. For a <multigraph>, each individual nonloop <edge> receives its own direction, so two <multiple edges> can point in opposite directions. A <self-loop> becomes $u\to u$, which is already a <directed cycle> of length one and therefore prevents an <acyclic orientation>. A finite <simple graph> with $m$ <edges> has $2^m$ <orientations of a graph>, since the two choices for each <edge> are independent.
Think of <vertices> as junctions and <edges> as streets. An <orientation of a graph> makes each street one-way; <reachability> asks whether a legal journey exists from one specified junction to another. Two useful aims pull in different directions: an <acyclic orientation> rules out circular dependencies, while a <strong orientation> permits journeys between every ordered pair of junctions.
Back to article page
