Definition: Incidence, Adjacency, Predecessor and Successor Vertices, Neighbours

Let \(D=(V,E,\alpha,\omega)\) be a digraph. A vertex \(v\in V\) and an edge \(e\in E\) are called incident if \(v\in\{\alpha(e),\omega(e)\}\).

Two different edges \(e,e'\in E\) are called adjacent, if there is at least one vertex incident with these edges, formally \( e\neq e'\) and \(\exists v:~ v\in \{\alpha(e),\omega(e)\} \cap \{\alpha(e'),\omega(e')\} \).

Two different vertices \(v,v'\in V\) are neighbours or are called adjacent, if there is at at least one edge incident with these vertices. \( v\neq v'\) and \(\exists e:~v,v'\in \{\alpha(e),\omega(e)\} \).

Let \(v\in V\) be a vertex of \(D\). (Note: In the following definitions, the index \(D\) can be omitted in the notation, if it is clear from the context, which digraph \(D\) is concerned).

The set \(\delta_D^+(v):=\{e\in E: \alpha(e)=v\}\) is called edges outgoing from v.

The set \(\delta_D^-(v):=\{e\in E: \omega(e)=v\}\) is called edges incoming to v.

The set \(N_D^+(v):=\{\omega(e): e\in\delta_D^+(v)\}\) is called successor vertices of v or successors of v.

The set \(N_D^-(v):=\{\alpha(e): e\in\delta_D^-(v)\}\) is called predecessor vertices of v or predecessors of v.

The set \(N_D(v):=N_D^+(v)\cup N_D^-(v)\) is called the neighbours of v.



The values of the degrees of vertices in the above graph are:

Vertex \(v\) Neighbours \(N(v)\) Predecessors \(N^-(v)\) Successors \(N^+(v)\)
\(a\) \(\{b,c,d\}\) \(\{b\}\) \(\{b,c,d\}\)
\(b\) \(\{a,c\}\) \(\{a,c\}\) \(\{a\}\)
\(c\) \(\{a,b\}\) \(\{a\}\) \(\{b\}\)
\(d\) \(\{a,e\}\) \(\{a\}\) \(\{e\}\)
\(e\) \(\{d,e\}\) \(\{d,e\}\) \(\{e\}\)
\(f\) \(\emptyset\) \(\emptyset\) \(\emptyset\)

Definitions: 1 2 3 4

Thank you to the contributors under CC BY-SA 4.0!




  1. Krumke S. O., Noltemeier H.: "Graphentheoretische Konzepte und Algorithmen", Teubner, 2005, 1st Edition