Nachbarschaft und Grad in Graphen

Wenn man über Graphen und ihrem Aufbau oder deren innere Struktur spricht, kommt man nicht umhin lokale Eigenschaften mit eindeutigen Namen zu belegen. Es gibt praktisch keine graphentheoretische Abhandlung, die ohne die Begriffe Nachbarschaft und Grad auskommt. Andererseits sind diese Begriffe so trivial, dass es kaum interessante Ergebnisse gibt, die nur mit diesen Begriffen operieren. Dieser Artikel beschränkt sich daher darauf, diese Begriffe und leicht daraus ableitbare Graphenklassen zu erklären und diese an Beispielen zu illustrieren. Der Laie sollte aber zumindest die Begriffe Grad und Nachbarschaft unbedingt verinnerlichen, bevor er sich an tiefergehende graphentheoretische Artikel wagt.

Definitionen

Zwei Knoten heißen in einem ungerichteten Graphen (bzw. Hypergraphen) GG benachbart, verbunden oder adjazent, wenn sie Element einer ungerichteten Kante (bzw. Hyperkante) von GG sind. Ein Knoten vv und eine ungerichtete Kante ee (bzw. Hyperkante) heißen inzident, falls vv Element von ee ist. Zwei ungerichtete Kanten heißen benachbart, wenn sie nicht disjunkt sind, d.h. wenn sie einen gemeinsamen Knoten besitzen.
Ein Knoten xx heißt Nachbar von einem Knoten yy in einem ungerichteten Graphen (bzw. Hypergraphen) GG, wenn xx und yy zu einer Kante von GG gehören. Mit NG(v)N_{G}(v) bezeichnet man die Menge aller Nachbarn eines Knotens vv in GG. Ferner bezeichnet man mit NG(X)N_{G}(X) die Menge aller Nachbarn der Knoten von XX in GG. NG(v)N_{G}(v) bzw. NG(X)N_{G}(X) nennt man auch Nachbarschaft von vv bzw. XX.
Mit dG(v)d_{G}(v) bezeichnet man den Grad (bzw. die Valenz) des Knotens vv in einem ungerichteten Graphen GG. Dabei ist dG(v)d_{G}(v) in
  • Graphen ohne Mehrfachkanten und Hypergraphen die Anzahl der Nachbarn von vv,
  • Graphen mit Mehrfachkanten die Summe der Vielfachheiten aller mit vv inzidenten Kanten.
Den kleinsten Grad eines Knotens in GG bezeichnet man dann als Minimalgrad von GG, den größten Grad eines Knotens in GG bezeichnet man als Maximalgrad von GG. Das arithmetische Mittel aller Eckengrade von GG wird als Durchschnittsgrad dG(G)d_{G}(G) bezeichnet.
Ein Knoten xx heißt Vorgänger von yy in einem gerichteten Graphen GG, wenn (x, y)(x,\, y) gerichtete Kante von GG ist. Mit NG−(v)N_{G}^{-}(v) bezeichnet man die Menge aller Vorgänger eines Knotens vv in GG. Ferner bezeichnet man mit NG−(X)N_{G}^{-}(X) die Menge aller Vorgänger der Knoten von XX in GG. NG−(v)N_{G}^{-}(v) bzw. NG−(X)N_{G}^{-}(X) nennt man auch Vorgängermenge oder Eingangsmenge von vv bzw. XX.
Analog heißt xx Nachfolger von yy in GG, wenn (y, x)(y,\, x) gerichtete Kante von GG ist. Mit NG+(v)N_{G}^{+}(v) bezeichnet man die Menge aller Nachfolger eines Knotens vv in GG. Ferner bezeichnet man mit NG+(X)N_{G}^{+}(X) die Menge aller Nachfolger der Knoten von XX in GG. NG+(v)N_{G}^{+}(v) bzw. NG+(X)N_{G}^{+}(X) nennt man auch Nachfolgermenge oder Ausgangsmenge von vv bzw. XX.
Mit dG−(v)d_{G}^{-}(v) bezeichnet man den Eingangsgrad des Knotens vv in einem gerichteten Graphen GG und mit dG+(v)d_{G}^{+}(v) dessen Ausgangsgrad. Dabei ist dG−(v)d_{G}^{-}(v) in
  • Graphen ohne Mehrfachkanten die Anzahl der Vorgänger von vv,
  • Graphen mit Mehrfachkanten die Summe der Vielfachheiten aller Kanten in GG der Form (v, x)(v,\, x).
und dG+(v)d_{G}^{+}(v) in
  • Graphen ohne Mehrfachkanten die Anzahl der Nachfolger von vv,
  • Graphen mit Mehrfachkanten die Summe der Vielfachheiten aller Kanten in GG der Form (x, v)(x,\, v).
In ungerichteten Graphen bzw. Hypergraphen nennt man einen Knoten isoliert, wenn er keine Nachbarn besitzt. In gerichteten Graphen nennt man einen Knoten isoliert, wenn er keine Vorgänger und keine Nachfolger besitzt.
Falls klar ist, um welchen Graphen es sich handelt, lässt man den Index GG bei N, N−, N+, d, d−N,\, N^{-},\, N^{+},\, d,\, d^{-} und d+d^{+} auch oft weg.
Ein ungerichteter Graph (bzw. Hypergraph) GG heißt regulär, falls alle seine Knoten den selben Grad besitzen. Besitzen alle seine Knoten Grad kk, so bezeichnet man GG als k-regulär. Einen 3-regulären Graphen bezeichnet man auch als kubisch.
Ein Hypergraph GG heißt uniform, wenn alle Kanten von GG die gleiche Anzahl Knoten enthalten. Enthalten alle Kanten von GG genau kk Knoten, so nennt man GG k-uniform.
Ein gerichteter Graph GG heißt regulär, falls alle seine Knoten den selben Eingangs- und Ausgangsgrad besitzen. Besitzen alle seine Knoten Eingangs- und Ausgangsgrad kk, so bezeichnet man GG als k-regulär.
 
 

Das entscheidende Kriterium ist Schönheit; für häßliche Mathematik ist auf dieser Welt kein beständiger Platz.

Godfrey Harold Hardy

Copyright- und Lizenzinformationen: Diese Seite basiert dem Artikel Nachbarschaft und Grad in Graphen aus der frеiеn Enzyklοpädιe Wιkιpеdιa und stеht unter der Dοppellizеnz GNU-Lιzenz für freie Dokumentation und Crеative Commons CC-BY-SA 3.0 Unportеd (Kurzfassung). In der Wιkιpеdιa ist eine Listе dеr Autorеn des Originalartikels verfügbar. Da der Artikel geändert wurde, reicht die Angabe dieser Liste für eine lizenzkonforme Weiternutzung nicht aus!
Anbieterkеnnzeichnung: Mathеpеdιa von Тhοmas Stеιnfеld  • Dοrfplatz 25  •  17237 Blankеnsее  • Tel.: 01734332309 (Vodafone/D2)  •  Email: cο@maτhepedιa.dе
Datenschutzerklärung

 

Diskrete Mathematik