Ausgangsmenge
Dieser Artikel oder Abschnitt bedarf einer Überarbeitung. Näheres ist auf der Diskussionsseite angegeben. Hilf mit, ihn zu verbessern, und entferne anschließend diese Markierung.

Nachbarschaft und Grad sind grundlegende Begriffe der Graphentheorie, einem Teilgebiet der Mathematik. Sie beschreiben Eigenschaften von Knoten.

Inhaltsverzeichnis

Definitionen

Nachbarschaft

Ungerichtete Graphen

Zwei Knoten u und v heißen in einem ungerichteten Graphen G benachbart, verbunden oder adjazent, wenn sie durch eine ungerichtete Kante verbunden sind.
Ein Knoten v und eine ungerichtete Kante e heißen inzident, wenn e den Knoten v mit einem anderen Knoten verbindet (v ist Element von e). Zwei ungerichtete Kanten heißen benachbart, wenn sie nicht disjunkt sind, d.h. wenn sie einen gemeinsamen Knoten besitzen.

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

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

Diese Begriffe gelten analog für Hypergraphen und -kanten.

Gerichtete Graphen

Ein Knoten x heißt Vorgänger von y in einem gerichteten Graphen G, wenn (x, y) gerichtete Kante von G ist. Mit NG-(v) bezeichnet man die Menge aller Vorgänger eines Knotens v in G. Ferner bezeichnet man mit NG-(X) die Menge aller Vorgänger der Knoten von X in G. NG-(v) bzw. NG-(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 NG+(v) bezeichnet man die Menge aller Nachfolger eines Knotens v in G. Ferner bezeichnet man mit NG+(X) die Menge aller Nachfolger der Knoten von X in G. NG+(v) bzw. NG+(X) nennt man auch Nachfolgermenge oder Ausgangsmenge von v bzw. X.

Grad

Der Grad (oder Valenz) dG(v) in einem Graphen ist der Anzahl Kanten, die den Knoten v mit einem anderen Knoten verbinden. Oft wird auch die Notation degG(v) (engl. degree) verwendet

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

Ungerichtete Graphen

Ein ungerichteter Graph. Die Knoten sind mit ihrem Grad beschriftet.

In einem ungerichteten Graph ist dG(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 dG(G) bezeichnet.


Gerichtete Graphen

Ein gerichteter Graph mit beschrifteten Knoten: (Eingangsgrad, Ausgangsgrad)

In gerichteten Graphen wird unterschieden, ob eine Kante an einem Knoten beginnt oder endet. Mit dG-(v) bezeichnet man den Eingangsgrad des Knotens v in einem gerichteten Graphen G und mit dG+(v) dessen Ausgangsgrad.

Dabei ist dG-(v) in

  • Graphen ohne Mehrfachkanten die Anzahl der Vorgänger von v,
  • Graphen mit Mehrfachkanten die Summe der Vielfachheiten aller Kanten in G der Form (v, x).

und dG+(v) in

  • Graphen ohne Mehrfachkanten die Anzahl der Nachfolger von v,
  • Graphen mit Mehrfachkanten die Summe der Vielfachheiten aller Kanten in G der Form (x, v).

Einen Knoten ohne Eingangskanten (dG-(v) = 0) nennt man Quelle, einen Knoten ohne Ausgangskanten (dG+(v) = 0) nennt man Senke.

Spezialfälle und -begriffe
  • Man nennt einen Knoten isoliert, wenn er:
    • in einem ungerichteten Graphen: keine Nachbarn besitzt dG = 0.
    • in einem gerichteten Graphen: keine Vorgänger und keine Nachfolger besitzt. d_G^+ = d_G^- =0.
  • Ein ungerichteter Graph (bzw. Hypergraph) G heißt regulär, falls alle seine Knoten denselben Grad besitzen. Besitzen alle seine Knoten Grad k, so bezeichnet man G als k-regulär. Einen 3-regulären Graphen bezeichnet man auch als kubisch.
  • Ein gerichteter Graph G heißt regulär, falls alle seine Knoten denselben Eingangs- und Ausgangsgrad besitzen. Besitzen alle seine Knoten Eingangs- und Ausgangsgrad k, so bezeichnet man G als k-regulär.
  • Ein Hypergraph G heißt uniform, wenn alle Kanten von G die gleiche Anzahl Knoten enthalten. Enthalten alle Kanten von G genau k Knoten, so nennt man G k-uniform.

Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Tibetischer Abakus mit losen Steinen — Tibetischer Finanzbeamter im Museum der Burg von Gyantse mit einem Rechenbrett Ein Tibetischer Abakus mit losen Steinen (tib.: rde u rtsis) ist ein Rechenhilfsmittel zur Durchführung von Rechenaufgaben und insbesondere von Umrechnungen von… …   Deutsch Wikipedia

  • Erzeugungssystem — Unter einem Erzeugungssystem (nicht: Erzeugendensystem) versteht man in der Mathematik ein formales System, das aus einer Ausgangsmenge und einer oder mehreren Erzeugungsregeln besteht. Die Elemente der Ausgangsmenge bezeichnet man auch als… …   Deutsch Wikipedia

  • Abzählende Kombinatorik — Zahl der Permutationen und Derangements (totalen Versetzungen) von n Elementen. P(n) n Permutationen; D(n) totale Derangements (bei der alle n Elemente ihre Plätze wechseln) …   Deutsch Wikipedia

  • Ajtai-Fagin-Spiele — Ehrenfeucht Fraïssé Spiele (EF Spiele) sind eine Beweistechnik der Modelltheorie. Durch EF Spiele lässt sich die Äquivalenz zweier Strukturen zeigen bzw. widerlegen. Strukturen dienen in der beschreibenden Komplexitätstheorie meist als… …   Deutsch Wikipedia

  • EF-Spiel — Ehrenfeucht Fraïssé Spiele (EF Spiele) sind eine Beweistechnik der Modelltheorie. Durch EF Spiele lässt sich die Äquivalenz zweier Strukturen zeigen bzw. widerlegen. Strukturen dienen in der beschreibenden Komplexitätstheorie meist als… …   Deutsch Wikipedia

  • EF-Spiele — Ehrenfeucht Fraïssé Spiele (EF Spiele) sind eine Beweistechnik der Modelltheorie. Durch EF Spiele lässt sich die Äquivalenz zweier Strukturen zeigen bzw. widerlegen. Strukturen dienen in der beschreibenden Komplexitätstheorie meist als… …   Deutsch Wikipedia

  • Ehrenfeucht-Fraisse Spiel — Ehrenfeucht Fraïssé Spiele (EF Spiele) sind eine Beweistechnik der Modelltheorie. Durch EF Spiele lässt sich die Äquivalenz zweier Strukturen zeigen bzw. widerlegen. Strukturen dienen in der beschreibenden Komplexitätstheorie meist als… …   Deutsch Wikipedia

  • Ehrenfeucht-Fraïssé-Spiel — Ehrenfeucht Fraïssé Spiele (EF Spiele) sind eine Beweistechnik der Modelltheorie. Durch EF Spiele lässt sich die Äquivalenz zweier Strukturen zeigen bzw. widerlegen. Strukturen dienen in der beschreibenden Komplexitätstheorie meist als… …   Deutsch Wikipedia

  • Ehrenfeucht-Fraïssé-Spiele — (EF Spiele) sind eine Beweistechnik der Modelltheorie. Durch EF Spiele lässt sich die Äquivalenz zweier Strukturen zeigen bzw. widerlegen. Strukturen dienen in der beschreibenden Komplexitätstheorie meist als Formalismus zur Beschreibung von… …   Deutsch Wikipedia

  • QPCR — Die Real Time quantitative PCR (kurz RTq PCR oder qRT PCR, auch Real Time Detection PCR, kurz RTD PCR) ist eine Vervielfältigungsmethode für Nukleinsäuren, die auf dem Prinzip der herkömmlichen Polymerase Kettenreaktion (PCR) beruht, und… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”