Nachbarschaft (Graphentheorie) - de.LinkFang.org

Nachbarschaft (Graphentheorie)

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.

Inhaltsverzeichnis

Definition


Für ungerichtete Graphen

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

\({\displaystyle N_{G}(v)}\) bezeichnet die Menge aller Nachbarn eines Knotens \({\displaystyle v}\) in \({\displaystyle G}\). Ferner bezeichnet man mit \({\displaystyle N_{G}(X)}\) die Menge aller Nachbarn der in \({\displaystyle X\subseteq V}\) enthaltenen Knoten. Diese Mengen werden auch die Nachbarschaft von \({\displaystyle v}\) bzw. \({\displaystyle X}\) genannt.

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

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

Für gerichtete Graphen

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

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


  1. H.W.Lang, FH Flensburg

Literatur





Kategorien: Grundbegriff (Graphentheorie)

Werbung:


Quelle: Wikipedia - https://de.wikipedia.org/wiki/Nachbarschaft (Graphentheorie) (Autoren [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Veränderungen: Alle Bilder und die meisten Designelemente, die mit ihnen in Verbindung stehen, wurden entfernt. Icons wurden teilweise durch FontAwesome-Icons ersetzt. Einige Vorlagen wurden entfernt (wie „Lesenswerter Artikel“, „Exzellenter Artikel“) oder umgeschrieben. CSS-Klassen wurden zum Großteil entfernt oder vereinheitlicht.
Wikipedia spezifische Links, die nicht zu Artikeln oder Kategorien führen (wie „Redlink“, „Bearbeiten-Links“, „Portal-Links“) wurden entfernt. Alle externen Links haben ein zusätzliches FontAwesome Icon erhalten. Neben weiteren kleinen Designanpassungen wurden Media-Container, Karten, Navigationsboxen, gesprochene Versionen & Geo-Mikroformate entfernt.


Stand der Informationen: 03.03.2020 01:22:32 CET - Wichtiger Hinweis Da die gegebenen Inhalte zum angegebenen Zeitpunkt maschinell von Wikipedia übernommen wurden, war und ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.org nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein oder Fehler in der Darstellung vorliegen, bitten wir Sie darum uns per zu kontaktieren: E-Mail.
Beachten Sie auch : Impressum & Datenschutzerklärung.