Online-Bibliothek

Glossar Graphentheorie

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 in einem ungerichteten Graph 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.

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, die den Graphen auf sich selbst abbildet (die permutierten Knoten sind durch dieselben Kanten verbunden wie die ursprünglichen).

B

(zum Seitenanfang)

Baum

Ein Baum ist ein zusammenhängender Graph, der keine Zyklen enthält.

Siehe auch: Baum.

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.

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

Blatt

Ein Blatt ist ein Knoten in einem Baum welcher keinen Nachfolger mehr hat.

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

todo

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)

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 von Graphen, 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 ist.

Siehe auch: Färbung von Graphen

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)

Defekt

todo

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:

Digraph

Siehe: gerichteter Graph

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₁,v₂,...,v_p) und w = (w₁,w₂,...,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 (). 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.

Dominationszahl

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

Dominierende Knotenmenge

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

Dreieck

Ein Dreieck ist ein Graph mit drei Knoten, die alle zueinander adjazent 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 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, 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 wird gewöhnlich ein Graph ohne besondere Strukturelemente wie Mehrfachkanten, orientierte Kante, Schleifen, Knoten- oder Kantengewichte bzw. Färbungen oder Markierungen bezeichnet.

Eingangsgrad

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

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

Endknoten eines Weges

todo

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

todo

Eulerkreis

Der Begriff Eulerkreis wird synonym für Eulertour verwendet. Die Bezeichnung "Eulerkreis" ist insofern falsch, als dass 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ächer

todo

Färbung

todo

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 und 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 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 ), 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:

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)

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 zyklus

Gerichteter Pfad

todo

Gerichteter Weg

todo

Gerüst

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

Gerichteter Zyklus

todo

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

Graph

Ein Graph ist ein Gebilde aus Knoten und Kanten, welche die Knoten miteinander verbinden.

Man unterscheidet vor allem zwischen ungerichteten und gerichteten Graphen sowie Graphen mit oder ohne Mehrfachkanten. Hypergraphen sind eine weitere Form von Graphen die untersucht werden.

Siehe auch: Typen von Graphen in der Graphentheorie

Graph mit Mehrfachkanten

todo

Graph ohne Mehrfachkanten

todo

Graphfärbung

todo

Größte Clique

Siehe: Maximale Clique

Größte gewichtete Paarung

todo

Größte Paarung

Siehe: Maximale Paarung

Größte stabile Menge

todo

Größtes gewichtetes Matching

Siehe: Größte gewichtete 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 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 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:

Siehe auch: Paarung

Höhe

Die Höhe eines Knotens u in einem Baum ist die Anzahl der Knoten zwischen der Wurzel des Baumes und u, und gibt somit den Abstand des Knotens zur Wurzel an.

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.

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:
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 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 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 den Kanten, die in G zwischen ihnen verlaufen.

Formal: der von I induzierte Teilgraph ist

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.

Siehe auch: Wälder und Bäume in der Graphentheorie

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.

Zwei Kanten eines einfachen ungerichteten Graphen heißen "inzident", wenn sie eine gemeinsame Endecke besitzen.

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 -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 ∈ E := {u,v} mit u, v ∈ 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 ∈ 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 ⊆ V x E, d. h. zu jedem Knoten wird für jede Kante, die ihn berührt, ein Element {v, e} mit v ∈ V und e ∈ E in I aufgenommen. Schlingen werden somit über jeweils ein Element der Inzidenzrelation, zwei parallele Kanten über vier Elemente der Inzidenzrelation eindeutig repräsentiert.

In-Tree

todo

Isolierter Knoten

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

Isomorphie

Zwei Graphen G = (V(G),E(G)) und H = (V(H),E(H)) heißen isomorph, falls eine bijektive Abbildung existiert, sodass für alle gilt genau dann, wenn

J

(zum Seitenanfang)

K

(zum Seitenanfang)

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.

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.

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

Kantengraph

Der Kantengraph (auch Linegraph) 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 inzident sind

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 . Kantenpanzyklische Graphen sind auch knotenpanzyklisch und damit auch panzyklisch.

Kantenüberdeckung

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

E' ist Kantenüberdeckung in G gdw. .

Kanten Unterteilung

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

Formal: Ist G = (V,E) ein Graph und , so entsteht G' durch Unterteilung von k als . Die Voraussetzung 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...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

Knotenpanzyklische Graphen

Ein Graph G heißt knotenpanzyklisch, wenn jeder Knoten auf einem Kreis der Länge p liegt, für alle .

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

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 eines Graphen G hat die gleiche Knotenmenge wie G und in sind zwei Knoten x und y genau dann Adjazent, wenn sie es in G nicht sind ( 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₁,v₂,...,v_p,v₁) ist eine Folge von Knoten, die bis auf den ersten und letzten Knoten paarweise verschieden sind, wobei immer v_i und v_{i + 1} adjazent sein müssen für alle i = 1,...,p − 1 und auch v_p und v₁ müssen adjazent sein.

Enthält ein Kreis alle Knoten des Graphen, so nennt man ihn einen 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 eines Graphen G ist der größte vollständige Graph, den G als Teilgraphen hat.

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.

Maximale stabile Menge

todo

Maximaler Fluss

todo

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 , so gilt stets , 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 also wenn sie durch eine Kante verbunden sind.

Bei gerichteten Graphen unterscheidet man positive - und negative Nachbarn. Genau dann, wenn 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 also nichts anderes als die Nachbarschaft von v, zu der v selbst hinzugefügt wurde. (analog sind und 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

todo

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.

Out-Tree

todo

P

(zum Seitenanfang)

paarer Graph

Siehe: Bipartiter Graph

Paarung

Eine Paarung bzw. ein Matching ist eine Teilmenge M der Kantenmenge eines ungerichteten Graphen, sodass jeder Knoten mit höchstens einer Kante aus M inzidiert.

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 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 den selben Knoten verlaufen, d. h. zu den selben Knoten inzident sind.

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 Paarung

Eine perfekte Paarung 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₁,v₂,...,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,...,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 der Knoten, von dem aus alle anderen Knoten erreichbar sind, der selbst aber keinen Vorgänger hat.

Siehe auch: Senke

R

(zum Seitenanfang)

Rand

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

Rectilinieares Traveling-Salesman-Problem

todo

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.

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 , wobei D(G) der Durchmesser von G ist.

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

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) der Knotenmenge V eines Graphen in zwei nichtleere Teilmengen und mit und heißt Schnitt.

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

Oder man betrachte die kleinste Äquivalenzrelation, welche die folgende Relation enthält: zwei beliebige Knoten sind in Relation ( in einer schwachen Zusammenhangskomponente ), falls es in einer Richtung ein gerichteter Weg existiert, der die beiden Knoten verbindet.

Damit stimmen die schwachen Zusammenhangskomponenten per Definition überein mit den Zusammenhangskomponenten des entsprechenden ungerichteten Graphen (man ersetze jede gerichtete Kante durch eine ungerichtete).

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 mehr hat.

Siehe auch: Quelle

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

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.

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 .

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

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

Trenner

todo

Triviale Partition

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

Trivialer Kreis

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

Trivialer Zyklus

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

U

(zum Seitenanfang)

Überdeckter Knoten

todo

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 mit der Eigenschaft, dass keine zwei Knoten aus U in G durch eine Kante verbunden sind:

U ist unabhängig in G gdw. .

unabhängige Kantenmenge

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

E' ist unabhängig in G gdw. .

Unabhängige Menge

Siehe: Stabile Menge

Unabhängigkeitszahl

Siehe: Stabilitätszahl

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.

Ungerichteter Kreis

todo

Ungerichteter Pfad

todo

Ungerichteter Weg

todo

Ungerichteter Zyklus

todo

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

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 enthält, wobei an beiden Enden Knoten liegen, welche mit keiner Kante aus M inzidieren (also sind auch die beiden Endkanten von w aus ).

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.

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 existiert, sodass x mit i und y mit j<