Definition:Incident (Graph Theory)
Jump to navigation
Jump to search
Definition
Undirected Graph
Let $G = \struct {V, E}$ be an undirected graph.
Let $u, v \in V$ be vertices of $G$.
Let $e = \set {u, v} \in E$ be an edge of $G$:
Then:
- $u$ and $v$ are each incident with $e$
- $e$ is incident with $u$ and incident with $v$.
Digraph
Let $G = \struct {V, E}$ be a digraph.
Let $u, v \in V$ be vertices of $G$.
Let $e = \tuple {u, v}$ be an arc that is directed from $u$ to $v$:
Then the following definitions are used:
Incident From
- $e$ is incident from $u$
- $v$ is incident from $e$.
Incident To
- $e$ is incident to $v$
- $u$ is incident to $e$.
Planar Graph
Let $G = \struct {V, E}$ be a planar graph:
Then a face of $G$ is incident to an edge $e$ of $G$ if $e$ is one of those which surrounds the face.
Similarly, a face of $G$ is incident to a vertex $v$ of $G$ if $v$ is at the end of one of those incident edges.
In the above graph, for example, the face $BCEF$ is incident to: