Studium, Ausbildung und Beruf

web uni-protokolle.de
 powered by
NachrichtenLexikonProtokolleBücherForenSamstag, 30. August 2014 

Nachbarschaft und Grad in Graphen


Dieser Artikel von Wikipedia ist u.U. veraltet. Die neue Version gibt es hier.

Einleitung

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

Definitionen

Zwei Knoten heißen in einem ungerichteten Graphen (bzw. Hypergraphen ) G benachbart verbunden oder adjazent wenn sie Element einer ungerichteten Kante (bzw. Hyperkante ) von G sind. Ein Knoten v und eine ungerichtete Kante e (bzw. Hyperkante) heißen inzident falls v Element von e ist. Zwei ungerichtete Kanten heißen benachbart wenn sie nicht disjunkt sind d.h. wenn sie einen gemeinsamen besitzen.

Ein Knoten x heißt Nachbar von einem Knoten y in einem ungerichteten Graphen (bzw. Hypergraphen) G wenn x und y zu einer Kante von G gehören. Mit N G ( v ) bezeichnet man die Menge aller Nachbarn eines Knotens v in G . Ferner bezeichnet man mit N G ( X ) die Menge aller Nachbarn der Knoten X in G . N G ( v ) bzw. N G ( X ) nennt man auch Nachbarschaft von v bzw. X .

Mit d G ( v ) bezeichnet man den Grad (bzw. die Valenz ) des Knotens v in einem ungerichteten Graphen G . Dabei ist d G ( v ) in

Den kleinsten Grad eines Knotens in G bezeichnet man dann als Minimalgrad von G den größten Grad eines Knotens in G bezeichnet man als Maximalgrad von G . Das arithmetische Mittel aller Eckengrade von G wird als Durchschnittsgrad d G ( G ) bezeichnet.

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 Knotens v in G . Ferner bezeichnet man mit N G - ( X ) die Menge aller Vorgänger der Knoten X in G . N G - ( v ) bzw. N G - ( X ) nennt man auch Vorgängermenge oder Eingangsmenge von v bzw. X .

Analog heißt x Nachfolger von y in G wenn ( y x ) gerichtete Kante von G ist. Mit N G + ( v ) bezeichnet man die Menge aller Nachfolger Knotens v in G . Ferner bezeichnet man mit N G + ( X ) die Menge aller Nachfolger der Knoten X in G . N G + ( v ) bzw. N G + ( X ) nennt man auch Nachfolgermenge oder Ausgangsmenge von v bzw. X .

Mit d G - ( v ) bezeichnet man den Eingangsgrad des Knotens v in einem gerichteten Graphen G und mit d G + ( v ) dessen Ausgangsgrad . Dabei ist d G - ( v ) in

  • Graphen ohne Mehrfachkanten die Anzahl der von v
  • Graphen mit Mehrfachkanten die Summe der aller Kanten in G der Form ( v x ).
und d G + ( v ) in
  • Graphen ohne Mehrfachkanten die Anzahl der von v
  • Graphen mit Mehrfachkanten die Summe der aller Kanten in G der Form ( x v ).

In ungerichteten Graphen bzw. Hypergraphen nennt einen Knoten isoliert wenn er keine Nachbarn besitzt. In Graphen nennt man einen Knoten isoliert wenn er keine Vorgänger und keine besitzt.

Falls klar ist um welchen Graphen sich handelt lässt man den Index G bei N N - N + d d - und d + auch oft weg.

Ein ungerichteter Graph (bzw. Hypergraph) G heißt regulär falls alle seine Knoten den selben besitzen. Besitzen alle seine Knoten Grad k so bezeichnet man G als k-regulär . Einen 3-regulären Graphen bezeichnet man auch kubisch .

Ein Hypergraph G heißt uniform wenn alle Kanten von G die gleiche Anzahl Knoten enthalten. Enthalten Kanten von G genau k Knoten so nennt man G k-uniform .

Ein gerichteter Graph G heißt regulär falls alle seine Knoten den selben und Ausgangsgrad besitzen. Besitzen alle seine Knoten und Ausgangsgrad k so bezeichnet man G als k-regulär .



Bücher zum Thema Nachbarschaft und Grad in Graphen

Dieser Artikel von Wikipedia unterliegt der GNU FDL.

ImpressumLesezeichen setzenSeite versendenSeite drucken

HTML-Code zum Verweis auf diese Seite:
<a href="http://www.uni-protokolle.de/Lexikon/Grad_(Graphentheorie).html">Nachbarschaft und Grad in Graphen </a>