Nachbarschaft (Graphentheorie)

Menge aller Knoten des Graphen, die mit ihm durch eine Kante verbunden sind
(Weitergeleitet von Nachbar (Graphentheorie))

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

Definition

Bearbeiten

Für ungerichtete Graphen

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

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 Knoten 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 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   bei der Notation oftmals weg.

Für gerichtete Graphen

Bearbeiten

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.

Literatur

Bearbeiten

Einzelnachweise

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