Definition:Orientation (Graph Theory)

From ProofWiki
Jump to navigation Jump to search


Let $G = \left({V, E}\right)$ be a simple graph.

Let $H = \left({V, A}\right)$ be a directed graph.

Then $H$ is an orientation of $G$ if and only if both of the following hold:

$G$ is a simple digraph. That is, $A$ is antisymmetric.
$\forall x, y \in V: \left({ \left\{{x, y}\right\} \in E \iff \left({x, y}\right) \in A \lor \left({y, x}\right) \in A }\right)$

Note that every simple digraph is an orientation of exactly one simple graph, but a simple graph may have more than one orientation.