Mathematik-Glossar: Graphentheorie

Aus Wikibooks


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


A[Bearbeiten]

Abstand[Bearbeiten]

Siehe: Distanz.

Achromatische Zahl[Bearbeiten]

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.

Adjazenz[Bearbeiten]

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.

Adjazenzliste[Bearbeiten]

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.

Adjazenzmatrix[Bearbeiten]

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.

Adjazenzraum[Bearbeiten]

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 Pfad[Bearbeiten]

Siehe: Verbesserungspfad.

Artikulation[Bearbeiten]

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 Teilgraph[Bearbeiten]

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

Augmentierender Pfad[Bearbeiten]

Siehe: Verbesserungspfad.

Ausgangsgrad[Bearbeiten]

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.

Ausgangsmenge[Bearbeiten]

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

Automorphismus[Bearbeiten]

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 Graph[Bearbeiten]

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

B[Bearbeiten]

(zum Seitenanfang)

Bandbreite[Bearbeiten]

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.

Baum[Bearbeiten]

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.

Baumkante[Bearbeiten]

Siehe: Vorwärtskante.

Binärbaum[Bearbeiten]

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.

Bipartition[Bearbeiten]

Eine Bipartition ist eine 2-Partition.

Bipartiter Graph[Bearbeiten]

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.

Blatt[Bearbeiten]

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.

Block[Bearbeiten]

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.

Blockgraph[Bearbeiten]

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 .

Bogen[Bearbeiten]

Siehe: Gerichtete Kante.

Brücke[Bearbeiten]

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.

C[Bearbeiten]

(zum Seitenanfang)

Chordaler Graph[Bearbeiten]

Siehe: Triangulierter Graph.

Chromatische Zahl[Bearbeiten]

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 Index[Bearbeiten]

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.

Clique[Bearbeiten]

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-Graph[Bearbeiten]

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.

Cliquenproblem[Bearbeiten]

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.

Cliquenzahl[Bearbeiten]

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

D[Bearbeiten]

(zum Seitenanfang)

Dichte[Bearbeiten]

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

Digraph[Bearbeiten]

Siehe: gerichteter Graph.

Dilation[Bearbeiten]

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 Nachfolger[Bearbeiten]

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änger[Bearbeiten]

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 Wege[Bearbeiten]

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.

Distanz[Bearbeiten]

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.

Distanzgraph[Bearbeiten]

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.

Dominationszahl[Bearbeiten]

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

Dominierende Menge[Bearbeiten]

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.

Dreieck[Bearbeiten]

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

Dreiecksfreier Graph[Bearbeiten]

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

Dualer Graph[Bearbeiten]

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.

Durchmesser[Bearbeiten]

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.

E[Bearbeiten]

(zum Seitenanfang)

Ecke[Bearbeiten]

Siehe: Knoten.

Einbettung[Bearbeiten]

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

Einfacher Graph[Bearbeiten]

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 Kreis[Bearbeiten]

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

Einfacher Pfad[Bearbeiten]

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

Eingangsgrad[Bearbeiten]

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.

Eingangsmenge[Bearbeiten]

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

Endknoten einer Kante[Bearbeiten]

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

Erreichbarkeitsmatrix[Bearbeiten]

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-Problem[Bearbeiten]

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.

Eulerkreis[Bearbeiten]

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 Graph[Bearbeiten]

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.

Eulertour[Bearbeiten]

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

Eulerweg[Bearbeiten]

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

Eulerzug[Bearbeiten]

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ät[Bearbeiten]

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.

F[Bearbeiten]

(zum Seitenanfang)

Färbung[Bearbeiten]

Siehe: Knotenfärbung, Kantenfärbung.

Färbungszahl[Bearbeiten]

Siehe: Chromatische Zahl.

Faktor[Bearbeiten]

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.

Faktorisierung[Bearbeiten]

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-kritisch[Bearbeiten]

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

Farbzahl[Bearbeiten]

Siehe: Chromatische Zahl.

Fläche[Bearbeiten]

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.

Fluss[Bearbeiten]

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.

Fundamentalkreis[Bearbeiten]

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

Fundamentalschnitt[Bearbeiten]

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

G[Bearbeiten]

(zum Seitenanfang)

Geordneter Baum[Bearbeiten]

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 Graph[Bearbeiten]

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

Gerichtete Kante[Bearbeiten]

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 Kreis[Bearbeiten]

Siehe: Gerichteter Zyklus.

Gerüst[Bearbeiten]

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.

Gewicht[Bearbeiten]

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

Grad[Bearbeiten]

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.

Gradfolge[Bearbeiten]

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.

Graph[Bearbeiten]

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.

Graphisch[Bearbeiten]

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

Graph mit Mehrfachkanten[Bearbeiten]

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 Clique[Bearbeiten]

Siehe: Maximale Clique.

Größte Paarung[Bearbeiten]

Siehe: Maximale Paarung.


Größtes Matching[Bearbeiten]

Siehe: Maximale Paarung.

Großvater[Bearbeiten]

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

Gültige Färbung[Bearbeiten]

Siehe: Gültige Knotenfärbung.

Gültige Kantenfärbung[Bearbeiten]

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

Gültige Knotenfärbung[Bearbeiten]

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

H[Bearbeiten]

(zum Seitenanfang)

Halbblatt[Bearbeiten]

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.

Hamiltonabschluss[Bearbeiten]

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 Graph[Bearbeiten]

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

Hamiltonkreis[Bearbeiten]

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

Hamiltonkreis Problem[Bearbeiten]

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

Hamiltonpfad[Bearbeiten]

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

Handschlag-Lemma[Bearbeiten]

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.

Heiratssatz[Bearbeiten]

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öhe[Bearbeiten]

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öomorphie[Bearbeiten]

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-Ursprung[Bearbeiten]

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.

Hypergraph[Bearbeiten]

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.

Hyperkante[Bearbeiten]

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

Hypohamiltonsch[Bearbeiten]

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.

I[Bearbeiten]

(zum Seitenanfang)

Index[Bearbeiten]

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 Teilgraph[Bearbeiten]

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 Knoten[Bearbeiten]

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.

Inzidenz[Bearbeiten]

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

Inzidenzmatrix[Bearbeiten]

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

Inzidenzrelation[Bearbeiten]

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.

Inzidenzvektor[Bearbeiten]

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 Knoten[Bearbeiten]

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

Isomorphie[Bearbeiten]

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

J[Bearbeiten]

(zum Seitenanfang)

Jordankurve[Bearbeiten]

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.

K[Bearbeiten]

(zum Seitenanfang)

k-Baum[Bearbeiten]

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.

Kaktusgraph[Bearbeiten]

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.

Kante[Bearbeiten]

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 Graph[Bearbeiten]

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ärbung[Bearbeiten]

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 Wege[Bearbeiten]

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ärbungszahl[Bearbeiten]

Siehe: Chromatischer Index.

Kantenfeld[Bearbeiten]

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 .

Kantengraph[Bearbeiten]

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.

Kantenkontraktion[Bearbeiten]

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 Graphen[Bearbeiten]

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überdeckung[Bearbeiten]

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-Unterteilung[Bearbeiten]

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.

Kantenzusammenhangszahl[Bearbeiten]

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

Kern[Bearbeiten]

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

Kind[Bearbeiten]

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

Knoten[Bearbeiten]

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 Wege[Bearbeiten]

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ärbung[Bearbeiten]

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ärbungszahl[Bearbeiten]

Siehe: Chromatische Zahl.

Knotenfeld[Bearbeiten]

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 Graphen[Bearbeiten]

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überdeckung[Bearbeiten]

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überdeckungszahl[Bearbeiten]

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.

Knotenzusammenhangszahl[Bearbeiten]

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.

Komplement[Bearbeiten]

Siehe: Komplementärer Graph.

Komplementärer Graph[Bearbeiten]

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.

Komplementgraph[Bearbeiten]

Siehe: Komplementärer Graph.

Kozyklenraum[Bearbeiten]

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

Kreis[Bearbeiten]

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 Wege[Bearbeiten]

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

Kubischer Graph[Bearbeiten]

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

L[Bearbeiten]

(zum Seitenanfang)

Länge eines Kreises[Bearbeiten]

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

Länge eines Pfades[Bearbeiten]

Siehe: Länge eines Weges.

Länge eines Weges[Bearbeiten]

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

Länge eines Zyklus[Bearbeiten]

Siehe: Länge eines Kreises.

Linegraph[Bearbeiten]

Siehe: Kantengraph.

M[Bearbeiten]

(zum Seitenanfang)

Matching[Bearbeiten]

Siehe: Paarung.

Matchingzahl[Bearbeiten]

Siehe: Paarungszahl.

Maximale Clique[Bearbeiten]

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 Paarung[Bearbeiten]

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 Matching[Bearbeiten]

Siehe: Maximale Paarung.

Maximalgrad[Bearbeiten]

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.

Mehrfachkante[Bearbeiten]

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.

Mehrfachschleife[Bearbeiten]

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

Metrischer Graph[Bearbeiten]

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-Problem[Bearbeiten]

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.

Minimalgrad[Bearbeiten]

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.

Minor[Bearbeiten]

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

Multigraph[Bearbeiten]

Mit Multigraph bezeichnet man einen Graphen mit Mehrfachkanten

Multikante[Bearbeiten]

Siehe: Mehrfachkante.

N[Bearbeiten]

(zum Seitenanfang)

Nachbar[Bearbeiten]

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 .

Nachbarschaft[Bearbeiten]

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

Nachbarschaftsliste[Bearbeiten]

Siehe: Adjazenzliste.

Nachbarschaftsmatrix[Bearbeiten]

Siehe: Adjazenzmatrix.

Nachfolger[Bearbeiten]

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

Nachfolgermenge[Bearbeiten]

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)

Netzwerk[Bearbeiten]

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.

O[Bearbeiten]

(zum Seitenanfang)

Obergraph[Bearbeiten]

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

Onkel[Bearbeiten]

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 Baumes[Bearbeiten]

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

P[Bearbeiten]

(zum Seitenanfang)

Paarer Graph[Bearbeiten]

Siehe: Bipartiter Graph.

Paarung[Bearbeiten]

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.

Paarungszahl[Bearbeiten]

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

Panzyklische Graphen[Bearbeiten]

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 Kanten[Bearbeiten]

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

Partieller k-Baum[Bearbeiten]

Siehe: k-Baum.

Partition[Bearbeiten]

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 Eliminationsordnung[Bearbeiten]

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 Paarung[Bearbeiten]

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

Perfektes Matching[Bearbeiten]

Siehe: Perfekte Paarung.

Pfad[Bearbeiten]

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 Graph[Bearbeiten]

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 Zahl[Bearbeiten]

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.

Q[Bearbeiten]

(zum Seitenanfang)

Quelle[Bearbeiten]

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.

R[Bearbeiten]

(zum Seitenanfang)

Rand[Bearbeiten]

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

Regulärer Graph[Bearbeiten]

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.

Radius[Bearbeiten]

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ärtskante[Bearbeiten]

Siehe: Vorwärtskante.

S[Bearbeiten]

(zum Seitenanfang)

Satz von Hall[Bearbeiten]

Siehe: Heiratssatz.

Schleife[Bearbeiten]

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 Graph[Bearbeiten]

Siehe: Schleifenloser Graph.

Schleifenloser Graph[Bearbeiten]

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

Schlinge[Bearbeiten]

Siehe: Schleife.

Schnitt[Bearbeiten]

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.

Schnittknoten[Bearbeiten]

Siehe: Artikulation.

Schwache Zusammenhangskomponente[Bearbeiten]

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

Sehne[Bearbeiten]

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

Semieulerscher Graph[Bearbeiten]

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 Graph[Bearbeiten]

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.

Senke[Bearbeiten]

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.

Separator[Bearbeiten]

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 Knoten[Bearbeiten]

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

Sohn[Bearbeiten]

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

Spannbaum[Bearbeiten]

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.

Spanner[Bearbeiten]

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.

Spannwald[Bearbeiten]

Siehe Gerüst.

Stabile Menge[Bearbeiten]

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ätszahl[Bearbeiten]

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 Graph[Bearbeiten]

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

Starke Zusammenhangskomponente[Bearbeiten]

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 Kante[Bearbeiten]

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

Stern[Bearbeiten]

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

Subgraph[Bearbeiten]

Siehe: Teilgraph.

Symmetrischer Graph[Bearbeiten]

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.

T[Bearbeiten]

(zum Seitenanfang)

Taillenweite[Bearbeiten]

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 .

Teilgraph[Bearbeiten]

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.

Tiefe[Bearbeiten]

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 Ordnung[Bearbeiten]

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 Sortierung[Bearbeiten]

Siehe: Topologische Ordnung bzw. w:Topologische Sortierung.

Travelling Salesman Problem[Bearbeiten]

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 Graph[Bearbeiten]

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 Partition[Bearbeiten]

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

Trivialer Kreis[Bearbeiten]

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

Trivialer Zyklus[Bearbeiten]

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

Turniergraph[Bearbeiten]

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

U[Bearbeiten]

(zum Seitenanfang)

Umfang[Bearbeiten]

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

Unabhängige Knotenmenge[Bearbeiten]

Siehe: Stabile Menge.

Unabhängige Kantenmenge[Bearbeiten]

Siehe Paarung.

Unabhängige Menge[Bearbeiten]

Siehe: Stabile Menge.

Unabhängigkeitszahl[Bearbeiten]

Siehe: Stabilitätszahl.

Unendlicher Graph[Bearbeiten]

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

Ungerichtete Kante[Bearbeiten]

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 Graph[Bearbeiten]

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

Uniformer Hypergraph[Bearbeiten]

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

Universaler Knoten[Bearbeiten]

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

Unterbaum[Bearbeiten]

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

Untergraph[Bearbeiten]

Siehe: Teilgraph.

Unterteilungsgraph[Bearbeiten]

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

Unzusammenhängender Graph[Bearbeiten]

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

V[Bearbeiten]

(zum Seitenanfang)

Valenz[Bearbeiten]

Siehe: Grad.

Valenzsequenz[Bearbeiten]

Siehe: Gradfolge.

Vater[Bearbeiten]

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

Verbesserungspfad[Bearbeiten]

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.

Vergleichbarkeitsgraph[Bearbeiten]

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ärbung[Bearbeiten]

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 Zuordnung[Bearbeiten]

Siehe: Perfekte Paarung.

Vollständiger Graph[Bearbeiten]

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änger[Bearbeiten]

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

Vorgängermenge[Bearbeiten]

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ärtskante[Bearbeiten]

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.

W[Bearbeiten]

(zum Seitenanfang)

Wald[Bearbeiten]

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

Weg[Bearbeiten]

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überdeckung[Bearbeiten]

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

Wurzel[Bearbeiten]

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

Wurzelbaum[Bearbeiten]

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.

X[Bearbeiten]

(zum Seitenanfang)

Y[Bearbeiten]

(zum Seitenanfang)

Z[Bearbeiten]

(zum Seitenanfang)

Zentrum[Bearbeiten]

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

Zuordnung[Bearbeiten]

Siehe Paarung.

Zusammenhängender Graph[Bearbeiten]

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

Zusammenhangskomponente[Bearbeiten]

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.

Zusammenhangszahl[Bearbeiten]

Siehe: Knotenzusammenhangszahl.

Zyklischer Graph[Bearbeiten]

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

Zyklomatische Zahl[Bearbeiten]

Siehe: Index.

Zyklus[Bearbeiten]

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.

Zyklenraum[Bearbeiten]

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 auch[Bearbeiten]