Definition:Orientation (Graph Theory)

From ProofWiki
Jump to navigation Jump to search


Let $G = \struct {V, E}$ be a simple graph.

Let $H = \struct {V, A}$ be a directed graph.

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

$(1): \quad H$ is a simple digraph. That is, $A$ is antisymmetric.
$(2): \quad \forall x, y \in V: \paren {\set {x, y} \in E \iff \tuple {x, y} \in A \lor \tuple {y, x} \in A}$

That is, $H$ is formed from $G$ by replacing every edge of $G$ with an arc.

Also see

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