# 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.

### Example:

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!

Github:

### References

#### Bibliography

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