Färbungszahl

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

A

Abstand

Siehe: Distanz.

Achromatische Zahl

Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G eine gültige und vollständige Knotenfärbung mit k Farben hat.

Siehe auch: chromatische Zahl, pseudo-achromatische Zahl.

Adjazenz

Adjazenz bezeichnet eine Beziehung zwischen Knoten oder Kanten in einem ungerichteten 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, Nachbarschaft und Grad in Graphen.

Adjazenzliste

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

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

Adjazenzraum

Der Adjazenzraum eines Graphen ist der Vektorraum, der von den Spalten der Adjazenzmatrix aufgespannt wird.

Die Adjazenzräume von isomorphen Graphen sind isomorphe Räume

Alternierender Pfad

Siehe: Verbesserungsweg.

Artikulation

Eine trennende Knotenmenge, die aus einem Knoten besteht, wird Artikulation genannt.

Augmentierender Pfad

Siehe: Verbesserungsweg.

Ausgangsgrad

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, Nachbarschaft und Grad in Graphen.

Ausgangsmenge

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

Automorphismus

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

Azyklischer Graph

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

B

(zum Seitenanfang)

Bandbreite

Die Bandbreite (engl. bandwidth, siehe auch Bandbreite) eines endlichen, schlichten, ungerichteten Graphen is wie folgt definiert: Sei $L: V \to\{1,\ldots,n\}$ eine eineindeutige Nummerierung der Knoten. Dann bezeichnet $\max_{\{i,j\}\in E} |L(i)-L(j)|$ die Bandbreite bezüglich L und $\min_L \max_{\{i,j\}\in E} |L(i)-L(j)|$ die Bandbreite des Graphen (V,E).

Die Ermittlung der Bandweite ist eines der wenigen Probleme, das auch für Bäume NP-vollständig ist.

Baum

Ein Baum ist ein zusammenhängender Graph, der keine Zyklen enthält. Genauer: G 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.

Hauptartikel: Baum.

Baumkante

Siehe: Vorwärtskante.

Bipartition

Eine Bipartition ist eine 2-Partition.

Bipartiter Graph

Ein bipartiter Graph ist ein einfacher Graph, der eine Bipartition besitzt.

Nach Dénes Kőnig ist ein Graph genau dann bipartit, wenn er keinen Kreis ungerader Länge besitzt.

Hauptartikel: Bipartiter Graph, vollständig bipartiter Graph.

Siehe auch: Satz von König, Wege, Pfade, Zyklen und Kreise in Graphen.

Blatt

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.

Block

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

Blockgraph

Ein Blockgraph block(G) zu einem Graphen G erfüllt die folgenden Eigenschaften:

• Für jeden Schnittknoten in G gibt es genau einen Knoten in block(G).
• Für jeden Block in G gibt es genau einen Knoten in block(G).
• Kanten verlaufen zwischen Schnittknoten und Blockknoten genau dann, wenn der Block den Schnittknoten enthält.
• Es gibt keine weiteren Knoten und Kanten in block(G).

Bogen

Siehe: Gerichtete Kante.

Brücke

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

C

(zum Seitenanfang)

Chordaler Graph

Siehe: Triangulierter Graph.

Chromatische Zahl

Die chromatische Zahl (auch Knotenfärbungszahl oder kurz Färbungszahl, selten auch Farbzahl genannt) eines Graphen ist die kleinste Zahl k, für die der Graph eine zulässige Knotenfärbung mit k Farben besitzt.

Siehe auch: Partition, Färbung, achromatische Zahl, pseudo-achromatische Zahl.

Chromatischer Index

Der chromatische Index (auch Kantenfärbungszahl) eines Graphen ist die kleinste Zahl k, für die der Graph eine zulässige Kantenfärbung mit k Farben besitzt. Das ist gleichzeitig auch die kleinste natürliche Zahl, für die das Chromatische Polynom $\chi(G,\lambda)\neq 0$ ist.

Siehe auch: Färbung.

Clique

Eine Clique ist in einem ungerichteten Graph eine Teilmenge der Knoten, innerhalb derer alle Knoten paarweise mit einer Kante verbunden sind.

Siehe auch: Knotenüberdeckungen, Cliquen und stabile Mengen.

Cliquenproblem

Das Cliquenproblem fragt, zu einem gegebenen ungerichteten Graph G und einer natürlichen Zahl k, ob die Cliquenzahl von G mindestens so groß wie k ist.

Siehe auch: Knotenüberdeckungen, Cliquen und stabile Mengen.

Cliquenzahl

Die Cliquenzahl ω(G) eines ungerichteten Graphen G ist die größte Zahl k, für die G eine Clique der Größe k besitzt.

Siehe auch: Cliquenproblem.

D

(zum Seitenanfang)

Dichte

Die Dichte dn(G) eines einfachen Graphen G = (V,E) ist das Verhältnis seiner Kantenzahl zur Kantenzahl eines vollständigen Graphen auf gleichvielen Knoten, das heißt:

$dn(G)=\frac{2|E|}{|V|(|V|-1)}.$

Digraph

Siehe: gerichteter Graph.

Dilation

Die Diolation 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

In einem gerichteten Graph heißt ein Knoten v direkter Nachfolger eines Knoten u falls es eine Kante gibt, welche von u nach v geht.

Direkter Vorgänger

In einem gerichteten Graphen heißt ein Knoten u direkter Vorgänger eines Knoten v falls es genau eine Kante u,v gibt, die nach v geht.

Disjunkte Wege

Zwei Wege $v=(v_1, v_2, \ldots, v_p)$ und $w=(w_1, w_2, \ldots, w_q)$ heißen disjunkt, falls alle Knoten aus v verschieden von denen aus w. Häufig lässt man zu, dass v₁ = w₁ und v_p = w_q, 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 x,y von Knoten p disjunkte Wege von x nach y, so nennt man den Graphen p-fach knotenzusammenhängend.

Distanz

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

Siehe auch: Distanzgraph.

Distanzgraph

Als Distanzgraph D_G eines Graphen G = (V,E) bezeichnet man den vollständigen kantengewichteten Graphen über V, der jeder Kante die Distanz der zugehörigen Knoten in G zuordnet.

Siehe auch: Distanzgraph.

Dominationszahl

Die Dominationszahl γ(G) ist die Mächtigkeit einer kleinsten dominierenden Knotenmenge von G.

Dominierende Knotenmenge

Eine Knotenteilmenge $X\subseteq V$ eines Graphen G = (V,E) heißt dominierend, wenn jeder Knoten aus $V\setminus X$ zu einem Knoten aus X adjazent ist.

Dreieck

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

Dreiecksfreier Graph

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

Dualer Graph

Sei G = (V,E) ein planerer Graph mit einer gegebenen planaren Einbettung. Der duale Graph $G^*=(V^*, E^*)\!$ entsteht aus G, indem jeder Fläche von G ein Knoten von G ^* zugeordnet wird. Zwei Knoten aus G ^* werden durch k Kanten verbunden, wenn die entsprechenden Flächen aus G genau k gemeinsame Randkanten besitzen.

Bemerkung: Für zusammenhängende G gilt: G * * = G, das heißt: Der duale Graph des dualen Graphen ist der Graph selbst.

Durchmesser

Der Durchmesser D(G) eines Graphen G ist das Maximum der Exzentrizitäten der Knoten von G

Für alle Graphen G gilt $R(G)\le D(G) \le 2 \cdot R(G)$, wobei R(G) der Radius von G ist.

Siehe auch: Zentrum.

E

(zum Seitenanfang)

Ecke

Siehe: Knoten.

Einbettung

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

Einfacher Graph

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

Ein einfacher Kreis in einem schlichten, ungerichteten Graphen G = (V,E) ist ein Kreis, der jeden Knoten $v \in V$ genau ein Mal enthält.

Einfacher Pfad

Ein einfacher Pfad in einem schlichten, ungerichteten Graphen G = (V,E) ist ein Pfad, der jeden Knoten $v \in V$ genau ein Mal enthält.

Eingangsgrad

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, Nachbarschaft und Grad in Graphen.

Eingangsmenge

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

Endknoten einer Kante

Ist k = (x,y) eine gerichtete Kante, so bezeichnet man x als ihren Startknoten und y als ihren Endknoten.

Bei ungerichteten Kanten k = {x,y} kann man x und y sowohl als Startknoten als auch als Endknoten bezeichnen. Hier spricht man in der Regel aber einfach von den beiden „zu k inzidenten Knoten“.

Erreichbarkeitsmatrix

Die Erreichbarkeitsmatrix ist eine binäre Matrix und gibt im n-ten Schritt die gesamte Erreichbarkeit der Knoten untereinander an.

Der 1. Schritt entsteht durch die Addition der 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

Das Euklidische Travelling Salesman Problem ist das Travelling Salesman Problem für einen kantenbewerteten Graphen, in dem die Dreiecksungleichung gilt.

Siehe auch: Problem des Handlungsreisenden.

Eulerkreis

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

Ein eulerscher Graph ist ein Graph, in dem ein Zyklus existiert, der jede Kante genau einmal enthält.

• 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 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: Eulerkreisproblem.

Eulertour

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

Eulerweg

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

Eulerzug

Ein geschlossener 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

Die Exzentrizität e(x) eines Knotens x ist die Distanz (die Länge eines kürzesten Weges) zu einem Knoten y, welcher maximalen Abstand von x hat.

Beachte: Hier wird das Maximum von minimalen Weglängen betrachtet

Siehe auch: Radius, Durchmesser, Zentrum.

F

(zum Seitenanfang)

Färbung

Siehe: Knotenfärbung, Kantenfärbung.

Färbungszahl

Siehe: Chromatische Zahl.

Faktor

Ist G = (V,E) ein Graph und g eine Abbildung der Knoten auf natürliche Zahlen, so ist ein g-Faktor F ein Teilgraph von G, mit V(F) = V(G) (also nur Kanten werden entfernt) und jeder Knoten x hat in F den Grad g(x).

Ist g(x) = p für alle Knoten x, so spricht man auch von einem p-Faktor.

Ist $g(x) \ge a$ und $g(x) \le b$ für alle Knoten x, so spricht man von einem [a,b]-Faktor.

• Eine Paarung ist ein [0,1]-Faktor; Eine perfekte Paarung ist ein 1-Faktor; Hamiltonsche Graphen besitzen einen 2-Faktor.
• Der 1-Faktorsatz von Tutte besagt, dass man aus G und g einen Graphen G ^* konstruieren kann, welcher genau dann einen 1-Faktor besitzt, wenn G einen g-Faktor besitzt. Dies ist die Definition einer Reduktion im Sinne der theoretischen Informatik. Da umgekehrt 1-Faktoren Spezialfälle von g-Faktoren sind, ist das g-Faktorproblem äquivalent zum 1-Faktorproblem.

Faktor-kritisch

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

Farbzahl

Siehe: Chromatische Zahl.

Fläche

Fläche eines planaren Graphen nennt man das Gebiet der Ebene (oder einer Fläche im $\mathbb{R}^3$), welches durch Kanten eines planaren Graphen, der in der Ebene (bzw. auf der Fläche) eingebettet ist, berandet wird.

Fluss

Ein Fluss ist in einem Netzwerk eine Funktion f von den gerichteten Kanten auf die reellen Zahlen.

Ein Fluss darf den Kanten nur positive Werte zuweisen, die höchstens so groß sein dürfen, wie die Kapazität der Kante.

Ferner muss für jeden Knoten x (außer für die Quelle q und die Senke s) gelten, dass die Summe der Flüsse aus den negativ inzidenten Kanten gleich der Summe der Flüsse in die positiv inzidenten Kanten ist.

Formal: $\forall x\in V\setminus \{ q,s \} : \sum_{y\in N^-(x)}f((y,x)) = \sum_{y\in N^+(x)}f((x,y))$

Anschaulich: aus keinem Knoten kann mehr herausfließen als hineinfließt und alles, was in einen Knoten hineinfließt, fließt auch wieder heraus.

G

(zum Seitenanfang)

Geordneter Baum

Ein geordneter Baum ist ein Wurzelbaum, in dem für die Söhne jedes Knotens eine 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

Ein Gerichteter Graph (auch Digraph genannt) ist ein Graph, der gerichtete Kanten enthält.

Siehe auch: Typen von Graphen in der Graphentheorie.

Gerichtete Kante

Eine gerichtete Kante, auch Bogen oder Pfeil genannt, verbindet zwei Knoten eines Graphen unter Beachtung einer Reihenfolge. Eine gerichtete Kante wird daher als geordnetes Paar zweier Knoten notiert.

Siehe auch: Ungerichtete Kante, Typen von Graphen in der Graphentheorie.

Gerichteter Kreis

Siehe: Gerichteter Zyklus.

Gerüst

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

Gewicht

Das Gewicht ist eine reelle Zahl, die einem Knoten oder einer Kante zugeordnet wird.

Siehe auch: Gewicht, Knotengewicht, Kantengewicht.

Grad

Der Grad eines Knotens in einem ungerichteten Graphen (auch Valenz genannt) ist die Anzahl seiner Nachbarn.

Siehe auch: Eingangsgrad, Ausgangsgrad, Nachbarschaft und Grad in Graphen.

Gradfolge

Als Gradfolge eines Graphen G = (V,E) mit den Knoten $v_1, v_2, \ldots, v_n \in V$ bezeichnet man die Folge natürlicher Zahlen $d_1, d_2, \ldots, d_n$, welche jeweils den Grad der einzelnen Knoten angeben, d. h. deg(v_i) = d_i für alle $i = 1, 2, \dots, n$. Eine solche Folge natürlicher Zahlen heißt auch graphisch, wenn tatsächlich mindestens ein Graph existiert, der diese Gradfolge aufweist.

Graph

Ein Graph ist ein Tupel (V,E). V ist eine nichtleere Menge von Knoten, E 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: Typen von Graphen in der Graphentheorie, Hypergraph.

Graphisch

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

Graph mit Mehrfachkanten

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

Siehe: Maximale Clique.

Größte Paarung

Siehe: Maximale Paarung.

Größtes Matching

Siehe: Maximale Paarung.

Großvater

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

Gültige Färbung

Siehe: Gültige Knotenfärbung.

Gültige Kantenfärbung

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

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

H

(zum Seitenanfang)

Hamiltonabschluss

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

Hamiltonscher Graph

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

Hamiltonkreis

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

Hamiltonkreis Problem

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 Hamiltonkreisproblem

Hamiltonpfad

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

Handschlag-Lemma

Das Handschlag-Lemma besagt, dass die Summe der Knotengrade gleich $2 \cdot |E(G)|$ 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

In bipartiten Graphen G mit Bipartition {A,B} existiert genau dann eine Paarung M der Kardinalität | M | = | A | (die jeden Knoten aus A überdeckt), falls für jede Teilmenge S von A gilt, dass ihre Nachbarschaft mindestens so groß ist wie S selbst:

$|N(S)| \ge |S|,\ \forall S\subseteq A$

Siehe auch: Paarung.

Höhe

Die Höhe eines Wurzelbaums ist die maximal auftretende Tiefe.

Homöomorphie

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: Planarer Graph.

Homöomorphie-Ursprung

Der Homöomorphie-Ursprung HU(G) eines Graphen G = (V,E) ist der kleinste Graph, zu dem G homöomorph ist. Man berechnet HU(G) mit dem folgenden Algorithmus:

1. Falls G keinen Knoten vom Grad 2 besitzt (abgesehen von isolierten Knoten die nur eine Schleife besitzen) so ist HU(G) = G.
2. Wähle einen Knoten x vom Grad 2 (außer isolierte Knoten mit einer Schleife) mit den beiden Nachbarn y und z (auch y = z ist möglich)
3. Entferne x, füge dafür eine Kante von y nach z ein.
   Formal: $G \leftarrow (V\setminus \{x\},E\cup \{\{y,z\}\})$
4. gehe zu 1

Siehe auch: Planarer Graph.

Hypergraph

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

Siehe auch: Typen von Graphen in der Graphentheorie.

Hyperkante

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

Siehe auch: Typen von Graphen in der Graphentheorie.

Hypohamiltonsch

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

I

(zum Seitenanfang)

Index

Der Index eines Graphen ist definiert als:

μ(G): = | E(G) | − | K(G) | + κ(G) (Anzahl der Kanten − Anzahl der Knoten + Anzahl der Zusammenhangskomponenten)

• Für alle Graphen G ist $\mu (G) \ge 0$ und G ist genau dann ein Wald, wenn μ(G) = 0 gilt
• Der Index eines Graphen G ist stets kleinergleich der Anzahl seiner Kreise und G ist genau dann ein Kaktusgraph, wenn sein Index der Anzahl der Kreise in G entspricht

Induzierter Teilgraph

Ist G ein Graph und $I\subseteq V(G)$ Teilmenge der Knotenmenge von G, so ist der von I induzierte Teilgraph ein Teilgraph, der durch Entfernung der Knoten aus G entsteht, die nicht in I liegen (bemerke: bei Entfernen eines Knotens k fallen auch alle mit k inzidenten Kanten weg).

Anschaulich bedeutet das: Der von I induzierte Teilgraph besteht aus den Knoten aus I und allen Kanten, die in G zwischen ihnen verlaufen.

Formal: der von I induzierte Teilgraph ist $G-(V(G)\setminus I)$

Innerer Knoten

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

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: Adjazenz, Inzidenzmatrix, Nachbarschaft und Grad in Graphen.

Inzidenzmatrix

Eine Inzidenzmatrix zu einem Graph mit n Knoten und m Kanten ist eine $n \times m$-Matrix, bei der die Zeilen mit den Knoten und die Spalten mit den Kanten identifiziert werden. Dazu nummeriert man die Knoten von 1 bis n und die Kanten von 1 bis m 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: Repräsentation von Graphen im Computer.

Inzidenzrelation

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 G = (V,E) mit $e \in E := \{u, v\}$ mit $u, v \in V$ nicht aus, denn hier müssten z. B. in E Duplikate erlaubt sein. Man führt daher eine Inzidenzrelation ein und benennt die Elemente aus E mit einem eindeutigen Namen $e \in E$, 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 $I \subseteq V \times E$, d. h. zu jedem Knoten wird für jede Kante, die ihn berührt, ein Element {v,e} mit $v \in V$ und $e \in E$ in I aufgenommen. Schlingen werden somit über jeweils ein Element der Inzidenzrelation, zwei parallele Kanten über vier Elemente der Inzidenzrelation eindeutig repräsentiert.

Isolierter Knoten

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

Isomorphie

Zwei Graphen G = (V,E) und H = (V',E') heißen isomorph, falls eine bijektive Abbildung $\varphi :V\rightarrow V'$ existiert, sodass für alle $x,y \in V$ gilt: $xy \in E$ genau dann, wenn $\varphi (x)\varphi (y)\in E'$

J

(zum Seitenanfang)

Jordankurve

Eine Jordankurve ist eine stetige und schnittpunktfreie Kurve mit Anfangs- und Endpunkt. Die Kanten eines planaren Graphen sind nicht-selbstschneidende Jordankurven zwischen seinen Endpunkten.

K

(zum Seitenanfang)

k-Baum

Ein ungerichteter Graph heißt k-Baum, wenn er wie folgt rekursiv erzeugbar ist:

• Der vollständige Graph K_k ist ein k-Baum.
• Fügt man zu einem k-Baum G einen neuen Knoten v hinzu, indem man v mit allen Knoten einer Clique der Größe k aus G verbindet, so ist dieser neue Graph ebenfalls ein k-Baum.

Ein partieller k-Baum entsteht durch die Entfernung von Kanten aus einem k-Baum: Ist G = (V,E) k-Baum, so ist H = (V, F ⊂ E) ein partieller k-Baum.

Gelegentlich werden auch Bäume mit dem maximalen Grad k als k-Bäume bezeichnet. Korrekter ist in diesem Fall die Bezeichnung k-närer Baum.

Kaktusgraph

Ein Graph G heißt Kaktusgraph, wenn alle seine Kreise paarweise Kantendisjunkt sind (sich also höchstens gemeinsame Knoten teilen).

Ein Graph G ist ein Kaktusgraph genau dann, wenn die Anzahl seiner Kreise seinem Index μ(G) entspricht.

Kante

Eine Kante ist ein Element der Kantenmenge eines Graphen. Die Kantenmenge 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: Typen von Graphen in der Graphentheorie.

Vergleiche: Bogen bei Digraphen (gerichteten Graphen)

Kantenbewerteter Graph

Ein Kantenbewerteter Graph ist ein Graph G mit einer Kantenbewertung g, welche formal eine Abbildung der Kantenmenge auf die reellen Zahlen ist. Die Kantenbewertungsfunktion g bezeichnet man oft auch als Kostenfunktion oder Kantengewichtsfunktion.

Kantenbewertungen spielen häufig eine Rolle in 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

Ist G = (V,E) ein ungerichteter Graph ohne Mehrfachkanten und f eine Abbildung von E in die Menge der natürlichen Zahlen $\mathbb{N}_0$, so nennt man f eine Kantenfärbung von G.

Kantendisjunkte Wege

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

Siehe: Chromatischer Index.

Kantenfeld

Ein Kantenfeld ist eine Darstellungsart für gerichtete Graphen nach folgendem Schema:

$|V|, |E|, E_1,\ldots, E_{|E|}$

wobei | V | die Anzahl der Knoten, | E | die Anzahl der Kanten und $E_1, \ldots, E_{|E|}$ die Kanten sind mit $E_i = (v, w) \in E$.

Kantengraph

Der Kantengraph (engl. line graph) L(G) eines Graphen G entsteht folgendermaßen aus G:

• Für jede Kante k aus G setze einen Knoten k' in L(G).
• Füge eine Kante {k',l'} in L(G) genau dann ein, wenn die Kanten k und l in G einen gemeinsamen Endknoten haben.

Kantenkontraktion

Ist k eine Kante, die die Knoten x und y verbindet, dann ist die Kontraktion von k eine „Verschmelzung“ von x und y, d. h. x, y und k werden durch einen neuen Knoten z ersetzt, der mit allen Nachbarn von x und y verbunden wird.

Haben x und y einen gemeinsamen Nachbarn w, so verlaufen im resultierenden Graphen parallele Kanten zwischen z und w oder allgemeiner: wenn zwischen x und w n parallele Kanten und zwischen y und w m parallele Kanten verlaufen, so verlaufen nach der Kontraktion von k zwischen z und w genau m + n parallele Kanten.

Kantenpanzyklische Graphen

Ein Graph heißt kantenpanzyklisch falls jede Kante auf einem Kreis der Länge p liegt für alle $p \in \{1,2,\ldots,|V(G)|\}$. Kantenpanzyklische Graphen sind auch knotenpanzyklisch und damit auch panzyklisch.

Kantenüberdeckung

Eine Kantenüberdeckung in einem ungerichteten Graphen G = (V,E) ist eine Menge $E' \subseteq E$ mit der Eigenschaft, dass jeder Knoten von V in einer Kante aus E' enthalten ist.

E' ist Kantenüberdeckung in G gdw. $\forall v \in V, \exists w \in E': v \in w$.

Kanten-Unterteilung

Eine Unterteilung einer Kante ist das Einfügen eines Knotens in die Kante

Formal: Ist G = (V,E) ein Graph und $k=\{x, y\} \in E$, so entsteht G' durch Unterteilung von k als $G'=(V \cup \{z \notin V\}, E \setminus \{k\} \cup \{\{z,x\},\{z,y\}\})$. Die Voraussetzung $z\notin V$ ist für die formale Korrektheit notwendig.

Kantenzusammenhangszahl

Die Kantenzusammenhangszahl eines Graphen bezeichnet die Anzahl der Kanten, die man aus diesem entfernen muss, um den Zusammenhang aufzuheben.

Kind

Kind ist die Bezeichnung für einen direkten Nachfolger in einem Baum.

Knoten

Als Knoten oder Ecke bezeichnet man ein Element der Knotenmenge eines Graphen. Graphen bestehen neben der Knotenmenge noch aus einer speziellen Kantenmenge, die beschreibt, wie die Knoten über Kanten verbunden sind.

Siehe auch: Typen von Graphen in der Graphentheorie.

Knotendisjunkte Wege

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

Knotenfärbung

Eine p-Knotenfärbung ist eine Abbildung der Knotenmenge auf die Menge $\{1, \ldots, p\}$ (also wird jedem Knoten eine von p Zahlen oder „Farben“ zugewiesen).

Siehe auch: Gültige Knotenfärbung, Chromatische Zahl, Vier-Farben-Satz.

Knotenfärbungszahl

Siehe: Chromatische Zahl.

Knotenfeld

Ein Knotenfeld ist eine Darstellungsart für gerichtete Graphen mit folgendem Aufbau:

$|V|, |E|, \text{ag}(V_1), \text{Ziel}_1, \ldots, \text{Ziel}_{\text{ag}(V_1)}, \ldots, \text{ag}(V_{|V|}), \text{Ziel}_1, \ldots, \text{Ziel}_{\text{ag}(V_{|V|})}$

wobei | V | die Anzahl der Knoten, | E | die Anzahl der Kanten und ag(V) Ausgangsgrad des Knotens sind.

Knotenpanzyklische Graphen

Ein Graph G heißt knotenpanzyklisch, wenn jeder Knoten auf einem Kreis der Länge p liegt, für alle $p \in \{1,2,\ldots,|V(G)|\}$.

Kantenpanzyklische Graphen sind knotenpanzyklisch, knotenpanzyklische Graphen sind panzyklisch.

Knotenüberdeckung

Als Knotenüberdeckung in einem ungerichteten Graphen bezeichnet man eine Teilmenge U seiner Knoten, für die gilt, dass jede Kante wenigstens einen Knoten aus U enthält.

U ist Knotenüberdeckung in G gdw. $\forall e \in E, \exists v \in U: v \in e$.

Siehe auch: Knotenüberdeckungen, Cliquen und stabile Mengen.

Knotenüberdeckungszahl

Als Knotenüberdeckungszahl eines ungerichteten Graphen wird die kleinste Zahl k bezeichnet, für die eine Knotenüberdeckung der Größe k existiert.

Siehe auch: Knotenüberdeckungen, Cliquen und stabile Mengen.

Knotenzusammenhangszahl

Die Knotenzusammenhangszahl (oft kurz Zusammenhangszahl genannt) κ(G) eines Graphen G ist die kleinste Anzahl von Knoten, deren Entfernung den Zusammenhang zerstört.

Komplement

Siehe: Komplementärer Graph.

Komplementärer Graph

Der Komplementäre Graph $\overline{G}$ eines Graphen G hat die gleiche Knotenmenge wie G und in $\overline{G}$ sind zwei Knoten x und y genau dann Adjazent, wenn sie es in G nicht sind ($\overline{G}$ hat also genau die Kanten, die G nicht hat).

Als Selbstkomplementär bezeichnet man Graphen, die isomorph zu ihrem Komplementären Graphen sind.

Komplementgraph

Siehe: Komplementärer Graph.

Kreis

Ein Kreis $C=(v_1, v_2, \ldots, v_p, v_1)$ ist eine Folge von Knoten, die bis auf den ersten und letzten Knoten paarweise verschieden sind, wobei sowohl v_i und v_{i + 1} für alle $i=1, \ldots, p-1$ als auch v_p und v₁ 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 n) besteht bezeichnet man mit C_n.

Kreuzungsfreie Wege

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

Kubischer Graph

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

L

(zum Seitenanfang)

Länge eines Kreises

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

Länge eines Pfades

Siehe: Länge eines Weges.

Länge eines Weges

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

Länge eines Zyklus

Siehe: Länge eines Kreises.

Linegraph

Siehe: Kantengraph.

M

(zum Seitenanfang)

Matching

Siehe: Paarung.

Matchingzahl

Siehe: Paarungszahl.

Maximale Clique

Eine Maximale Clique C eines Graphen G ist ein Teilgraph von G, der ein vollständiger Graph ist, und der in keinem größeren Teilgraph von G enthalten ist, der auch ein vollständiger Graph ist.

Gibt es in G zudem keinen vollständigen Teilgraphen, der mehr Knoten als C enthält, so nennt man C größte Clique.

Maximale Paarung

Eine Paarung M ist eine maximale Paarung, wenn keine Paarung N mit | N | > | M | existiert.

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

Maximales Matching

Siehe: Maximale Paarung.

Maximalgrad

Der Maximalgrad Δ(G) eines Graphen G ist die größte Zahl m, für die in G ein Knoten vom Grad m existiert.

Entspricht der Maximalgrad dem Minimalgrad, so spricht man von einem regulären Graphen.

Mehrfachkante

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: Typen von Graphen in der Graphentheorie.

Mehrfachschleife

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

Metrischer Graph

Ein Metrischer Graph ist ein kantenbewerteter Graph, der die Dreiecksungleichung erfüllt, d. h. sind $a,b,c \in V(G)$, so gilt stets $d(a,c) \le d(a,b)+d(b,c)$, wobei d(a,b) die Bewertung der Kante {a,b}.

Intuitiv formuliert: der Weg von a über b nach c darf nicht kürzer sein, als der direkte Weg von a nach c.

Distanzgraphen sind stets Metrisch.

Metrisches Traveling-Salesman-Problem

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: Problem des Handlungsreisenden.

Minimalgrad

Der Minimalgrad δ(G) eines Graphen G ist die kleinste Zahl m, für die in G ein Knoten vom Grad m existiert.

Entspricht der Minimalgrad dem Maximalgrad, so spricht man von einem regulären Graphen.

Minor

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

Multigraph

Mit Multigraph bezeichnet man einen Graphen mit Mehrfachkanten

Multikante

Siehe: Mehrfachkante.

N

(zum Seitenanfang)

Nachbar

Ein Knoten x ist Nachbar eines Knotens y genau dann, wenn $\{x,y\}\in E(G)$ also wenn sie durch eine Kante verbunden sind.

Bei gerichteten Graphen unterscheidet man positive - und negative Nachbarn. Genau dann, wenn $(x,y)\in B(G)$ eine gerichtete Kante von x nach y führt, nennt man y positiven Nachbar von x und x negativen Nachbarn von y.

Nachbarschaft

Die Nachbarschaft N(v) eines Knotens v ist die Menge seiner Nachbarn.

Bei gerichteten Graphen unterscheidet man die positive Nachbarschaft N ⁺ (v) (die Menge der Knoten, zu denen eine gerichtete Kante von v aus führt) und die negative Nachbarschaft N ⁻ (v) (die Menge der Knoten, von denen aus eine gerichtete Kante zu v führt)

Die Abgeschlossene Nachbarschaft ist $N[v] = N(v)\cup \{v\}$ also nichts anderes als die Nachbarschaft von v, zu der v selbst hinzugefügt wurde. (analog sind $N^+[v]=N^+(v)\cup \{v\}$ und $N^-[v]=N^-(v)\cup \{v\}$ definiert)

Nachbarschaftsliste

Siehe: Adjazenzliste.

Nachbarschaftsmatrix

Siehe: Adjazenzmatrix.

Nachfolger

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

Nachfolgermenge

Die Menge aller Nachfolger eines Knoten v. Also alle in einem Graphen von v durch einen Pfad erreichbaren Knoten.

Formal: $\forall w: \exist (v,\ldots, w)$ mit $v,w \in V$ (siehe auch: Transitive Hülle)

Netzwerk

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 Fluss interessiert, den man mit dem Ford-Fulkerson Algorithmus (nach Lester Randolph Ford und Delbert Ray Fulkerson) berechnet.

O

(zum Seitenanfang)

Obergraph

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

Onkel

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

Ordnung eines Baumes

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

P

(zum Seitenanfang)

Paarer Graph

Siehe: Bipartiter Graph.

Paarung

Eine Paarung (auch Matching, Zuordnung oder unabhängige Kantenmenge) in einem ungerichteten Graphen G = (V,E) ist eine Menge $E' \subseteq E$ mit der Eigenschaft, dass keine zwei Kanten aus E' in G durch einen gemeinsamen Knoten verbunden sind:

E' ist unabhängig in G gdw. $\forall e,e' \in E',\ mit\ e \not= e': e \cap e' = \varnothing$.

Siehe auch: perfekte Paarung, maximale Paarung.

Paarungszahl

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

Panzyklische Graphen

Ein Graph heißt panzyklisch wenn er für alle $p \in \{1,2,\ldots,|V(G)|\}$ einen Kreis der Länge p besitzt.

Insbesondere sind panzyklische Graphen damit hamiltonsch.

Siehe auch: Knotenpanzyklische Graphen, Kantenpanzyklische Graphen.

Parallele Kanten

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

Partieller k-Baum

Siehe: k-Baum.

Partition

Sei G = (V,E) ein Graph. Eine Zerlegung (Partition) der Knotenmenge V in p disjunkte Teilmengen V₁...V_p heißt p-Partition, falls keine adjazenten Ecken in einem gemeinsamen V_i liegen. (Anschaulich heißt das: Alle Kanten verlaufen zwischen diesen Teilmengen, keine innerhalb einer der Teilmengen.)

• Besitzt ein Graph G eine p-Partition, so sagt man auch „G ist p-partit“ oder „G ist ein p-partiter Graph“.
• Die chromatische Zahl von G ist das kleinste p, sodass G eine p-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

Als perfekte Eliminationsordnung bezeichnet man eine Knotenreihenfolge $(v_1, v_2, \ldots, v_n), V = \{v_1, v_2, \ldots, v_n\}$ des Graphen G = (V,E), so dass für jeden Graphen mit der (durch Eliminierung der Knoten v₁ bis v_{i − 1}) eingeschränkten Knotenmenge $G_i = (\{v_i, \ldots, v_n\}, E_i)$ gilt: v_i ist simplizial in G_i. Jeder (in Bezug auf die gewählte Ordnung) „kleinste“ Knoten in G_i 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

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

Perfektes Matching

Siehe: Perfekte Paarung.

Pfad

Ein Pfad $P=(v_1, v_2, \ldots, v_p)$ ist eine Folge von Knoten, mit paarweise verschiedenen Knoten, wobei immer v_i und v_{i + 1} adjazent sein müssen für alle $i=1,\ldots,p-1$.

Enthält P alle Knoten von G, so nennt man P einen Hamiltonpfad.

Fordert man nicht, dass die Knoten von P paarweise verschieden sind, so spricht man von einem Weg.

Planarer Graph

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 K₅ oder K_3,3 als Minor hat.

Siehe: Planarer Graph.

Pseudo-achromatische Zahl

Die pseudo-achromatische Zahl ψ_s(G) eines Graphen G ist die größte Zahl k, für die G 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

(zum Seitenanfang)

Quelle

Eine Quelle in einem gerichteten Graph ist ein Knoten, der keinen Vorgänger hat.

Siehe auch: Senke.

R

(zum Seitenanfang)

Rand

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

Regulärer Graph

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 k, so bezeichnet man ihn als k-regulär. Ein Wurzelbaum heißt k-regulär, wenn alle Knoten mit Ausnahme der Blätter den Ausgangsgrad k haben.

Siehe auch: Nachbarschaft und Grad in Graphen.

Radius

Der Radius R(G) eines Graphen G ist das Minimum der Exzentrizitäten der Knoten von G.

Für alle Graphen G gilt $R(G)\le D(G)\le 2 \cdot R(G)$, wobei D(G) der Durchmesser von G ist.

Die Knoten, deren Exzentrizität dem Radius entsprechen, bilden das Zentrum von G.

Rückwärtskante

Siehe: Vorwärtskante.

S

(zum Seitenanfang)

Satz von Hall

Siehe: Heiratssatz.

Schleife

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 (v,v).

Siehe auch: Mehrfachschleife.

Schleifenfreier Graph

Siehe: Schleifenloser Graph.

Schleifenloser Graph

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

Schlinge

Siehe: Schleife.

Schnitt

Eine Zerlegung (oder Partition) $S(X,Y)\!$ der Knotenmenge V eines Graphen in zwei nichtleere Teilmengen $X\subset V$ und $Y\subset V$ mit $X\cup Y=V\!$ und $X\cap Y=\varnothing$ 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: Flüsse und Schnitte in Netzwerken.

Schnittknoten

Ein Schnittknoten in einem Graphen G ist ein Knoten k für den gilt, dass G − k mindestens eine Zusammenhangskomponente mehr hat, als G. D. h. dass die Zusammenhangskomponente, in der k liegt, durch Entfernen von k zerfällt. Anders ausgedrückt: es existieren Knoten x und y für die jeder Weg von x nach y über k führt.

Schwache Zusammenhangskomponente

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

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

Semieulerscher Graph

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

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

Eine Senke ist ein Knoten in einem gerichteten Graph, welcher keinen Nachfolger hat.

Siehe auch: Quelle.

Separator

Sei G = (V,E) ein endlicher, ungerichteter, schlichter Graph. Eine Knotenmenge $S \subseteq V$ heißt Separator für zwei nicht benachbarte Knoten $a, b \in V$ gdw. a und b in $G(V \setminus S)$ in verschiedenen Zusammenhangskomponenten liegen.

Simplizialer Knoten

Ein Knoten $v \in V$ des Graphen G = (V,E) heißt simplizial, wenn er gemeinsam mit all seinen Nachbarn eine Clique, d. h. einen vollständigen Teilgraphen in G bildet.

Spannbaum

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

Siehe auch: Spannbaum.

Spanner

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

Spannwald

Siehe Gerüst.

Stabile Menge

Eine stabile oder unabhängige Menge (Independent Set) ist in einem ungerichteten Graphen eine Menge von Knoten, zwischen denen keine Kante verläuft.

Siehe auch: Knotenüberdeckungen, Cliquen und stabile Mengen.

Stabilitätszahl

Als Stabilitäts- oder Unabhängigkeitszahl bezeichnet man die Anzahl der Knoten in einer größten stabilen Menge.

Siehe auch: Knotenüberdeckungen, Cliquen und stabile Mengen.

Stark zusammenhängender Graph

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

Starke Zusammenhangskomponente

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

Ist k = (x,y) eine gerichtete Kante, so bezeichnet man x als ihren Startknoten und y als ihren Endknoten.

Bei ungerichteten Kanten k = {x,y} kann man x und y sowohl als Startknoten als auch als Endknoten bezeichnen. Hier spricht man in der Regel aber einfach von den beiden „zu k inzidenten Knoten“.

Stern

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

Siehe: Teilgraph.

Symmetrischer Graph

Ein symmetrischer Graph ist ein gerichteter Graph, der mit jeder Kante (u,v) auch die Kante (v,u) enthält.

Hauptartikel: Symmetrischer Graph.

Siehe auch: Typen von Graphen in der Graphentheorie.

T

(zum Seitenanfang)

Taillenweite

Die Taillenweite τ(G) eines Graphen G ist die Länge eines kürzesten Kreises in G. Ist G ein Wald (hat also keine Kreise) so setzt man $\tau (G) = \infty$.

Teilgraph

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

Siehe auch: Obergraph, Induzierter Teilgraph.

Tiefe

Die Tiefe eines Knotens in einem Wurzelbaum ist die Anzahl der Kanten im Weg von der Wurzel bis zum Knoten.

Siehe auch: Höhe.

Topologische Ordnung

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

Topologische Sortierung

Siehe: Topologische Ordnung bzw. Topologische Sortierung.

Travelling Salesman Problem

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: Problem des Handlungsreisenden.

Triangulierter Graph

Ein endlicher, schlichter und ungerichteter Graph heißt trianguliert oder auch chordal, wenn er keine induzierten Kreise C_n mit $n \geq 4$ 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: Triangulierter Graph.

Triviale Partition

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

Trivialer Kreis

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

Trivialer Zyklus

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

Turniergraph

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

Siehe auch: Turniergraph

U

(zum Seitenanfang)

Umfang

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

Unabhängige Knotenmenge

Eine unabhängige Knotenmenge in einem ungerichteten Graphen G = (V,E) ist eine Menge $U \subseteq V$ mit der Eigenschaft, dass keine zwei Knoten aus U in G durch eine Kante verbunden sind:

U ist unabhängig in G gdw. $\forall u,v \in U: {u, v} \notin E$.

Unabhängige Kantenmenge

Siehe Paarung.

Unabhängige Menge

Siehe: Stabile Menge.

Unabhängigkeitszahl

Siehe: Stabilitätszahl.

Unendlicher Graph

Ein unendlicher Graph ist ein Graph, dessen Knotenzahl unendlich ist.

Siehe auch: Unendlicher Graph

Ungerichtete Kante

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, Typen von Graphen in der Graphentheorie.

Ungerichteter Graph

Ein ungerichteter Graph ist ein Graph, der keine gerichteten Kanten enthält.

Siehe auch: Typen von Graphen in der Graphentheorie.

Uniformer Hypergraph

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

Universaler Knoten

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

Unterbaum

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

Untergraph

Siehe: Teilgraph.

Unzusammenhängender Graph

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

V

(zum Seitenanfang)

Valenz

Siehe: Grad.

Valenzsequenz

Siehe: Gradfolge.

Vater

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

Verbesserungsweg

Ist G ein Graph und M eine Paarung in G, dann ist ein Verbesserungsweg (auch M-alternierender Weg) ein Weg w, der abwechselnd Kanten aus M und Kanten aus $E(G)\setminus M$ enthält, wobei an beiden Enden Knoten liegen, welche mit keiner Kante aus M inzidieren (also sind auch die beiden Endkanten von w aus $E(G)\setminus M$).

Ein solcher Weg heißt Verbesserungsweg, da man eine Paarung M' mit | M' | > | M | erhalten kann, indem man die Kanten von w, die in M liegen aus M entfernt und dafür die anderen Kanten von w einfügt.

Satz von Berge (1957): Eine Paarung ist genau dann maximal, wenn es keinen Verbesserungsweg gibt.

Vergleichbarkeitsgraph

Ein (gerichteter) Vergleichbarkeitsgraph ist ein gerichteter Graph, dessen Kanten einer Ordnungsrelation auf seinen Knoten entsprechen. Sei beispielsweise O = (V, < ) eine Halbordnung auf der Knotenmenge V des Graphen G = (V,E), so gilt für jede Kante $(u, v) \in E$ die Beziehung u < v.

Von einem ungerichteten Vergleichbarkeitsgraphen spricht man, wenn für jede Kante $(u, v) \in E$ gilt: (u < v oder v < u).

Vollständige Knotenfärbung

Eine vollständige Knotenfärbung ist eine Knotenfärbung, bei der für jedes Paar {i,j} von Farben eine Kante $\{x,y\}\in E(G)$ existiert, sodass x mit i und y mit j 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

Siehe: Perfekte Paarung.

Vollständiger Graph

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 n Knoten bezeichnet man mit K_n

Ein vollständiger p-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 p Partitionsmengen, welche n1,...,np Knoten enthalten, bezeichnet man mit $K_{n1, \ldots, np}$

Siehe auch: K₅ und K_3,3 in Charakterisierung von planaren Graphen.

Vorgänger

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

Vorgängermenge

Die Menge aller Vorgänger eines Knoten v. Also alle Knoten in einem Graphen von denen v durch einen Pfad erreicht werden kann.

Formal: $\forall w : \exist p : p = (w,\ldots, v)$ mit $v,w \in V, p \in P, w \in W$ wobei V die Knotenmenge, P die Menge der Pfade und W die Vorgängermenge ist, (siehe auch: Transitive Hülle)

Vorwärtskante

Der Begriff Vorwärtskante hat ebenso wie die Begriffe Rückwärtskante, Querkante und Baumkante im Kontext der 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 einen 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 einen 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

(zum Seitenanfang)

Wald

Als Wald bezeichnet man in der Graphentheorie einen ungerichteten Graphen ohne Kreis.

Ein Graph ist genau dann ein Wald, wenn sein Index 0 ist.

Siehe auch: Wald (Graphentheorie).

Weg

Ein Weg $W=(v_1, v_2, \ldots, v_p)$ ist eine Folge von Knoten, wobei immer v_i und v_{i + 1} adjazent sein müssen für alle i = 1,...,p − 1.

Sind alle Knoten paarweise verschieden, so spricht man von einem Pfad.

Wegüberdeckung

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

Wurzel

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

Siehe auch: Wurzelbaum.

Wurzelbaum

Ein Wurzelbaum ist ein Baum B = (V,E) bei welchem ein Knoten als Wurzel $w\in V$ ausgezeichnet ist. Bäume ohne Wurzel bezeichnet man im Gegensatz zu Wurzelbäumen auch als freie Bäume. 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 y auf einem einfachen Pfad von w zu einem anderen Knoten x heißt Vorgänger von x.
• Ist y ein Vorgänger von x und $x \neq y$, so heißt x Nachfolger von y.
• Ein durch eine Kante verbundener Vorgänger heißt auch Vater, x heißt dann Sohn von y.
• Die Höhe eines Wurzelbaums ist die maximale Länge eines Pfades von der Wurzel bis zu einem Blatt.

X

(zum Seitenanfang)

Y

(zum Seitenanfang)

Z

(zum Seitenanfang)

Zentrum

Das Zentrum Z(G) eines Graphen G ist die Menge der Knoten von G, deren Exzentrizität dem Radius von G entspricht

Siehe auch: Durchmesser.

Zuordnung

Siehe Paarung.

Zusammenhängender Graph

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

Zusammenhangskomponente

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

Zusammenhangszahl

Siehe: Knotenzusammenhangszahl.

Zyklischer Graph

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

Zyklomatische Zahl

Siehe: Index.

Zyklus

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: Wege, Pfade, Zyklen und Kreise in Graphen.

Siehe auch

• Portal:Graphentheorie