Nachbarschaft (Graphentheorie)

Menge aller Knoten des Graphen, die mit ihm durch eine Kante verbunden sind

In der Graphentheorie versteht man unter der Nachbarschaft eines Knotens die Menge aller 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.

DefinitionBearbeiten

Für ungerichtete GraphenBearbeiten

Sei   ein ungerichteter Graph (welcher auch Schlingen enthalten kann). Dann heißen zwei Knoten   benachbart, verbunden oder adjazent in  , wenn sie durch eine ungerichtete Kante verbunden sind, das heißt, wenn   gilt. Sind zwei Knoten benachbart, so werden sie auch Nachbarn genannt.

  bezeichnet die Menge aller Nachbarn eines Knotens   in  . Ferner bezeichnet man mit   die Menge aller Nachbarn der in   enthaltenen Knoten. Diese Mengen werden auch die Nachbarschaft von   bzw.   genannt.

Ein Knoten ist genau dann sein eigener Nachbar, wenn er eine Schlinge besitzt. Die Nachbarschaft einer Menge von Knoten   kann Knoten aus der Menge   selbst enthalten. Die Vereinigung der Nachbarschaft mit den Knoten aus   heißt abgeschlossene Nachbarschaft.

Ein Knoten   und eine Kante   heißen inzident, wenn   den Knoten   mit einem anderen Knoten verbindet ( ). 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   bei der Notation oftmals weg.

Für gerichtete GraphenBearbeiten

Ein Knoten   heißt Vorgänger von   in einem gerichteten Graphen  , wenn   gerichtete Kante von   ist. Mit   bezeichnet man die Menge aller Vorgänger eines Knotens   in   . Ferner bezeichnet man mit   die Menge aller Vorgänger der Knoten von   in  .   bzw.   nennt man auch Vorgängermenge oder Eingangsmenge von   bzw.  .

Analog heißt   Nachfolger von   in  , wenn   gerichtete Kante von   ist. Mit   bezeichnet man die Menge aller Nachfolger eines Knotens   in  . Ferner bezeichnet man mit   die Menge aller Nachfolger der Knoten von   in  .   beziehungsweise   nennt man auch Nachfolgermenge oder Ausgangsmenge von   bzw.  .[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.

EinzelnachweiseBearbeiten

  1. H.W.Lang, FH Flensburg

LiteraturBearbeiten