Definition:Incident (Graph Theory)

From ProofWiki
Jump to navigation Jump to search

Definition

Undirected Graph

Let $G = \left({V, E}\right)$ be an undirected graph.

Let $u, v \in V$ be vertices of $G$.


Let $e = \left\{{u, v}\right\} \in E$ be an edge of $G$:

IncidentGraph.png

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$:

IncidentDigraph.png

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

PlanarGraph.png


Let $G = \left({V, E}\right)$ 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 $ABHC$ is incident to:

the edges $AB, BH, HC, CA$
the vertices $A, B, H, C$.