Nachbarschaft (Graphentheorie)

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Nachbarschaft ist ein grundlegender Begriff der Graphentheorie, eines Teilgebietes der Mathematik. Er beschreibt Eigenschaften eines Knotens, die sich durch mit ihm verbundene Kanten beschreiben lassen.

Definition[Bearbeiten]

Für ungerichtete Graphen[Bearbeiten]

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

 N_G(v)bezeichnet die Menge aller Nachbarn eines Knotens  v in  G . Ferner bezeichnet man mit  N_G(X) die Menge aller Nachbarn der in  X enthaltenen Knoten.Diese Mengen werden auch die Nachbarschaft von  v bzw.  X genannt.

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

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

Für gerichtete Graphen[Bearbeiten]

Ein Knoten  x heißt Vorgänger von  y in einem gerichteten Graphen  G, wenn  (x,y) gerichtete Kante von  G ist. Mit N_G^-(v)bezeichnet man die Menge aller Vorgänger eines Knotens  v in G . Ferner bezeichnet man mit N_G^-(X) die Menge aller Vorgänger der Knoten von X in G. N_G^-(v) bzw. N_G^-(X) nennt man auch Vorgängermenge oder Eingangsmenge von  v bzw.  X .

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

Einzelnachweise[Bearbeiten]

  1. H.W.Lang, FH Flensburg

Literatur[Bearbeiten]