Nachbar (Graphentheorie) - LinkFang.de





Nachbarschaft (Graphentheorie)

(Weitergeleitet von: Nachbarschaft_(Graphentheorie))

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

Für ungerichtete Graphen

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

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

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

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

Für gerichtete Graphen

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

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

  1. H.W.Lang, FH Flensburg

Literatur


Kategorien: Keine Kategorien vorhanden!

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Nachbarschaft (Graphentheorie) (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.