Definition:Adjacent (Graph Theory)
Definition
Vertices
Undirected Graph
Let $G = \struct {V, E}$ be an undirected graph.
Two vertices $u, v \in V$ of $G$ are adjacent if and only if there exists an edge $e = \set {u, v} \in E$ of $G$ to which they are both incident.
Digraph
Let $G = \struct {V, E}$ be a digraph.
Two vertices $u, v \in V$ of $G$ are adjacent if and only if there exists an arc $e = \tuple {u, v} \in E$ of $G$ to which they are both incident.
Edges
Undirected Graph
Let $G = \struct {V, E}$ be an undirected graph.
Two edges $e_1, e_2 \in E$ of $G$ adjacent if and only if there exists a vertex $v \in V$ to which they are both incident.
Digraph
Let $G = \struct {V, E}$ be a digraph.
Two arcs $e_1, e_2 \in E$ of $G$ adjacent if and only if there exists a vertex $v \in V$ to which they are both incident.
Faces
Let $G = \struct {V, E}$ be a planar graph.
Two faces of $G$ are adjacent if and only if they are both incident to the same edge (or edges).
In the above diagram, $BCEF$ and $ABF$ are adjacent, but $BCEF$ and $AFG$ are not adjacent.
Also known as
Adjacent elements of a graph can also be described as neighboring (British English spelling: neighbouring).
Also see
- Results about adjacency in the context of graph theory can be found here.