nLab oriented graph

Contents

Contents

Idea

In graph theory, an orientation of an undirected graph is a choice of one of two possible directions for every edge. An oriented graph is an undirected graph equipped with an orientation.

Since the precise definition of “undirected graph” can vary depending on context (notably, whether one allows loops or multiple edges), the precise definition of “oriented graph” is likewise context dependent.

Definitions

Oriented simple graphs

In combinatorics, the most common sense of “oriented graph” is “simple graph equipped with an orientation”.

More formally: let (V2)\binom{V}{2} denote the set of two-element subsets of VV, and ΔV 2=V×V\Delta \hookrightarrow V^2 = V \times V the diagonal {(v,v):vV}\{(v, v): v \in V\}. Then there is a quotient map q:V 2Δ(V2)q: V^2 \setminus \Delta \to \binom{V}{2}, realizing (V2)\binom{V}{2} as the set of orbits of the fixed-point free involution (x,y)(y,x)(x, y) \mapsto (y, x) on V 2ΔV^2 \setminus \Delta. Then an oriented graph consists of a graph (V,E(V2)(V, E \hookrightarrow \binom{V}{2} together with a section of the quotient pp identified in the pullback diagram

F V 2Δ p q E (V2).\array{ F & \to & V^2 \setminus \Delta \\ \mathllap{p} \downarrow & & \downarrow \mathrlap{q} \\ E & \hookrightarrow & \binom{V}{2}. }

Equivalently, an oriented graph consists of a set VV and a subset EV 2E \hookrightarrow V^2 such that (x,y)E(x, y) \in E implies (y,x)E(y, x) \notin E. We may depict a pair (x,y)(x, y) in EE as an arrow from xx to yy. Of course the condition rules out loops (arrows from a vertex to itself), and evidently the notion of oriented graph is very different from the notion of digraph where 2-cycles are allowed (an arrow from xx to yy and another back from yy to xx).

More general graph orientations

If the underlying undirected graph is allowed to have loops and multiple edges, then an oriented graph is essentially the same thing as a directed graph (i.e., quiver).

Formally, let an undirected graph GG be given by a quiver s,t:EVs,t : E \rightrightarrows V together with a fixed point free involution i:EEi : E \to E such that si=ts\circ i = t and ti=st \circ i = s (in the style of Serre 1977). Then an orientation of GG consists of a subset E +EE^+ \subseteq E such that EE is the disjoint union E=E +i(E +)E = E^+ \uplus i(E^+).

Any such orientation induces a corresponding quiver G +=E +VG^+ = E^+ \rightrightarrows V. Conversely, any quiver EVE \rightrightarrows V can be seen as an orientation of the undirected Serre graph defined by adding a formal inverse to each edge.

Although the terms “oriented graph” and “directed graph” become essentially equivalent under this reading, in many situations it is useful to consider an oriented graph as one of the many possible orientations of a given undirected graph. For example, various graph invariants? (such as the flow polynomial?, or Tutte‘s original definition of the Tutte polynomial?) can be defined relative to an arbitrary orientation of a graph, but are independent of the choice of orientation.

References

  • W. T. Tutte, A contribution to the theory of chromatic polynomials. Canad. J. Math. 6:80–91, 1954. (doi)

  • Frank Harary (1969), Graph Theory, Addison-Wesley.

  • Jean-Pierre Serre (1977), Trees, Springer.

  • W. T. Tutte (1984), Graph Theory, Addison-Wesley.

Last revised on August 6, 2017 at 05:55:41. See the history of this page for a list of all contributions to it.