Nachbarschaft (Graphentheorie)

In der Graphentheorie versteht man unter der Nachbarschaft eines Knotens die Menge seiner adjazenten (also benachbarten) Knoten. Sie besteht aus allen Knoten des Graphen, die mit ihm durch eine Kante verbunden sind. Oft wird eine Adjazenzmatrix benutzt, um die Nachbarschaftsbeziehung zwischen den Knoten eines Graphen darzustellen.

Sei ${\displaystyle G=(V,E)}${\displaystyle G=(V,E)} ein ungerichteter Graph (welcher auch Schlingen enthalten kann). Dann heißen zwei Knoten ${\displaystyle u,v\in V}${\displaystyle u,v\in V} benachbart, verbunden oder adjazent in ${\displaystyle G}${\displaystyle G}, wenn sie durch eine ungerichtete Kante verbunden sind, wenn also ${\displaystyle \{u,v\}\in E}${\displaystyle \{u,v\}\in E} gilt. Sind zwei Knoten benachbart, so werden sie Nachbarn genannt. Ein Knoten ist genau dann sein eigener Nachbar, wenn er eine Schlinge besitzt.

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

Die Nachbarschaft ${\displaystyle N_{G}(X)}${\displaystyle N_{G}(X)} einer Knotenmenge ${\displaystyle X}${\displaystyle X} kann Knoten aus der Menge ${\displaystyle X}${\displaystyle X} selbst enthalten. Die Vereinigung der Nachbarschaft ${\displaystyle N_{G}(X)}${\displaystyle N_{G}(X)} mit der Knotenmenge ${\displaystyle X}${\displaystyle X} heißt abgeschlossene Nachbarschaft von ${\displaystyle X}${\displaystyle X}.

Ein Knoten ${\displaystyle v}${\displaystyle v} und eine Kante ${\displaystyle e}${\displaystyle e} heißen inzident, wenn ${\displaystyle e}${\displaystyle e} den Knoten ${\displaystyle v}${\displaystyle v} mit einem anderen Knoten verbindet (${\displaystyle v\in e}${\displaystyle v\in e}). Zwei ungerichtete Kanten heißen benachbart oder adjazent, wenn sie nicht disjunkt sind, d. h., wenn sie einen gemeinsamen Endknoten 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}${\displaystyle G} bei der Notation oftmals weg.

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

Analog heißt ${\displaystyle y}${\displaystyle y} Nachfolger von ${\displaystyle x}${\displaystyle x} in ${\displaystyle G}${\displaystyle G}, wenn ${\displaystyle (x,y)}${\displaystyle (x,y)} eine gerichtete Kante von ${\displaystyle G}${\displaystyle G} ist. Mit ${\displaystyle N_{G}^{+}(z)}${\displaystyle N_{G}^{+}(z)} bezeichnet man die Menge aller Nachfolger eines Knotens ${\displaystyle z}${\displaystyle z} in ${\displaystyle G}${\displaystyle G}. Ferner bezeichnet man mit ${\displaystyle N_{G}^{+}(Z)}${\displaystyle N_{G}^{+}(Z)} die Menge aller Nachfolger der Knoten von ${\displaystyle Z}${\displaystyle Z} in ${\displaystyle G}${\displaystyle G}. ${\displaystyle N_{G}^{+}(z)}${\displaystyle N_{G}^{+}(z)} beziehungsweise ${\displaystyle N_{G}^{+}(Z)}${\displaystyle N_{G}^{+}(Z)} nennt man die Nachfolgermenge oder Ausgangsmenge von ${\displaystyle z}${\displaystyle z} bzw. ${\displaystyle Z}${\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.

• Reinhard Diestel: Graphentheorie. Springer, Berlin 2010, ISBN 978-3-642-14911-5 (354 S.). 

1. ↑ H.W. Lang: Mathematische Grundlagen. Graph auf der Seite der Hochschule Flensburg, 1998 (abgerufen am 8. April 2023)

• Grundbegriff (Graphentheorie)