Nachbarschaft Graphentheorie In der Graphentheorie versteht man unter der Nachbarschaft eines Knotens die Menge aller Kn

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.

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 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 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. .

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

Reinhard Diestel: Graphentheorie. Springer, Berlin 2010, ISBN 978-3-642-14911-5 (354 S.).

Einzelnachweise Bearbeiten

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

wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele

Veröffentlichungsdatum: November 29, 2023, 19:40 pm

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 1 Definition 1 1 Fur ungerichtete Graphen 1 2 Fur gerichtete Graphen 2 Literatur 3 EinzelnachweiseDefinition BearbeitenFur ungerichtete Graphen Bearbeiten nbsp Ungerichteter Graph die Nachbarschaft von Knoten 1 ist 1 2 5 die von 6 ist 4 Sei G V E displaystyle G V E nbsp ein ungerichteter Graph welcher auch Schlingen enthalten kann Dann heissen zwei Knoten u v V displaystyle u v in V nbsp benachbart verbunden oder adjazent in G displaystyle G nbsp wenn sie durch eine ungerichtete Kante verbunden sind das heisst wenn u v E displaystyle u v in E nbsp gilt Sind zwei Knoten benachbart so werden sie auch Nachbarn genannt N G v displaystyle N G v nbsp bezeichnet die Menge aller Nachbarn eines Knotens v displaystyle v nbsp in G displaystyle G nbsp Ferner bezeichnet man mit N G X displaystyle N G X nbsp die Menge aller Nachbarn der in X V displaystyle X subseteq V nbsp enthaltenen Knoten Diese Mengen werden auch die Nachbarschaft von v displaystyle v nbsp bzw X displaystyle X nbsp genannt Ein Knoten ist genau dann sein eigener Nachbar wenn er eine Schlinge besitzt Die Nachbarschaft N G X displaystyle N G X nbsp einer Menge X displaystyle X nbsp von Knoten kann Knoten aus der Menge X displaystyle X nbsp selbst enthalten Die Vereinigung der Nachbarschaft mit den Knoten aus X displaystyle X nbsp heisst abgeschlossene Nachbarschaft Ein Knoten v displaystyle v nbsp und eine Kante e displaystyle e nbsp heissen inzident wenn e displaystyle e nbsp den Knoten v displaystyle v nbsp mit einem anderen Knoten verbindet v e displaystyle v in e nbsp Zwei ungerichtete Kanten heissen benachbart wenn sie nicht disjunkt sind d h wenn sie einen gemeinsamen Knoten besitzen Diese Begriffe gelten analog fur Hypergraphen und kanten Falls klar ist um welchen Graphen es sich handelt lasst man den Index G displaystyle G nbsp bei der Notation oftmals weg Fur gerichtete Graphen Bearbeiten Ein Knoten x displaystyle x nbsp heisst Vorganger von y displaystyle y nbsp in einem gerichteten Graphen G displaystyle G nbsp wenn x y displaystyle x y nbsp gerichtete Kante von G displaystyle G nbsp ist Mit N G z displaystyle N G z nbsp bezeichnet man die Menge aller Vorganger eines Knotens z displaystyle z nbsp in G displaystyle G nbsp Ferner bezeichnet man mit N G Z displaystyle N G Z nbsp die Menge aller Vorganger der Knoten von Z displaystyle Z nbsp in G displaystyle G nbsp N G z displaystyle N G z nbsp bzw N G Z displaystyle N G Z nbsp nennt man auch Vorgangermenge oder Eingangsmenge von z displaystyle z nbsp bzw Z displaystyle Z nbsp Analog heisst y displaystyle y nbsp Nachfolger von x displaystyle x nbsp in G displaystyle G nbsp wenn x y displaystyle x y nbsp gerichtete Kante von G displaystyle G nbsp ist Mit N G z displaystyle N G z nbsp bezeichnet man die Menge aller Nachfolger eines Knotens z displaystyle z nbsp in G displaystyle G nbsp Ferner bezeichnet man mit N G Z displaystyle N G Z nbsp die Menge aller Nachfolger der Knoten von Z displaystyle Z nbsp in G displaystyle G nbsp N G z displaystyle N G z nbsp beziehungsweise N G Z displaystyle N G Z nbsp nennt man auch Nachfolgermenge oder Ausgangsmenge von z displaystyle z nbsp bzw Z displaystyle Z nbsp 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 BearbeitenReinhard Diestel Graphentheorie Springer Berlin 2010 ISBN 978 3 642 14911 5 354 S Einzelnachweise Bearbeiten H W Lang Mathematische Grundlagen Graph auf der Seite der Hochschule Flensburg 1998 abgerufen am 8 April 2023 Abgerufen von https de wikipedia org w index php title Nachbarschaft Graphentheorie amp oldid 232610434