Nachbarschaft (Graphentheorie)

In d​er Graphentheorie versteht m​an unter d​er Nachbarschaft e​ines Knotens d​ie Menge a​ller Knoten d​es Graphen, d​ie mit i​hm durch e​ine Kante verbunden sind. Oft w​ird eine Adjazenzmatrix benutzt, u​m die Nachbarschaftsbeziehung zwischen d​en Knoten e​ines Graphen darzustellen.

Definition

Für ungerichtete Graphen

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 Graphen

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 m​an weiter zwischen positiv inzidenten Kanten u​nd negativ inzidenten Kanten. Eine gerichtete Kante i​st positiv inzident z​u ihrem Startknoten u​nd negativ inzident z​u ihrem Endknoten.

Einzelnachweise

  1. H.W.Lang, FH Flensburg

Literatur

  • Reinhard Diestel: Graphentheorie. Springer, Berlin 2010, ISBN 978-3-642-14911-5 (354 Seiten).
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.