Nachbarschaft (Graphentheorie)

Ungerichteter Graph, die Nachbarschaft von Knoten 1 ist {1,2,5}, die von 6 ist {4}

Sei ${\displaystyle G=(V,E)}$ ein ungerichteter Graph (welcher auch Schlingen enthalten kann). Dann heißen zwei Knoten ${\displaystyle u,v\in V}$ benachbart, verbunden oder adjazent in ${\displaystyle G}$, wenn sie durch eine ungerichtete Kante verbunden sind, das heißt, wenn ${\displaystyle \{u,v\}\in E}$ gilt. Sind zwei Knoten benachbart, so werden sie auch Nachbarn genannt.

${\displaystyle N_{G}(v)}$ bezeichnet die Menge aller Nachbarn eines Knotens ${\displaystyle v}$ in ${\displaystyle G}$. Ferner bezeichnet man mit ${\displaystyle N_{G}(X)}$ die Menge aller Nachbarn der in ${\displaystyle X\subseteq V}$ enthaltenen Knoten. Diese Mengen werden auch die Nachbarschaft von ${\displaystyle v}$ bzw. ${\displaystyle X}$ genannt.

Ein Knoten ist genau dann sein eigener Nachbar, wenn er eine Schlinge besitzt. Die Nachbarschaft ${\displaystyle N_{G}(X)}$ einer Menge ${\displaystyle X}$ von Knoten kann Knoten aus der Menge ${\displaystyle X}$ selbst enthalten. Die Vereinigung der Nachbarschaft mit den Knoten aus ${\displaystyle X}$ heißt abgeschlossene Nachbarschaft.

Ein Knoten ${\displaystyle v}$ und eine Kante ${\displaystyle e}$ heißen inzident, wenn ${\displaystyle e}$ den Knoten ${\displaystyle v}$ mit einem anderen Knoten verbindet (${\displaystyle v\in e}$). Zwei ungerichtete Kanten heißen benachbart, wenn sie nicht disjunkt sind, d. h., wenn sie einen gemeinsamen Knoten besitzen.

Diese Begriffe gelten analog für Hypergraphen und -kanten. Falls klar ist, um welchen Graphen es sich handelt, lässt man den Index ${\displaystyle G}$ bei der Notation oftmals weg.

Ein Knoten ${\displaystyle x}$ heißt Vorgänger von ${\displaystyle y}$ in einem gerichteten Graphen ${\displaystyle G}$, wenn ${\displaystyle (x,y)}$ gerichtete Kante von ${\displaystyle G}$ ist. Mit ${\displaystyle N_{G}^{-}(z)}$ bezeichnet man die Menge aller Vorgänger eines Knotens ${\displaystyle z}$ in ${\displaystyle G}$. Ferner bezeichnet man mit ${\displaystyle N_{G}^{-}(Z)}$ die Menge aller Vorgänger der Knoten von ${\displaystyle Z}$ in ${\displaystyle G}$. ${\displaystyle N_{G}^{-}(z)}$ bzw. ${\displaystyle N_{G}^{-}(Z)}$ nennt man auch Vorgängermenge oder Eingangsmenge von ${\displaystyle z}$ bzw. ${\displaystyle Z}$.

Analog heißt ${\displaystyle y}$ Nachfolger von ${\displaystyle x}$ in ${\displaystyle G}$, wenn ${\displaystyle (x,y)}$ gerichtete Kante von ${\displaystyle G}$ ist. Mit ${\displaystyle N_{G}^{+}(z)}$ bezeichnet man die Menge aller Nachfolger eines Knotens ${\displaystyle z}$ in ${\displaystyle G}$. Ferner bezeichnet man mit ${\displaystyle N_{G}^{+}(Z)}$ die Menge aller Nachfolger der Knoten von ${\displaystyle Z}$ in ${\displaystyle G}$. ${\displaystyle N_{G}^{+}(z)}$ beziehungsweise ${\displaystyle N_{G}^{+}(Z)}$ nennt man auch Nachfolgermenge oder Ausgangsmenge von ${\displaystyle z}$ bzw. ${\displaystyle Z}$.[1]

Bei gerichteten Graphen unterscheidet man weiter zwischen positiv inzidenten Kanten und negativ inzidenten Kanten. Eine gerichtete Kante ist positiv inzident zu ihrem Startknoten und negativ inzident zu ihrem Endknoten.