Mathematik-Glossar: Graphentheorie


Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen.

Inhaltsverzeichnis: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z


ABearbeiten

AbstandBearbeiten

Siehe: Distanz.

Achromatische ZahlBearbeiten

Die achromatische Zahl   eines Graphen   ist die größte Zahl  , für die   eine gültige und vollständige Knotenfärbung mit   Farben hat.
Siehe auch: chromatische Zahl, pseudo-achromatische Zahl.

AdjazenzBearbeiten

Adjazenz bezeichnet eine Beziehung zwischen Knoten oder Kanten in einem Graph. Zwei Knoten heißen adjazent oder benachbart, wenn sie in diesem durch eine Kante verbunden sind. Zwei Kanten heißen adjazent oder benachbart, wenn sie sich an einem Knoten berühren, das heißt diesen gemeinsam besitzen.
Siehe auch: Inzidenz, Adjazenzmatrix, w:Nachbarschaft und Grad in Graphen.

AdjazenzlisteBearbeiten

Eine Adjazenzliste ist eine Möglichkeit, Graphen im Computer darzustellen, wobei zu jedem Knoten eine Liste seiner Nachbarn geführt wird. Hierzu wird z. B. eine verkettete Liste oder ein Array verwendet.
Siehe auch: Adjazenzmatrix.

AdjazenzmatrixBearbeiten

Eine Adjazenzmatrix ist eine binäre Matrix, die alle Knoten beinhaltet und jeweils die Erreichbarkeit zum direkten Nachfolger markiert. Addiert mit der w:Einheitsmatrix ergibt sich die Erreichbarkeitsmatrix im ersten Schritt.

AdjazenzraumBearbeiten

Der Adjazenzraum eines Graphen ist der w:Vektorraum, der von den Spalten der Adjazenzmatrix aufgespannt wird.
Die Adjazenzräume von isomorphen Graphen sind isomorphe Räume

Alternierender PfadBearbeiten

Siehe: Verbesserungspfad.

ArtikulationBearbeiten

Ein Separator, der aus einem Knoten besteht, wird Artikulation oder Schnittknoten genannt.
Ein Knoten   ist genau dann eine Artikulation, wenn Knoten   existieren für die jeder Weg von   nach   über   führt.

Aufspannender TeilgraphBearbeiten

Ein Teilgraph, der alle Knoten des Ausgangsgraphen enthält.

Augmentierender PfadBearbeiten

Siehe: Verbesserungspfad.

AusgangsgradBearbeiten

Als Ausgangsgrad eines Knotens wird in einem gerichteten Graph die Anzahl seiner direkten Nachfolger bezeichnet. Man bezeichnet dies auch als den positiven Grad eines Knotens.
Siehe auch: Grad, Eingangsgrad, w:Nachbarschaft und Grad in Graphen.

AusgangsmengeBearbeiten

Als Ausgangsmenge eines Knotens wird in einem gerichteten Graph die Menge seiner direkten Nachfolger bezeichnet.

AutomorphismusBearbeiten

Ein Automorphismus eines Graphen ist eine w:Permutation der Knoten, bei der zwei Knoten genau dann durch eine Kanten verbunden sind, wenn es die Bilder dieser beiden Knoten sind.

Azyklischer GraphBearbeiten

Ein azyklischer Graph ist ein gerichteter Graph, der keinen Zyklus enthält.

BBearbeiten

(zum Seitenanfang)

BandbreiteBearbeiten

Die Bandbreite (engl. bandwidth, siehe auch w:Bandbreite) eines endlichen, schlichten, ungerichteten Graphen ist wie folgt definiert: Sei   eine eineindeutige Nummerierung der Knoten. Dann bezeichnet   die Bandbreite bezüglich   und   die Bandbreite des Graphen  .
Die Ermittlung der Bandweite ist eines der wenigen Probleme, das auch für Bäume NP-vollständig ist.

BaumBearbeiten

Ein Baum ist ein zusammenhängender Graph, der keine Zyklen enthält. Genauer:   ist maximal kreisfrei und minimal zusammenhängend. D. h. keine Kante kann zur Kantenmenge hinzugefügt werden, ohne einen Kreis zu erzeugen, und keine kann entfernt werden, ohne die Zusammenhangs-Eigenschaft zu verletzen.
Häufig ist der Baum gerichtet, also eigentlich ein Wurzelbaum, was oft nur indirekt durch den Zusammenhang, z. B. durch die Verwendung von Begriffen wie die Wurzel oder Vater, Sohn, Kind, deutlich wird.
Hauptartikel: Baum.

BaumkanteBearbeiten

Siehe: Vorwärtskante.

BinärbaumBearbeiten

Ein Wurzelbaum, bei dem jeder Knoten höchstens 2 Söhne hat, heißt Binärbaum.
Die Knoten ohne Sohn heißen (wie auch beim nicht binären Baum) Blätter.
Beim Binärbaum heißt ein Knoten mit genau einem Sohn Halbblatt. Dann zählt ein Blatt als 2 Halbblätter.
Hauptartikel: w:Binärbaum.
Als eine w:Datenstruktur der w:Informatik ist der Binärbaum besonders interessant als (binärer) w:Suchbaum.
Hauptartikel: w:Binärer Suchbaum.

BipartitionBearbeiten

Eine Bipartition ist eine 2-Partition.

Bipartiter GraphBearbeiten

Ein bipartiter Graph ist ein einfacher Graph, der eine Bipartition besitzt.
Nach w:Dénes Kőnig ist ein Graph genau dann bipartit, wenn er keinen Kreis ungerader Länge besitzt.
Hauptartikel: w:Bipartiter Graph, w:vollständig bipartiter Graph.
Siehe auch: Satz von König, w:Wege, Pfade, Zyklen und Kreise in Graphen.

BlattBearbeiten

Ein Blatt ist ein Knoten in einem Baum welcher nur einen Nachbarn hat.
In einem Wurzelbaum muss ein Blatt zusätzlich verschieden zur Wurzel sein. Der eindeutige Nachbar ist dann der Vorgänger, und ein Blatt hat keinen Nachfolger.
Hat im Binärbaum ein Knoten genau einen Sohn, so spricht man auch von einem Halbblatt. Ein Blatt zählt dann als 2 Halbblätter.

BlockBearbeiten

Ein Block   eines Graphen   ist ein Teilgraph, der maximal in der Eigenschaft ist, dass er zweifach knotenzusammenhängend ist. Das heißt, dass wenn ein weiterer Knoten von   zu   hinzugenommen würde, dieser zu einem der anderen Knoten von   nur einen Weg hätte.

BlockgraphBearbeiten

Ein Blockgraph   zu einem Graphen G erfüllt die folgenden Eigenschaften:
  • Für jeden Schnittknoten in G gibt es genau einen Knoten in  .
  • Für jeden Block in G gibt es genau einen Knoten in  .
  • Kanten verlaufen zwischen Schnittknoten und Blockknoten genau dann, wenn der Block den Schnittknoten enthält.
  • Es gibt keine weiteren Knoten und Kanten in  .

BogenBearbeiten

Siehe: Gerichtete Kante.

BrückeBearbeiten

Sei   ein Graph. Eine Kante   heißt Brücke in  , falls zwei Knoten  ,   in   existieren, für die jeder Weg von   nach   über   führt. Äquivalent lässt sich eine Brücke als Kante charakterisieren, die auf keinem Kreis in   liegt.

CBearbeiten

(zum Seitenanfang)

Chordaler GraphBearbeiten

Siehe: Triangulierter Graph.

Chromatische ZahlBearbeiten

Die chromatische Zahl   (auch Knotenfärbungszahl oder kurz Färbungszahl, selten auch Farbzahl genannt) eines Graphen ist die kleinste Zahl  , für die der Graph eine zulässige Knotenfärbung mit   Farben besitzt. Das ist gleichzeitig auch die kleinste natürliche Zahl λ, für die das chromatische Polynom   ist.
Siehe auch: Partition, Färbung, achromatische Zahl, pseudo-achromatische Zahl.

Chromatischer IndexBearbeiten

Der chromatische Index   (auch Kantenfärbungszahl) eines Graphen ist die kleinste Zahl  , für die der Graph eine zulässige Kantenfärbung mit   Farben besitzt.
Der chromatische Index entspricht der Chromatischen Zahl des Kantengraphen  .
Nach Satz von Vizing (1964) gilt  . Graphen mit   nennt man Klasse 1 Graphen, Graphen mit   nennt man Klasse 2 Graphen. Zu entscheiden, ob ein Graph Klasse 1 oder Klasse 2 ist (Klassifikationsproblem), ist NP-vollständig.
Siehe auch: Färbung.

CliqueBearbeiten

Eine Clique ist in einem ungerichteten Graph eine Teilmenge der Knoten, innerhalb derer alle Knoten paarweise mit einer Kante verbunden sind.
Siehe auch: w:Knotenüberdeckungen, Cliquen und stabile Mengen.

Cliquen-GraphBearbeiten

Der Cliquen-Graph eines Graphen G ist der Graph, der sich ergibt, wenn alle Cliquen jeweils einem Knoten zugeordnet und zwei Knoten verbunden werden, wenn die zugehörigen Cliquen in G gemeinsame Knoten haben.

CliquenproblemBearbeiten

Das Cliquenproblem fragt, zu einem gegebenen ungerichteten Graph   und einer natürlichen Zahl  , ob die Cliquenzahl von   mindestens so groß wie   ist.
Siehe auch: w:Knotenüberdeckungen, Cliquen und stabile Mengen.

CliquenzahlBearbeiten

Die Cliquenzahl   eines ungerichteten Graphen   ist die größte Zahl  , für die   eine Clique der Größe   besitzt.
Siehe auch: Cliquenproblem.

DBearbeiten

(zum Seitenanfang)

DichteBearbeiten

Die Dichte   eines einfachen Graphen   ist das Verhältnis seiner w:Kantenzahl zur Kantenzahl eines vollständigen Graphen auf gleichvielen Knoten, das heißt:
 

DigraphBearbeiten

Siehe: gerichteter Graph.

DilationBearbeiten

Die Dilation oder Dilatation eines euklidischen Graphen ist ein Maß dafür, wie viel Umweg beim Durchlaufen des Graphen in Kauf genommen werden muss, im Vergleich zur direkten euklidischen Strecke.
Siehe auch: Dilation.

Direkter NachfolgerBearbeiten

In einem gerichteten Graphen heißt ein Knoten   direkter Nachfolger oder positiver Nachbar eines Knoten  , falls es eine Kante gibt, welche von   nach   geht.
Siehe auch: Kind und Sohn.

Direkter VorgängerBearbeiten

In einem gerichteten Graphen heißt ein Knoten   direkter Vorgänger oder negativer Nachbar eines Knotens   falls es eine Kante gibt, die von   nach   geht.
Siehe auch: Vater.

Disjunkte WegeBearbeiten

Zwei Wege   und   heißen disjunkt, falls alle Knoten aus   verschieden von denen aus  . Häufig lässt man zu, dass   und  , also dass es Wege vom gleichen Startknoten zum gleichen Zielknoten sind. Eine Menge von Wegen heißt disjunkt, wenn diese paarweise disjunkt sind.
Existieren für jedes Paar   von Knoten   disjunkte Wege von   nach  , so nennt man den Graphen p-fach knotenzusammenhängend.

DistanzBearbeiten

Die Distanz zweier Knoten   und   in einem Graphen (auch Abstand der Knoten genannt) ist die Länge eines kürzesten Pfades, der von   nach   führt. Falls ein solcher Pfad nicht existiert, so setzt man den Abstand auf unendlich ( ). Der Abstand eines Knotens zu sich selbst ist null (0).
Siehe auch: w:Distanzgraph.

DistanzgraphBearbeiten

Als Distanzgraph   eines Graphen   bezeichnet man den vollständigen kantengewichteten Graphen über  , der jeder Kante die Distanz der zugehörigen Knoten in   zuordnet.
Siehe auch: w:Distanzgraph.

DominationszahlBearbeiten

Die Dominationszahl   eines gerichteten Graphen   ist die Mächtigkeit einer kleinsten dominierenden Menge von  .

Dominierende MengeBearbeiten

Eine Menge   von Knoten in einem gerichteten Graphen   heißt dominierend oder äußerlich stabil (engl. dominating), wenn jeder Knoten aus   einen positiven Nachbarn in   hat.
Siehe auch: Kern.

DreieckBearbeiten

Ein Dreieck ist ein Graph mit drei Knoten, die alle zueinander adjazent (benachbart) sind.

Dreiecksfreier GraphBearbeiten

Als dreiecksfrei werden Graphen bezeichnet, die keinen Kreis der Länge 3 (ein Dreieck) als Teilgraph besitzen.

Dualer GraphBearbeiten

Sei   ein planarer Graph mit einer gegebenen planaren Einbettung. Der duale Graph   entsteht aus  , indem jeder Fläche von   ein Knoten von   zugeordnet wird. Zwei Knoten aus   werden durch   Kanten verbunden, wenn die entsprechenden Flächen aus   genau   gemeinsame Randkanten besitzen.
Bemerkung: Für zusammenhängende   gilt:  , das heißt: Der duale Graph des dualen Graphen ist der Graph selbst.

DurchmesserBearbeiten

Der Durchmesser   eines Graphen   ist das Maximum der Exzentrizitäten der Knoten von  
Für alle Graphen   gilt  , wobei   der Radius von   ist.
Siehe auch: Zentrum.

EBearbeiten

(zum Seitenanfang)

EckeBearbeiten

Siehe: Knoten.

EinbettungBearbeiten

Eine Darstellung eines Graphen in der Ebene wird als Einbettung bezeichnet. Ist die Darstellung überkreuzungsfrei, so spricht man von einer planaren Einbettung.

Einfacher GraphBearbeiten

Als einfacher Graph oder auch schlichter Graph wird ein Graph ohne besondere Strukturelemente wie Mehrfachkanten, orientierte Kante, Schleifen, Knoten- oder Kantengewichte bzw. Färbungen oder Markierungen bezeichnet.

Einfacher KreisBearbeiten

Ein einfacher Kreis in einem schlichten, ungerichteten Graphen   ist ein Kreis, der keinen Knoten mehrfach enthält (abgesehen von Anfangs- und Endknoten).

Einfacher PfadBearbeiten

Ein einfacher Pfad in einem schlichten, ungerichteten Graphen   ist ein Pfad, der keine Kante mehrfach enthält.

EingangsgradBearbeiten

Als Eingangsgrad eines Knotens wird in einem gerichteten Graph die Anzahl seiner direkten Vorgänger bezeichnet. Man bezeichnet dies auch als den negativen Grad eines Knotens.
Siehe auch: Grad, Ausgangsgrad, w:Nachbarschaft und Grad in Graphen.

EingangsmengeBearbeiten

Als Eingangsmenge eines Knotens wird in einem gerichteten Graph die Menge seiner direkten Vorgänger bezeichnet.

Endknoten einer KanteBearbeiten

Ist   eine gerichtete Kante, so bezeichnet man   als ihren Startknoten und   als ihren Endknoten.
Bei ungerichteten Kanten   kann man   und   sowohl als Startknoten als auch als Endknoten bezeichnen. Hier spricht man in der Regel aber einfach von den beiden „zu   inzidenten Knoten“.

ErreichbarkeitsmatrixBearbeiten

Die Erreichbarkeitsmatrix ist eine binäre Matrix und gibt im  -ten Schritt die gesamte Erreichbarkeit der Knoten untereinander an.
Der 1. Schritt entsteht durch die Addition der w:Einheitsmatrix mit der Adjazenzmatrix. Der nächste Schritt ist immer die Anfangsmatrix multipliziert mit der vorherigen Matrix oder zum Beispiel der 3. Schritt multipliziert mit dem 2. Schritt ergibt den 5. Schritt. Tritt keine Veränderung zum jeweiligen nächsten Schritt ein, bricht der Algorithmus ab.

Euklidisches Traveling-Salesman-ProblemBearbeiten

Das Euklidische Travelling Salesman Problem ist das Travelling Salesman Problem für einen kantenbewerteten Graphen, in dem die w:Dreiecksungleichung gilt.
Siehe auch: w:Problem des Handlungsreisenden.

EulerkreisBearbeiten

Der Begriff Eulerkreis wird synonym für Eulertour verwendet. Die Bezeichnung „Eulerkreis“ ist insofern falsch, als es sich im Allgemeinen nicht um einen Kreis, sondern um einen Zyklus handelt.

Eulerscher GraphBearbeiten

Ein eulerscher Graph ist ein Graph, in dem ein Zyklus existiert, der jede Kante genau einmal enthält.
  • w:Leonhard Euler zeigte 1736, dass in jedem Eulerschen Graphen alle Knoten geraden Grad haben, weshalb Eulersche Graphen nach ihm benannt sind. Er zeigte ebenfalls, dass in jedem semieulerschen Graphen entweder keine oder zwei Knoten ungeraden Grad haben. Auf diese Weise löste er das w:Königsberger Brückenproblem.
  • Carl Hierholzer zeigte 1873 die Umkehrung, dass in jedem zusammenhängenden Graphen, in dem jeder Knoten geraden Grad hat, eine Eulertour existiert und in jedem Graphen, in dem zwei Knoten ungeraden Grad haben, ein Eulerweg existiert.
Siehe auch: w:Eulerkreisproblem.

EulertourBearbeiten

Eine Eulertour ist ein Zyklus, der über alle Kanten eines Graphen läuft.

EulerwegBearbeiten

Ein Eulerweg ist ein Weg, der über alle Kanten eines Graphen läuft.

EulerzugBearbeiten

Ein geschlossener w:Kantenzug in einem Graphen heißt Eulerzug, wenn er jede Kante des Graphen genau einmal enthält. Ein Graph heißt eulersch, wenn er einen solchen Kantenzug besitzt.
Siehe auch: Eulerscher Graph.

ExzentrizitätBearbeiten

Die Exzentrizität   eines Knotens   ist die Distanz (die Länge eines kürzesten Weges) zu einem Knoten  , welcher maximalen Abstand von   hat.
Beachte: Hier wird das Maximum von minimalen Weglängen betrachtet
Siehe auch: Radius, Durchmesser, Zentrum.

FBearbeiten

(zum Seitenanfang)

FärbungBearbeiten

Siehe: Knotenfärbung, Kantenfärbung.

FärbungszahlBearbeiten

Siehe: Chromatische Zahl.

FaktorBearbeiten

Ist   ein Graph und   eine Abbildung seiner Knoten auf natürliche Zahlen, ist ein  -Faktor   ein Teilgraph von   mit derselben Knotenmenge V wie  , in dem jeder Knoten   von   genau   Nachbarn hat, also den Grad   besitzt.
Gilt für alle Knoten   die Bedingung  , besitzen also alle Knoten genau   Nachbarn, spricht man dementsprechend auch von einem  -Faktor.
Gilt dagegen für alle Knoten   die Bedingung  , besitzen also alle Knoten mindestens   und gleichzeitig höchstens   Nachbarn, spricht man entsprechend von einem  -Faktor.
Beispiele
Eine Paarung ist ein  -Faktor, also ein Teilgraph von  , in dem jeder Knoten   höchstens einen Nachbarn hat, eine perfekte Paarung dagegen ein 1-Faktor, also ein Teilgraph von  , in dem jeder Knoten   genau einen Nachbarn besitzt. Hamiltonsche Graphen schließlich besitzen 2-Faktoren, in denen jeder Knoten   genau zwei Nachbarn hat.
Der 1-Faktor-Satz von Tutte besagt, dass man aus   und   einen Graphen   konstruieren kann, welcher genau dann einen 1-Faktor besitzt, wenn   einen  -Faktor besitzt. Dies ist die Definition einer Reduktion im Sinne der theoretischen Informatik. Da umgekehrt 1-Faktoren Spezialfälle von  -Faktoren sind, ist das  -Faktorproblem äquivalent zum 1-Faktorproblem.

FaktorisierungBearbeiten

Zerlegung eines Graphen   in  -Faktoren, z. B. bei der 1-Faktorisierung in 1-Faktoren, d. h. Teilgraphen, deren Knoten nur jeweils genau einen Nachbarn haben.

Faktor-kritischBearbeiten

Ein Graph   mit   heißt faktor-kritisch, wenn durch Wegnahme eines beliebigen Knoten eine perfekte Paarung möglich wird.

FarbzahlBearbeiten

Siehe: Chromatische Zahl.

FlächeBearbeiten

Fläche eines planaren Graphen nennt man das Gebiet der Ebene (oder einer Fläche im  ), welches durch Kanten eines planaren Graphen, der in der Ebene (bzw. auf der Fläche) eingebettet ist, berandet wird.

FlussBearbeiten

Ein Fluss zu einem gerichteten Graphen und Kantenkapazitäten ist eine Funktion   von den gerichteten Kanten auf die nichtnegativen reellen Zahlen. Ein Fluss darf jeder Kante nur einen Wert zuweisen, der höchstens so groß ist wie die Kapazität der Kante.
Spricht man von einem s-t-Fluss, muss ferner für jeden Knoten   (außer für die Quelle   und die Senke  ) gelten, dass die Summe der Flüsse auf den hineinführenden Kanten gleich der Summe der Flüsse auf den hinausführenden Kanten ist.
Formal:  
Anschaulich: aus keinem Knoten (außer   und  ) kann mehr herausfließen als hineinfließt und alles, was in einen Knoten hineinfließt, fließt auch wieder heraus.

FundamentalkreisBearbeiten

Zu einem aufspannenden Baum   heißt   FundamentalKreis, falls er durch Hinzufügen einer Kante zum Baum erzeugt wird.

FundamentalschnittBearbeiten

Sei   zusammenhängend. Zu einem Spannenden Baum   heißt   Fundamentalschnitt, falls   als Knotenmenge durch Weglassen einer Kante im Baum als Zusammenhangskomponente entsteht.

GBearbeiten

(zum Seitenanfang)

Geordneter BaumBearbeiten

Ein geordneter Baum ist ein Wurzelbaum, in dem für die Söhne jedes Knotens eine w:Ordnungsrelation definiert ist. Anschaulich legt die Ordnung fest, in welcher Weise die Nachfolger eines Knotens in der grafischen Darstellung des Baumes angezeigt werden (z. B. von links nach rechts gemäß Ordnungskriterium). Formal wird durch die Ordnung festgelegt, in welcher Reihenfolge die Knoten bei unterschiedlichen Traversierungsverfahren (preorder, inorder, postorder) durchlaufen werden.

Gerichteter GraphBearbeiten

Ein Gerichteter Graph (auch Digraph genannt) ist ein Graph, der gerichtete Kanten enthält.
Siehe auch: w:Typen von Graphen in der Graphentheorie.

Gerichtete KanteBearbeiten

Eine gerichtete Kante, auch Bogen oder Pfeil genannt, verbindet zwei Knoten eines Graphen unter Beachtung einer Reihenfolge. Eine gerichtete Kante wird daher als w:geordnetes Paar zweier Knoten notiert.
Siehe auch: Ungerichtete Kante, w:Typen von Graphen in der Graphentheorie.

Gerichteter KreisBearbeiten

Siehe: Gerichteter Zyklus.

GerüstBearbeiten

Ein Gerüst ist ein Teilgraph eines Graphen  , der alle Knoten aus   enthält. Ist   zusammenhängend, so ist das Gerüst zugleich ein Spannbaum. Ist   nicht zusammenhängend, so bezeichnet man das entstehende Gerüst auch als Spannwald oder aufspannender Wald.

GewichtBearbeiten

Das Gewicht ist eine reelle Zahl, die einem Knoten oder einer Kante zugeordnet wird.
Siehe auch: Gewicht, w:Knotengewicht, w:Kantengewicht.

GradBearbeiten

Der Grad eines Knotens in einem ungerichteten Graphen (auch Valenz genannt) ist die Anzahl seiner Nachbarn.
Siehe auch: Eingangsgrad, Ausgangsgrad, w:Nachbarschaft und Grad in Graphen.

GradfolgeBearbeiten

Als Gradfolge eines Graphen   mit den Knoten   bezeichnet man die Folge natürlicher Zahlen  , welche jeweils den Grad der einzelnen Knoten angeben, d. h.   für alle  . Eine solche Folge natürlicher Zahlen heißt auch graphisch, wenn tatsächlich mindestens ein Graph existiert, der diese Gradfolge aufweist.

GraphBearbeiten

Ein Graph ist ein Tupel  .   ist eine nichtleere Menge von Knoten,   eine Menge von Kanten.
Jede Kante hat je einen Anfangs- und Endknoten. Werden Anfangs- und Endknoten nicht unterschieden, spricht man von einem ungerichteten Graphen, andernfalls von einem gerichteten Graphen. In einem Graphen ohne Mehrfachkanten ist jede Kante bereits durch das Paar aus Anfangs- und Endecke bestimmt.
Siehe auch: w:Typen von Graphen in der Graphentheorie, Hypergraph.

GraphischBearbeiten

Als graphisch bezeichnet man eine Folge natürlicher Zahlen, welche die Gradfolge eines Graphen ist.

Graph mit MehrfachkantenBearbeiten

Wird die Forderung aufgegeben, dass eine Kante durch ihre zwei Knoten festgelegt ist, so können zwei Knoten auch durch mehr als eine Kante miteinander verbunden sein. In diesem Fall spricht man von Mehrfachkanten.


Größte CliqueBearbeiten

Siehe: Maximale Clique.

Größte PaarungBearbeiten

Siehe: Maximale Paarung.


Größtes MatchingBearbeiten

Siehe: Maximale Paarung.

GroßvaterBearbeiten

Unter dem Großvater eines Knotens   in einem gerichteten Baum versteht man den Vater des Vaters von  .

Gültige FärbungBearbeiten

Siehe: Gültige Knotenfärbung.

Gültige KantenfärbungBearbeiten

Eine Kantenfärbung ist gültig (oder echt), falls keine inzidenten Kanten existieren, die mit der gleichen Farbe gefärbt sind.

Gültige KnotenfärbungBearbeiten

Eine Knotenfärbung ist gültig (oder echt), falls keine adjazenten Knoten existieren, die mit der gleichen Farbe gefärbt sind.

HBearbeiten

(zum Seitenanfang)

HalbblattBearbeiten

Beim Binärbaum heißt ein Knoten mit höchstens einem Sohn Halbblatt. Bei manchen Zählungen wird dann ein Blatt als 2 Halbblätter gezählt.
Die Seite des Knotens, bei der es keinen Sohn gibt, stellt zusammen mit dieser Richtung einen unmittelbaren Einfügepunkt dar.

HamiltonabschlussBearbeiten

Der Hamiltonabschluss (oder Hülle;  -Hülle) eines Graphen   ist der Obergraph (oder Supergraph) von   mit identischer Knotenmenge und zusätzlich w:iterativ eingefügten Kanten, welche nicht-adjazente (oder nicht-benachbarte; nicht-verbundene) Knoten mit Gradsumme   miteinander verbinden, so lange dies möglich ist. Der Hamiltonabschluss eines Graphen ist eindeutig.

Hamiltonscher GraphBearbeiten

Ein Graph heißt hamiltonsch, falls er einen Hamiltonkreis besitzt.

HamiltonkreisBearbeiten

Ein Hamiltonkreis ist ein Kreis, der alle Knoten des Graphen genau einmal enthält.

Hamiltonkreis ProblemBearbeiten

Das Hamiltonkreis Problem ist die Frage danach, ob ein gegebener Graph einen Hamiltonkreis besitzt. Dieses Problem ist im Allgemeinen NP-vollständig.
Für einige Graphenklassen ist das Problem jedoch polynomial lösbar. Siehe hierzu w:Hamiltonkreisproblem

HamiltonpfadBearbeiten

Ein Hamiltonpfad ist ein Pfad, der alle Knoten des Graphen enthält.

Handschlag-LemmaBearbeiten

Das Handschlag-Lemma besagt, dass die Summe der Knotengrade gleich   ist. (Jede Kante trägt bei genau zwei Knoten zum Knotengrad bei.) Daraus folgt, dass die Summe der Knotengrade stets gerade ist. Insbesondere existiert stets eine gerade Anzahl von Knoten, die ungeraden Grad haben.

HeiratssatzBearbeiten

Hauptartikel: Heiratssatz
In bipartiten Graphen   mit Bipartition   existiert genau dann eine Paarung   der Kardinalität   (die jeden Knoten aus   überdeckt), falls für jede Teilmenge   von   gilt, dass ihre Nachbarschaft mindestens so groß ist wie   selbst:
 
Siehe auch: Paarung.

HöheBearbeiten

Die Höhe eines Wurzelbaums ist die maximal auftretende Tiefe.
Sehr häufig auch um 1 mehr, da man dem leeren Baum die Höhe 0 und dem nur aus der Wurzel bestehenden Baum die Höhe 1 geben möchte.

HomöomorphieBearbeiten

Zwei Graphen heißen homöomorph, falls sie isomorph sind oder einen gemeinsamen Unterteilungsgraphen haben. Zwei Graphen sind genau dann homöomorph, wenn ihre Homöomorphie-Ursprünge isomorph sind. Anschaulich bedeutet dies, dass zwei homöomorphe Graphen aus einem gemeinsamen Ursprungsgraphen durch Einfügen neuer Knoten vom Grad 2 in bereits existierende Kanten hervorgehen.
Siehe auch: w:Planarer Graph.

Homöomorphie-UrsprungBearbeiten

Der Homöomorphie-Ursprung   eines Graphen   ist der kleinste Graph, zu dem   homöomorph ist. Man berechnet   mit dem folgenden w:Algorithmus:
  1. Falls   keinen Knoten vom Grad 2 besitzt (abgesehen von isolierten Knoten die nur eine Schleife besitzen) so ist  .
  2. Wähle einen Knoten   vom Grad 2 (außer isolierte Knoten mit einer Schleife) mit den beiden Nachbarn   und   (auch   ist möglich)
  3. Entferne  , füge dafür eine Kante von   nach   ein.
    Formal:  
  4. gehe zu 1
Siehe auch: w:Planarer Graph.

HypergraphBearbeiten

Als Hypergraph werden Graphen bezeichnet, bei denen Kanten mehr als nur zwei Knoten verbinden können. Kanten dieser Form nennt man gewöhnlich Hyperkanten. Mengentheoretisch betrachtet sind Hypergraphen dasselbe wie w:Mengensysteme.
Siehe auch: Hypergraph.

HyperkanteBearbeiten

Als Hyperkante werden Kanten in Hypergraphen bezeichnet. Diese können dort mehr als zwei Knoten miteinander verbinden.
Siehe auch: Hypergraph.

HypohamiltonschBearbeiten

Ein Graph   heißt hypohamiltonsch, wenn er keinen hamiltonschen Kreis besitzt, aber zu jedem seiner Knoten ein Kreis existiert, der alle anderen Knoten enthält.

IBearbeiten

(zum Seitenanfang)

IndexBearbeiten

Der Index eines Graphen ist definiert als:
  (Anzahl der Kanten - Anzahl der Knoten + Anzahl der Zusammenhangskomponenten)
  • Für alle Graphen   ist   und   ist genau dann ein Wald, wenn   gilt.
  • Der Index eines Graphen   ist stets kleinergleich der Anzahl seiner Kreise und   ist genau dann ein Kaktusgraph, wenn sein Index der Anzahl der Kreise in   entspricht.

Induzierter TeilgraphBearbeiten

Ist   ein Graph und   Teilmenge der Knotenmenge von  , so ist der von   induzierte Teilgraph ein w:Teilgraph, der durch Entfernung der Knoten aus   entsteht, die nicht in   liegen (bemerke: bei Entfernen eines Knotens   fallen auch alle mit   inzidenten Kanten weg).
Anschaulich bedeutet das: Der von   induzierte Teilgraph besteht aus den Knoten aus   und allen Kanten, die in   zwischen ihnen verlaufen.
Formal: der von   induzierte Teilgraph ist  

Innerer KnotenBearbeiten

Ein Knoten in einem Graph wird innerer Knoten genannt, wenn es sich bei dem Knoten nicht um ein Blatt handelt. Im Falle von gewurzelten Bäumen wird auch die Wurzel häufig nicht als innerer Knoten betrachtet.

InzidenzBearbeiten

Inzidenz bezeichnet eine Beziehung zwischen Knoten und Kanten in einem ungerichteten Graphen. Ein Knoten heißt in einem ungerichteten Graph inzident mit einer Kante, wenn er von dieser Kante berührt wird, das heißt, wenn diese ihn enthält.
Bei gerichteten Graphen unterscheidet man zwischen positiv inzidenten Kanten und negativ inzidenten Kanten. Eine gerichtete Kante ist positiv inzident zu ihrem Startknoten und negativ inzident zu ihrem Endknoten.

Siehe auch AdjazenzInzidenzmatrixNachbarschaft und Grad in Graphen

InzidenzmatrixBearbeiten

Eine Inzidenzmatrix zu einem Graph mit   Knoten und   Kanten ist eine  -Matrix, bei der die Zeilen mit den Knoten und die Spalten mit den Kanten identifiziert werden. Dazu nummeriert man die Knoten von 1 bis   und die Kanten von 1 bis   durch und trägt in die Matrix die Beziehungen der Knoten zu den Kanten ein.
Jede Spalte der Inzidenzmatrix enthält genau zwei von Null verschiedene Einträge. In ungerichteten Graphen zweimal die 1 und in schleifenfreien gerichteten Graphen einmal die 1 (Endknoten) und einmal die -1 (Startknoten).

Siehe auch w:Repräsentation von Graphen im Computer

InzidenzrelationBearbeiten

Zur Definition sehr allgemeiner, nämlich ungerichteter Graphen mit Schlingen (Kanten von einem Knoten zu sich selbst) und parallelen Kanten (Mehrfachkanten) reicht die vereinfachende Graphendefinition   mit   mit   nicht aus, denn hier müssten z. B. in   Duplikate erlaubt sein. Man führt daher eine Inzidenzrelation ein und benennt die Elemente aus   mit einem eindeutigen Namen  , der nicht von den Knoten der Kante abhängt. Mittels solcher eindeutiger Elemente können nun auch Mehrfachkanten und Schlingen definiert werden. Die Inzidenzrelation wird dann definiert als  , d. h. zu jedem Knoten wird für jede Kante, die ihn berührt, ein Element   mit   und   in   aufgenommen. Schlingen werden somit über jeweils ein Element der Inzidenzrelation, zwei parallele Kanten über vier Elemente der Inzidenzrelation eindeutig repräsentiert.

InzidenzvektorBearbeiten

Zu einer beliebig vorgegebenen Nummerierung der Kanten   ist ein Element   ein Inzidenzvektor zur (gewichteten) Kantenmenge  , falls   haben die Kanten zudem ein nichtnegatives Gewicht, werden die Kanteneinträge im Vektor mit diesem Gewicht multipliziert. Die Menge aller so beschriebenen Kreise bilden einen w:Untervektorraum von  , den w:Zyklenraum. Die Menge der w:Fundamentalkreise sind eine Basis. Der Raum ergibt in direkter Summe mit dem w:Kozyklenraum ganz  

Isolierter KnotenBearbeiten

Ein isolierter Knoten ist ein Knoten mit Grad 0 (also ohne Nachbarn)

IsomorphieBearbeiten

Zwei Graphen   und   heißen isomorph, falls eine bijektive Abbildung   existiert, sodass für alle   gilt:   genau dann, wenn  

JBearbeiten

(zum Seitenanfang)

JordankurveBearbeiten

Eine Jordankurve ist eine stetige und schnittpunktfreie Kurve mit Anfangs- und Endpunkt, wobei Anfangs- und Endpunkt übereinstimmen können. Die Kanten eines planaren Graphen sind Jordankurven zwischen seinen Endpunkten in einer Ebene.

KBearbeiten

(zum Seitenanfang)

k-BaumBearbeiten

Ein ungerichteter Graph heißt k-Baum, wenn er wie folgt rekursiv erzeugbar ist:
  • Der vollständige Graph   ist ein k-Baum.
  • Fügt man zu einem k-Baum   einen neuen Knoten   hinzu, indem man   mit allen Knoten einer Clique der Größe k aus   verbindet, so ist dieser neue Graph ebenfalls ein k-Baum.
Ein partieller  -Baum entsteht durch die Entfernung von Kanten aus einem  -Baum: Ist   ein  -Baum, so ist   mit   ein partieller  -Baum.
Gelegentlich werden auch Bäume mit dem maximalen Grad   als  -Bäume bezeichnet. Korrekter ist in diesem Fall die Bezeichnung  -närer Baum.

KaktusgraphBearbeiten

Ein Graph   heißt Kaktusgraph, wenn alle seine Kreise paarweise Kantendisjunkt sind (sich also höchstens gemeinsame Knoten teilen).
Ein Graph   ist ein Kaktusgraph genau dann, wenn die Anzahl seiner Kreise seinem Index   entspricht.

KanteBearbeiten

Eine Kante ist ein Element der Kantenmenge eines Graphen. Die Kantenmenge eines Graphen   wird meist mit   (für engl. edge) bezeichnet. Sie beschreibt, wie die Knoten der Knotenmenge des Graphen miteinander verbunden sind. Je nach Typ des Graphen unterscheiden sich die möglichen Formen von Kanten.
Siehe auch: w:Typen von Graphen in der Graphentheorie.
Vergleiche: Bogen bei Digraphen (gerichteten Graphen)

Kantenbewerteter GraphBearbeiten

Ein Kantenbewerteter Graph ist ein Graph   mit einer Kantenbewertung  , welche formal eine Abbildung der Kantenmenge auf die reellen Zahlen ist. Die Kantenbewertungsfunktion   bezeichnet man oft auch als Kostenfunktion oder Kantengewichtsfunktion.
Kantenbewertungen spielen häufig eine Rolle in w:Optimierungsproblemen, wie dem Travelling Salesman Problem, wobei die Bewertungen z. B. für Fahrtzeiten auf verschiedenen Straßen (Geschwindigkeitsbegrenzungen, Staus), Fahrtkosten (Maut, Benzinverbrauch) oder Streckenlänge steht.

KantenfärbungBearbeiten

Ist   ein ungerichteter Graph ohne Mehrfachkanten und   eine Abbildung von   in die Menge der natürlichen Zahlen  , so nennt man   eine Kantenfärbung von  .

Kantendisjunkte WegeBearbeiten

Zwei Wege heißen kantendisjunkt, wenn sie keine gemeinsamen Kanten haben. Im Gegensatz zu disjunkten Wegen dürfen kantendisjunkte Wege mehrere Knoten gemeinsam enthalten.

KantenfärbungszahlBearbeiten

Siehe: Chromatischer Index.

KantenfeldBearbeiten

Ein Kantenfeld ist eine Darstellungsart für gerichtete Graphen nach folgendem Schema:
 
wobei   die Anzahl der Knoten,   die Anzahl der Kanten und   die Kanten sind mit  .

KantengraphBearbeiten

Der w:Kantengraph (engl. line graph)   eines Graphen   entsteht folgendermaßen aus  :
  • Für jede Kante   aus   setze einen Knoten   in  .
  • Füge eine Kante   in   genau dann ein, wenn die Kanten   und   in   einen gemeinsamen Endknoten haben.

KantenkontraktionBearbeiten

Ist   eine Kante, die die Knoten   und   verbindet, dann ist die Kontraktion von   eine „Verschmelzung“ von   und  , d. h.  ,   und   werden durch einen neuen Knoten   ersetzt, der mit allen Nachbarn von   und   verbunden wird.
Haben   und   einen gemeinsamen Nachbarn  , so verlaufen im resultierenden Graphen parallele Kanten zwischen   und   oder allgemeiner: wenn zwischen   und     parallele Kanten und zwischen   und     parallele Kanten verlaufen, so verlaufen nach der Kontraktion von   zwischen   und   genau   parallele Kanten.

Kantenpanzyklische GraphenBearbeiten

Ein Graph heißt kantenpanzyklisch falls jede Kante auf einem Kreis der Länge   liegt für alle  . Kantenpanzyklische Graphen sind auch knotenpanzyklisch und damit auch panzyklisch.

KantenüberdeckungBearbeiten

Eine Kantenüberdeckung in einem ungerichteten Graphen   ist eine Menge   mit der Eigenschaft, dass jeder Knoten von   in einer Kante aus   enthalten ist.
  ist Kantenüberdeckung in   gdw.  .

Kanten-UnterteilungBearbeiten

Eine Unterteilung einer Kante ist das Einfügen eines Knotens in die Kante
Formal: Ist   ein Graph und  , so entsteht   durch Unterteilung von   als  . Die Voraussetzung   ist für die formale Korrektheit notwendig.

KantenzusammenhangszahlBearbeiten

Die Kantenzusammenhangszahl   eines Graphen ist die kleinste Anzahl an Kanten, die man entfernen muss, um den Zusammenhang zu zerstören.
Siehe auch: Schnitt

KernBearbeiten

In einem gerichteten Graphen bezeichnet man eine Menge von Knoten als Kern (engl. kernel), wenn sie zugleich stabil und dominierend ist.

KindBearbeiten

Kind oder Sohn ist die Bezeichnung für einen direkten Nachfolger in einem Wurzelbaum.

KnotenBearbeiten

Als Knoten oder Ecke bezeichnet man ein Element der Knotenmenge eines Graphen. Ist   der Graph, wird seine Knotenmenge für gewöhnlich mit   (englisch vertex) bezeichnet. Graphen bestehen neben der Knotenmenge noch aus einer dazugehörigen Kantenmenge   (englisch edge), die beschreibt, wie die einzelnen Knoten des Graphen durch Kanten verbunden sind.
Siehe auch: w:Typen von Graphen in der Graphentheorie.

Knotendisjunkte WegeBearbeiten

Zwei Wege heißen knotendisjunkt oder kreuzungsfrei, wenn sie keine gemeinsamen Knoten haben. Knotendisjunkte Wege sind immer auch kantendisjunkt. (w:Kantendisjunkte Wege sind aber nicht unbedingt knotendisjunkt!)

KnotenfärbungBearbeiten

Eine  -Knotenfärbung ist eine Abbildung der Knotenmenge auf die Menge   (also wird jedem Knoten eine von   Zahlen oder „Farben“ zugewiesen).
Siehe auch: Gültige Knotenfärbung, Chromatische Zahl, w:Vier-Farben-Satz.

KnotenfärbungszahlBearbeiten

Siehe: Chromatische Zahl.

KnotenfeldBearbeiten

Ein Knotenfeld ist eine Darstellungsart für gerichtete Graphen mit folgendem Aufbau:
 
wobei   die Anzahl der Knoten,   die Anzahl der Kanten und   Ausgangsgrad des Knotens sind.

Knotenpanzyklische GraphenBearbeiten

Ein Graph   heißt knotenpanzyklisch, wenn jeder Knoten auf einem Kreis der Länge   liegt, für alle  .
Kantenpanzyklische Graphen sind knotenpanzyklisch, knotenpanzyklische Graphen sind panzyklisch.

KnotenüberdeckungBearbeiten

Als Knotenüberdeckung in einem ungerichteten Graphen bezeichnet man eine Teilmenge   seiner Knoten, für die gilt, dass jede Kante wenigstens einen Knoten aus   enthält.
  ist Knotenüberdeckung in   gdw.  .
Siehe auch: w:Knotenüberdeckungen, Cliquen und stabile Mengen.

KnotenüberdeckungszahlBearbeiten

Als Knotenüberdeckungszahl   eines ungerichteten Graphen wird die kleinste Zahl   bezeichnet, für die eine Knotenüberdeckung der Größe   existiert.
Siehe auch: w:Knotenüberdeckungen, Cliquen und stabile Mengen.

KnotenzusammenhangszahlBearbeiten

Die Knotenzusammenhangszahl (oft kurz Zusammenhangszahl genannt) eines Graphen   ist die kleinste Zahl   für die   einen Separator der Größe   besitzt.
Die Notation ist in der Literatur inkonsistent, u. A. sind   und   gebräuchlich.

KomplementBearbeiten

Siehe: Komplementärer Graph.

Komplementärer GraphBearbeiten

Der komplementäre Graph   eines Graphen   hat die gleiche Knotenmenge wie   und in   sind zwei Knoten   und   genau dann adjazent, wenn sie es in   nicht sind (  hat also genau die Kanten, die   nicht hat).
Als selbstkomplementär bezeichnet man Graphen, die isomorph zu ihrem komplementären Graphen sind.

KomplementgraphBearbeiten

Siehe: Komplementärer Graph.

KozyklenraumBearbeiten

Ist der Vektorraum aller durch Schnitte erzeugten Inzidenzvektoren. Er ist w:Unterraum des   und gibt in direkter Summe mit dem Zyklenraum den ganzen Raum. Eine basis ist immer durch die Fundamentalschnitte gegeben

KreisBearbeiten

Ein Kreis   ist eine Folge von Knoten, die bis auf den ersten und letzten Knoten w:paarweise verschieden sind, wobei sowohl   und   für alle   als auch   und   adjazent sein müssen.
Enthält ein Kreis alle Knoten des Graphen, so nennt man ihn Hamiltonkreis.
Ein Graph der nur aus einem Kreis (der Länge  ) besteht bezeichnet man mit  .

Kreuzungsfreie WegeBearbeiten

Wege heißen kreuzungsfrei, wenn sie keinen gemeinsamen inneren Knoten haben.

Kubischer GraphBearbeiten

Ein Graph heißt kubisch, falls er 3-regulär ist.

LBearbeiten

(zum Seitenanfang)

Länge eines KreisesBearbeiten

Die Länge eines Kreises ist die Anzahl seiner Kanten.

Länge eines PfadesBearbeiten

Siehe: Länge eines Weges.

Länge eines WegesBearbeiten

Die Länge eines Weges ist die Anzahl seiner Kanten.

Länge eines ZyklusBearbeiten

Siehe: Länge eines Kreises.

LinegraphBearbeiten

Siehe: Kantengraph.

MBearbeiten

(zum Seitenanfang)

MatchingBearbeiten

Siehe: Paarung.

MatchingzahlBearbeiten

Siehe: Paarungszahl.

Maximale CliqueBearbeiten

Eine Maximale Clique   eines Graphen   ist ein Teilgraph von  , der ein vollständiger Graph ist, und der in keinem größeren Teilgraph von   enthalten ist, der auch ein vollständiger Graph ist.
Gibt es in   zudem keinen vollständigen Teilgraphen, der mehr Knoten als   enthält, so nennt man   größte Clique.
Siehe auch: Cliquenzahl

Maximale PaarungBearbeiten

Eine Paarung   ist eine maximale Paarung, wenn keine Paarung   mit   existiert.
Satz von Berge (1957): Eine Paarung   ist genau dann eine maximale Paarung, wenn kein M-alternierender Weg existiert.

Maximales MatchingBearbeiten

Siehe: Maximale Paarung.

MaximalgradBearbeiten

Der Maximalgrad   eines Graphen   ist die größte Zahl  , für die in   ein Knoten vom Grad   existiert.
Entspricht der Maximalgrad dem Minimalgrad, so spricht man von einem regulären Graphen.

MehrfachkanteBearbeiten

Zu einer Mehrfachkante oder Multikante fasst man eine Menge von Kanten zusammen, die zwischen denselben Knoten verlaufen und in gerichteten Graphen zusätzlich identische Orientierung besitzen.
Siehe auch: w:Typen von Graphen in der Graphentheorie.

MehrfachschleifeBearbeiten

Eine Mehrfachschleife ist eine gerichtete Mehrfachkante, die zugleich Schleife ist.

Metrischer GraphBearbeiten

Ein Metrischer Graph ist ein kantenbewerteter Graph, der die w:Dreiecksungleichung erfüllt, d. h. sind  , so gilt stets  , wobei   die Bewertung der Kante  .
Intuitiv formuliert: der Weg von   über   nach   darf nicht kürzer sein, als der direkte Weg von   nach  .
Distanzgraphen sind stets Metrisch.

Metrisches Traveling-Salesman-ProblemBearbeiten

Das Metrische Travelling Salesman Problem (vergleiche: Travelling Salesman Problem) ist die Frage nach einem kürzesten Hamiltonkreis in einem vollständigen, kantenbewerteten, metrischen Graphen.
Dieses Problem ist NP-Vollständig
Siehe auch: w:Problem des Handlungsreisenden.

MinimalgradBearbeiten

Der Minimalgrad   eines Graphen   ist die kleinste Zahl  , für die in   ein Knoten vom Grad   existiert.
Entspricht der Minimalgrad dem Maximalgrad, so spricht man von einem regulären Graphen.

MinorBearbeiten

Ein Graph   ist Minor eines Graphen  , falls   aus   durch beliebig viele Kantenkontraktionen entsteht.

MultigraphBearbeiten

Mit Multigraph bezeichnet man einen Graphen mit Mehrfachkanten

MultikanteBearbeiten

Siehe: Mehrfachkante.

NBearbeiten

(zum Seitenanfang)

NachbarBearbeiten

Ein Knoten   ist Nachbar eines Knotens   genau dann, wenn   also wenn sie durch eine Kante verbunden sind.
Bei gerichteten Graphen unterscheidet man positive - und negative Nachbarn. Genau dann, wenn   eine gerichtete Kante von   nach   führt, nennt man   positiven Nachbar von   und   negativen Nachbarn von  .

NachbarschaftBearbeiten

Die Nachbarschaft  , manchmal auch  , eines Knotens   ist die Menge seiner Nachbarn.
Bei gerichteten Graphen unterscheidet man die positive Nachbarschaft   (die Menge der Knoten, zu denen eine gerichtete Kante von   aus führt) und die negative Nachbarschaft   (die Menge der Knoten, von denen aus eine gerichtete Kante zu   führt).
Die abgeschlossene Nachbarschaft ist  , also nichts anderes als die Nachbarschaft von  , zu der   selbst hinzugefügt wurde.
(Analog sind   und   definiert.)

NachbarschaftslisteBearbeiten

Siehe: Adjazenzliste.

NachbarschaftsmatrixBearbeiten

Siehe: Adjazenzmatrix.

NachfolgerBearbeiten

Ein Knoten   heißt Nachfolger eines Knoten   in einem gerichteten Graphen falls es einen Pfad gibt, welcher von   nach   geht.

NachfolgermengeBearbeiten

Die Menge aller Nachfolger eines Knoten  . Also alle in einem Graphen von   durch einen Pfad erreichbaren Knoten.
Formal:   mit   (siehe auch: w:Transitive Hülle)

NetzwerkBearbeiten

Ein Netzwerk ist ein gerichteter, kantenbewerteter Graph mit zwei ausgezeichneten Knoten, der Quelle und der Senke.
Die Kanten dürfen nur positiv bewertet sein und die Kantenbewertung wird in diesem Zusammenhang in der Regel als Kapazität der gerichteten Kante bezeichnet.
In Netzwerken werden hauptsächlich sogenannte Flüsse betrachtet. Meist ist man hierbei am maximal möglichen s-t-Fluss interessiert, den man beispielsweise mit dem Edmonds-Karp-Algorithmus berechnen kann.

OBearbeiten

(zum Seitenanfang)

ObergraphBearbeiten

Ein Graph   ist Obergraph eines Graphen  , wenn   Teilgraph von   ist.

OnkelBearbeiten

Unter dem Onkel eines Knotens   in einem Binärbaum versteht man den Sohn des Großvaters von  , der nicht der Vater von   ist.

Ordnung eines BaumesBearbeiten

Als Ordnung eines w:Out-Trees wird die größte Anzahl Kinder eines seiner Knoten bezeichnet.

PBearbeiten

(zum Seitenanfang)

Paarer GraphBearbeiten

Siehe: Bipartiter Graph.

PaarungBearbeiten

Eine Paarung (auch Matching, Zuordnung oder unabhängige Kantenmenge) in einem ungerichteten Graphen   ist eine Menge   mit der Eigenschaft, dass keine zwei Kanten aus   in   durch einen gemeinsamen Knoten verbunden sind:
  ist unabhängig in   gdw.  .
Siehe auch: perfekte Paarung, maximale Paarung.

PaarungszahlBearbeiten

Die Paarungszahl ist die Größe einer maximalen Paarung.

Panzyklische GraphenBearbeiten

Ein Graph heißt panzyklisch wenn er für alle   einen Kreis der Länge   besitzt.
Insbesondere sind panzyklische Graphen damit hamiltonsch.
Siehe auch: Knotenpanzyklische Graphen, Kantenpanzyklische Graphen.

Parallele KantenBearbeiten

Zwei Kanten heißen parallel, falls sie zwischen denselben Knoten verlaufen, d. h. zu denselben Knoten inzident sind.

Partieller k-BaumBearbeiten

Siehe: k-Baum.

PartitionBearbeiten

Sei   ein Graph. Eine Zerlegung (Partition) der Knotenmenge   in   w:disjunkte Teilmengen   heißt  -Partition, falls keine adjazenten Ecken in einem gemeinsamen   liegen. (Anschaulich heißt das: Alle Kanten verlaufen zwischen diesen Teilmengen, keine innerhalb einer der Teilmengen.)
  • Besitzt ein Graph   eine  -Partition, so sagt man auch „  ist  -partit“ oder „  ist ein  -partiter Graph“.
  • Die chromatische Zahl von   ist das kleinste  , sodass   eine  -Partition besitzt (färbe alle Elemente einer Partitionsmenge mit der gleichen Farbe).
  • In der Praxis arbeitet man häufig mit Paarungen in bipartiten (2-partiten) Graphen.

Perfekte EliminationsordnungBearbeiten

Als perfekte Eliminationsordnung bezeichnet man eine Knotenreihenfolge   des Graphen  , so dass für jeden Graphen mit der (durch Eliminierung der Knoten   bis  ) eingeschränkten Knotenmenge   gilt:   ist simplizial in  . Jeder (in Bezug auf die gewählte Ordnung) „kleinste“ Knoten in   bildet also mit seinen Nachbarn eine Clique. Dies gilt beispielsweise für alle Blätter eines Baums, so dass ein sukzessives Eliminieren von Blättern eines Baums eine perfekte Eliminationsordnung für diesen Baum liefert.

Perfekte PaarungBearbeiten

Eine perfekte Paarung (auch vollständige Zuordnung) ist eine Paarung  , bei der jeder Knoten mit genau einer Kante aus   inzidiert.

Perfektes MatchingBearbeiten

Siehe: Perfekte Paarung.

PfadBearbeiten

Ein Pfad   ist eine Folge von Knoten, mit paarweise verschiedenen Knoten, wobei immer   und   adjazent sein müssen für alle  .
Enthält   alle Knoten von  , so nennt man   einen Hamiltonpfad.
Fordert man nicht, dass die Knoten von   paarweise verschieden sind, so spricht man von einem Weg.

Planarer GraphBearbeiten

Ein planarer Graph ist ein Graph, der sich in der Ebene darstellen lässt, ohne dass sich seine Kanten schneiden.
  • Satz von Kuratowski: Ein Graph ist genau dann planar, wenn er keinen Teilgraphen enthält, der einen vollständigen Graphen   oder   als Minor hat.
Siehe: w:Planarer Graph.

Pseudo-achromatische ZahlBearbeiten

Die pseudo-achromatische Zahl   eines Graphen   ist die größte Zahl  , für die   eine vollständige Knotenfärbung hat.
Im Gegensatz zur achromatischen Zahl ist hier nicht die Gültigkeit der Färbung verlangt.
Siehe auch: chromatische Zahl, achromatische Zahl.

QBearbeiten

(zum Seitenanfang)

QuelleBearbeiten

Eine Quelle in einem gerichteten Graph ist ein Knoten, der keinen Vorgänger hat.
Im Zusammenhang mit Flüssen versteht man unter einer Quelle einen Knoten, aus dem mehr Fluss hinaus als hinein fließt.
Siehe auch: Senke.

RBearbeiten

(zum Seitenanfang)

RandBearbeiten

Der Rand entspricht der Menge aller Knoten maximaler Exzentrizität eines Graphen.

Regulärer GraphBearbeiten

Ein Graph heißt regulär, falls alle seine Knoten den gleichen Grad (ungerichteter Graph) bzw. den gleichen Eingangs- und Ausgangsgrad (gerichteter Graph) besitzen. Ist der Grad aller Knoten eines regulären Graphen  , so bezeichnet man ihn als  -regulär. Ein Wurzelbaum heißt k-regulär, wenn alle Knoten mit Ausnahme der Blätter den Ausgangsgrad   haben.
Siehe auch: w:Nachbarschaft und Grad in Graphen.

RadiusBearbeiten

Der Radius ist das kleinste Maximum der minimalen Weglängen der Knoten.
Der Radius   eines Graphen   ist das Minimum der Exzentrizitäten der Knoten von  .
Für alle Graphen   gilt  , wobei   der Durchmesser von   ist.
Die Knoten, deren Exzentrizität dem Radius entsprechen, bilden das Zentrum von  .

RückwärtskanteBearbeiten

Siehe: Vorwärtskante.

SBearbeiten

(zum Seitenanfang)

Satz von HallBearbeiten

Siehe: Heiratssatz.

SchleifeBearbeiten

Als Schleife oder Schlinge wird in einem Graph eine Kante bezeichnet, die einen Knoten mit sich selbst verbindet, das heißt eine Kante der Form  .
Siehe auch: Mehrfachschleife.

Schleifenfreier GraphBearbeiten

Siehe: Schleifenloser Graph.

Schleifenloser GraphBearbeiten

Als schleifenlosen oder schleifenfreien Graph bezeichnet man einen gerichteten Graph, der keine Schleife enthält.

SchlingeBearbeiten

Siehe: Schleife.

SchnittBearbeiten

Eine Zerlegung (oder Partition)   der Knotenmenge   eines Graphen in zwei nichtleere w:Teilmengen   und   mit   und   heißt Schnitt.
Der Begriff spielt insbesondere bei Netzwerken mit ausgezeichneten Knoten q (der Quelle) und s (der Senke) eine Rolle. Hier nennt man eine Teilmenge S von Knoten, die q aber nicht s enthält, einen Schnitt. Die Vereinigungsmenge der Kanten, die von S nach V \ S führen sowie der Kanten, die von V \ S nach S führen, nennt man den durch S definierten Schnitt. Man spricht dann auch, wenn im Kontext jeweils klar ist, ob die Knoten- oder die Kantenmenge gemeint ist, vom Schnitt S und meint die durch S definierte Kantenmenge.
Siehe auch: w:Flüsse und Schnitte in Netzwerken.

SchnittknotenBearbeiten

Siehe: Artikulation.

Schwache ZusammenhangskomponenteBearbeiten

Eine schwache Zusammenhangskomponente eines gerichteten Graphen ist eine maximale Teilmenge seiner Knoten, in der zwischen je zwei beliebigen Knoten dieser Menge ein ungerichteter Weg existiert (man ersetze dazu jede gerichtete durch eine ungerichtete Kante).

SehneBearbeiten

In einem Graphen   bezeichnet Sehne eine Kante von  , die zwei Knoten eines Kreises in   verbindet, selbst jedoch nicht Teil des Kreises ist.

Semieulerscher GraphBearbeiten

Ein Graph heißt semieulersch, wenn in ihm ein Eulerweg existiert. Eine Eulertour ist zwar ebenfalls ein Eulerweg, aber in der Regel meint man mit „semieulersch“ dass keine Eulertour existiert, da man in diesem Fall von einem eulerschen Graphen sprechen würde.

Semihamiltonscher GraphBearbeiten

Ein Graph heißt semihamiltonsch, wenn in ihm ein Hamiltonpfad existiert. Ein Hamiltonkreis induziert zwar Hamiltonpfade, aber in der Regel meint man mit „semihamiltonsch“ dass kein Hamiltonkreis existiert, da man in diesem Fall von einem hamiltonschen Graphen sprechen würde.

SenkeBearbeiten

Eine Senke ist ein Knoten in einem gerichteten Graphen, welcher keinen Nachfolger hat.
Im Zusammenhang mit Flüssen versteht man unter einer Senke einen Knoten, in den mehr Fluss hinein als hinaus fließt.
Eine Senke heißt universelle Senke, falls sie eingehende Kanten von jedem anderen Knoten hat, falls also ihr Eingangsgrad gleich   ist.
Siehe auch: Quelle.

SeparatorBearbeiten

Ein Separator (auch Trenner oder Trennende Knotenmenge genannt) ist eine Knotenmenge  , deren Entfernung den Zusammenhang zerstört d. h. dass eine Zusammenhangskomponente zerfällt. Es existieren also Knoten   für die jeder Weg von   nach   einen Knoten aus   enthält.
Fallen   und   durch entfernen von   in verschiedene Zusammenhangskomponenten, so nennt man   auch einen  -Separator. Befinden   und   sich schon in   in verschiedenen Zusammenhangskomponenten, so kann man   als  -Separator auffassen.
Im Fall eines vollständigen Graphen existiert keine solche Menge. Für diesen Fall wird üblicherweise ganz   als Separator definiert.
Siehe auch: Menger'sche Sätze

Simplizialer KnotenBearbeiten

Ein Knoten   des Graphen   heißt simplizial, wenn er gemeinsam mit all seinen Nachbarn eine Clique, d. h. einen vollständigen Teilgraphen in   bildet.

SohnBearbeiten

Sohn oder Kind ist die Bezeichnung für einen direkten Nachfolger in einem Wurzelbaum.

SpannbaumBearbeiten

Ein Spannbaum (auch spannender Baum genannt) eines Graphen ist ein Teilgraph, der ein Baum ist und alle Knoten des Graphen enthält.
Siehe auch: w:Spannbaum.

SpannerBearbeiten

Ein k-Spanner eines Graphen   ist ein sämtliche Knoten umfassender (also spannender) Teilgraph, in welchem die Distanz jedes Knotenpaares höchstens dem  -fachen seiner Distanz in   entspricht.

SpannwaldBearbeiten

Siehe Gerüst.

Stabile MengeBearbeiten

Eine stabile oder unabhängige (engl. independent oder stable) Menge ist in einem ungerichteten Graphen eine Menge von Knoten, zwischen denen keine Kante verläuft.
Siehe auch: Kern, w:Knotenüberdeckungen, Cliquen und stabile Mengen.

StabilitätszahlBearbeiten

Als Stabilitäts- oder Unabhängigkeitszahl   eines Graphen   bezeichnet man die größte Zahl   für die   eine Stabile Menge der größe   besitzt.
Da eine Menge genau dann unabhängig in   ist, wenn sie eine Clique im komplementären Graphen   ist, gilt  
Siehe auch: w:Knotenüberdeckungen, Cliquen und stabile Mengen.

Stark zusammenhängender GraphBearbeiten

Ein gerichteter Graph heißt stark zusammenhängend, wenn er nur eine starke Zusammenhangskomponente besitzt.

Starke ZusammenhangskomponenteBearbeiten

Eine starke Zusammenhangskomponente eines gerichteten Graphen ist eine maximale Teilmenge seiner Knoten, in der zwischen je zwei beliebigen Knoten dieser Menge in beide Richtungen mindestens ein gerichteter Weg existiert.

Startknoten einer KanteBearbeiten

Ist   eine gerichtete Kante, so bezeichnet man   als ihren Startknoten und   als ihren Endknoten.
Bei ungerichteten Kanten   kann man   und   sowohl als Startknoten als auch als Endknoten bezeichnen. Hier spricht man in der Regel aber einfach von den beiden „zu   inzidenten Knoten“.

SternBearbeiten

Ein Graph vom Grad k ist ein Stern, wenn ein Knoten (die Mitte des Sterns) Grad k (Kanten zu allen anderen Knoten) hat, und alle anderen Knoten Grad 1 haben (nur mit dem Knoten in der Mitte verbunden sind).

SubgraphBearbeiten

Siehe: Teilgraph.

Symmetrischer GraphBearbeiten

Ein symmetrischer Graph ist ein gerichteter Graph, der mit jeder Kante   auch die Kante   enthält.
Hauptartikel: w:Symmetrischer Graph.
Siehe auch: w:Typen von Graphen in der Graphentheorie.

TBearbeiten

(zum Seitenanfang)

TaillenweiteBearbeiten

Die Taillenweite   eines Graphen   ist die Länge eines kürzesten Kreises in  . Ist   ein Wald (hat also keine Kreise) so setzt man  . Aufgrund der englischen Bezeichnung girth findet man auch die Notation  .

TeilgraphBearbeiten

Ein Teilgraph eines Graphen   ist ein Graph, der durch Entfernen von beliebigen Knoten und Kanten aus   entsteht (bemerke: bei Entfernen eines Knotens   fallen auch alle mit   inzidenten Kanten weg).
Siehe auch: Obergraph, Induzierter Teilgraph.

TiefeBearbeiten

Die Tiefe oder auch Suchtiefe eines Knotens in einem Wurzelbaum ist die Anzahl der Kanten im Weg von der Wurzel bis zum Knoten.
Siehe auch: Höhe.

Topologische OrdnungBearbeiten

Die Knotenreihenfolge eines gerichteten, azyklischen Graphen heißt topologische Ordnung oder topologische Sortierung, wenn für alle Kanten   des Graphen gilt:   liegt in dieser Reihenfolge vor  .

Topologische SortierungBearbeiten

Siehe: Topologische Ordnung bzw. w:Topologische Sortierung.

Travelling Salesman ProblemBearbeiten

Das Travelling Salesman Problem (Problem des Handlungsreisenden) ist die Frage nach einem kürzesten Hamiltonkreis in einem vollständigen, kantenbewerteten Graphen, also ein Kreis, der jeden Knoten genau ein mal passiert und eine minimale Summe der Kantenbewertungen der passierten Kanten hat.
Siehe auch: w:Problem des Handlungsreisenden.

Triangulierter GraphBearbeiten

Ein endlicher, schlichter und ungerichteter Graph heißt trianguliert oder auch chordal, wenn er keine induzierten Kreise   mit   enthält. Mit anderen Worten: Jeder induzierte Kreis ist ein Dreieck (lat. triangulum). Man nennt dabei einen Kreis induziert, wenn zwischen den Knoten, die den Kreis bilden, keine weiteren Kanten (sogenannte Sehnen, engl. chord) im Ursprungsgraphen existieren.
Siehe auch: w:Triangulierter Graph.

Triviale PartitionBearbeiten

Die Triviale Partition eines Graphen ist die Partition, in der jeder Knoten in einer eigenen Partitionsmenge liegt.

Trivialer KreisBearbeiten

Die Folge   von Knoten bestehend aus nur einem Knoten erfüllt die Definition eines Kreises

Trivialer ZyklusBearbeiten

Die Folge   von Knoten bestehend aus nur einem Knoten erfüllt die Definition eines Zyklus

TurniergraphBearbeiten

Ein Turniergraph ist ein Graph, in dem zwischen je zwei Knoten genau eine Kante existiert.
Siehe auch: w:Turniergraph

UBearbeiten

(zum Seitenanfang)

UmfangBearbeiten

Die Länge eines längsten Weges in einem Graphen ist sein Umfang.

Unabhängige KnotenmengeBearbeiten

Siehe: Stabile Menge.

Unabhängige KantenmengeBearbeiten

Siehe Paarung.

Unabhängige MengeBearbeiten

Siehe: Stabile Menge.

UnabhängigkeitszahlBearbeiten

Siehe: Stabilitätszahl.

Unendlicher GraphBearbeiten

Ein unendlicher Graph ist ein Graph, dessen Knotenzahl unendlich ist.
Siehe auch: w:Unendlicher Graph

Ungerichtete KanteBearbeiten

Eine ungerichtete Kante verbindet zwei Knoten eines Graphen ohne Beachtung einer Reihenfolge. Eine ungerichtete Kante wird daher als zweielementige Menge von Knoten notiert.
Siehe auch: Gerichtete Kante, w:Typen von Graphen in der Graphentheorie.

Ungerichteter GraphBearbeiten

Ein ungerichteter Graph ist ein Graph, der keine gerichteten Kanten enthält.
Siehe auch: w:Typen von Graphen in der Graphentheorie.

Uniformer HypergraphBearbeiten

Ein uniformer Hypergraph ist ein Hypergraph, in dem alle Hyperkanten gleich viele Knoten miteinander verbinden.

Universaler KnotenBearbeiten

Ein universaler Knoten ist ein Knoten, welcher zu allen anderen Knoten im Graphen adjazent ist.

UnterbaumBearbeiten

Ein Unterbaum ist ein spezieller Teilgraph eines Baumes, der selbst als kompletter Baum angesehen werden kann.

UntergraphBearbeiten

Siehe: Teilgraph.

UnterteilungsgraphBearbeiten

Ein Unterteilungsgraph F eines Graphen G entsteht aus diesem durch Kanten-Unterteilung.

Unzusammenhängender GraphBearbeiten

Ein Unzusammenhängender Graph ist ein Graph, der mindestens zwei Zusammenhangskomponenten hat.

VBearbeiten

(zum Seitenanfang)

ValenzBearbeiten

Siehe: Grad.

ValenzsequenzBearbeiten

Siehe: Gradfolge.

VaterBearbeiten

Vater ist die Bezeichnung für den direkten Vorgänger in einem Wurzelbaum.

VerbesserungspfadBearbeiten

Ist   ein Graph und   eine Paarung in  , dann ist ein Verbesserungspfad (auch  -alternierender Pfad) ein Pfad  , der abwechselnd Kanten aus   und Kanten aus   enthält, wobei an beiden Enden Knoten liegen, welche mit keiner Kante aus   inzidieren (also sind auch die beiden Endkanten von   aus  ).
Ein solcher Pfad heißt Verbesserungspfad, da man eine Paarung   mit   erhalten kann, indem man die Kanten von  , die in   liegen aus   entfernt und dafür die anderen Kanten von   zu   hinzufügt.
Satz von Berge (1957): Eine Paarung ist genau dann maximal, wenn es keinen Verbesserungspfad gibt.

VergleichbarkeitsgraphBearbeiten

Ein (gerichteter) Vergleichbarkeitsgraph ist ein gerichteter Graph, dessen Kanten einer w:Ordnungsrelation auf seinen Knoten entsprechen. Sei beispielsweise   eine w:Halbordnung auf der Knotenmenge   des Graphen  , so gilt für jede Kante   die Beziehung  .
Von einem ungerichteten Vergleichbarkeitsgraphen spricht man, wenn für jede Kante   gilt: (  oder  ).

Vollständige KnotenfärbungBearbeiten

Eine vollständige Knotenfärbung ist eine Knotenfärbung, bei der für jedes Paar   von Farben eine Kante   existiert, sodass   mit   und   mit   gefärbt ist. D. h. dass für jedes Farbenpaar benachbarte Knoten existieren, die mit diesen Farben gefärbt sind.
Beachte: eine vollständige Knotenfärbung muss nicht notwendig eine gültige Knotenfärbung sein.
Siehe auch: chromatische Zahl, achromatische Zahl, pseudo-achromatische Zahl.

Vollständige ZuordnungBearbeiten

Siehe: Perfekte Paarung.

Vollständiger GraphBearbeiten

Ein vollständiger Graph ist ein Graph, bei dem jeder Knoten mit jedem anderen Knoten durch genau eine Kante verbunden ist.
  • Den vollständigen Graphen mit   Knoten bezeichnet man mit  
Ein vollständiger  -partiter Graph ist ein p-partiter Graph bei dem jedes Paar von zwei Knoten aus verschiedenen Partitionsmengen adjazent ist
  • Den vollständigen multipartiten Graphen mit   Partitionsmengen, welche   Knoten enthalten, bezeichnet man mit  
Siehe auch:   und   in Charakterisierung von planaren Graphen.

VorgängerBearbeiten

Ein Knoten   heißt Vorgänger eines Knoten   in einem gerichteten Graphen falls es einen Pfad gibt, welcher von   nach   geht.

VorgängermengeBearbeiten

Die Menge aller Vorgänger eines Knoten  . Also alle Knoten in einem Graphen von denen   durch einen Pfad erreicht werden kann.
Formal:   mit   wobei   die Knotenmenge,   die Menge der Pfade und   die Vorgängermenge ist, (siehe auch: w:Transitive Hülle)

VorwärtskanteBearbeiten

Der Begriff Vorwärtskante hat ebenso wie die Begriffe Rückwärtskante, Querkante und Baumkante im Kontext der w:Tiefensuche in Graphen eine Bedeutung. Bei einer Tiefensuche werden die Kanten des Graphen, welche vom Tiefensuche-Algorithmus zum Durchlaufen des Graphen benutzt werden, als Baumkanten bezeichnet. Diejenigen Kanten, die nicht benutzt werden und von einem Knoten zu einem anderen Knoten im selben Teilbaum führen, der bei der Tiefensuche später besucht wird, heißen Vorwärtskanten. Diejenigen Kanten, die nicht benutzt werden und von einem Knoten zu einem anderen Knoten im selben Teilbaum führen, der bei der Tiefensuche bereits vorher besucht wurde, heißen Rückwärtskanten. Diejenigen Kanten, die „quer“ von einem Teilbaum zu einem anderen Teilbaum verlaufen, heißen Querkanten. Innerhalb des Tiefensuchbaums würde der Pfad zwischen zwei über eine Querkante verbundenen Knoten zunächst ein Auf- und dann ein Absteigen im Baum erfordern. Vorwärtskanten, Rückwärtskanten, Querkanten und Baumkanten ergeben insgesamt die Kantenmenge des Graphen.

WBearbeiten

(zum Seitenanfang)

WaldBearbeiten

Als Wald bezeichnet man in der w:Graphentheorie einen ungerichteten Graphen ohne Kreis.
Ein Graph ist genau dann ein Wald, wenn sein Index 0 ist.
Siehe auch: w:Wald (Graphentheorie).

WegBearbeiten

Ein Weg   ist eine Folge von Knoten, wobei immer   und   adjazent sein müssen für alle  .
Sind alle Knoten paarweise verschieden, so spricht man von einem Pfad.
In der Literatur wird ein Pfad meistens als Weg und ein Weg als w:Kantenzug bezeichnet.

WegüberdeckungBearbeiten

Eine Menge disjunkter Wege in einem gerichteten Graphen   mit der Eigenschaft, dass jeder Knoten von   auf einem dieser Wege liegt, heißt Wegüberdeckung.

WurzelBearbeiten

Eine Wurzel ist ein Knoten, von dem aus alle anderen Knoten des Graphen erreichbar sind.
Siehe auch: Wurzelbaum.

WurzelbaumBearbeiten

Ein Wurzelbaum oder gewurzelter Baum ist ein Baum   bei welchem ein Knoten als Wurzel   ausgezeichnet ist. Bäume ohne Wurzel bezeichnet man im Gegensatz zu Wurzelbäumen auch als freie Bäume. Die Auszeichnung einer Wurzel richtet den Baum aus und macht ihn zu einem gerichteten Graphen. In der Literatur wird oftmals implizit ein Wurzelbaum gemeint, wenn allgemein von einem Baum die Rede ist. Wurzelbäume verfügen gegenüber freien Bäumen über einige besondere Eigenschaften:
  • Jeder Knoten   auf einem einfachen Pfad von   zu einem anderen Knoten   heißt Vorfahr von  .
  • Ist   ein Vorfahr von  , so heißt   Nachfahr von  .
  • Ein direkter Vorfahr   heißt auch Vater,   heißt dann Sohn von  .
  • Die Höhe eines Wurzelbaums ist die maximale Länge eines Pfades von der Wurzel bis zu einem Blatt.
Hauptartikel: w:Gewurzelter Baum.

XBearbeiten

(zum Seitenanfang)

YBearbeiten

(zum Seitenanfang)

ZBearbeiten

(zum Seitenanfang)

ZentrumBearbeiten

Das Zentrum   eines Graphen   ist die Menge der Knoten von  , deren Exzentrizität dem Radius von   entspricht
Siehe auch: Durchmesser.

ZuordnungBearbeiten

Siehe Paarung.

Zusammenhängender GraphBearbeiten

Ein zusammenhängender Graph ist ein Graph, der nur aus einer Zusammenhangskomponente besteht.

ZusammenhangskomponenteBearbeiten

Eine Zusammenhangskomponente eines ungerichteten Graphen ist eine maximale Teilmenge seiner Knoten, in der zwischen je zwei beliebigen Knoten dieser Menge mindestens ein Weg existiert. Die Anzahl der Zusammenhangskomponenten eines Graphen   wird mit   bezeichnet.

ZusammenhangszahlBearbeiten

Siehe: Knotenzusammenhangszahl.

Zyklischer GraphBearbeiten

Ein zyklischer Graph ist ein gerichteter Graph, der mindestens einen Zyklus enthält.

Zyklomatische ZahlBearbeiten

Siehe: Index.

ZyklusBearbeiten

Ein Zyklus in einem Graphen ist ein Weg, der im selben Knoten beginnt und endet.
Eine Kante liegt genau dann auf einem Zyklus, wenn sie keine Brücke ist.
Siehe auch: w:Wege, Pfade, Zyklen und Kreise in Graphen.

ZyklenraumBearbeiten

Ist der Vektorraum aller durch (gewichtete) Kreise beschriebenen Inzidenzvektoren. Er ist ein w:Untervektorraum des  . In direkter Summe mit dem Kozyklenraum gibt er den ganzen Raum. Die Fundamentalkreise sind eine Basis.

Siehe auchBearbeiten