Allgemeine Definitionen, Kürzeste Wege und minimaler Spannbaum als LP, Kruskal-Algorithmus Flashcards
Definition: Graph
Ein Graph g(V,E) ist eine Menge von Punkten V, die eventuell durch Kanten E miteinander verbunden sind, wobei es nicht auf die Form ankommt. Punkte nennt man auch Ecken oder Knoten.
Definition: Endlicher Graph
Ein Graph dessen Menge der Knoten und Kanten endlich ist, heißt endlicher Graph.
Definition: Schlichter Graph
Ein Graph ohne parallele Kanten und ohne Schlinge wird als schlichter Graph bezeichnet.
Definition: Digraph
Ein schlichter, gerichteter Graph mit endlicher Knotenmenge heißt Digraph.
vgl. Folie 253
Definition: Multigraph
Ein Graph mit parallelen Kanten wird als Multigraph bezeichnet.
Definition: Weg
Ein Weg ist die Folge von gerichteten Kanten, jeweils vom Pfeilende zur Pfeilspitze.
Definition: Zyklus
Ein geschlossener Weg heißt Zyklus.
vgl. Folie 254
Definition: Kette
Eine Kette ist die Folge von ungerichteten Kanten oder von gerichteten Kanten, wobei der Richtungssinn keine Rolle spielt.
vgl. Folie 255
Definition: Kreis
Eine geschlossene Kette heißt Kreis.
vgl. Folie 255
Definition: Vollständiger Digraph
Ein Digraph heißt vollständiger Digraph, wenn für jedes Knotenpaar i, j ein Pfeil von i nach j und ein Pfeil von j nach i vorhanden ist.
vgl. Folie 256
Definition: Vollständiger schlichter Graph
Ein ungerichteter schlichter Graph heißt vollständiger schlichter Graph, wenn für jedes Knotenpaar i, j eine Kante von i nach j existiert.
vgl. Folie 257
Definition: Zusammenhängender Graph
Ein Graph heißt zusammenhängender Graph, wenn jedes Knotenpaar durch mindestens eine Kette verbunden ist.
vgl. Folie 258
Definition: Gewichteter Graph
Ein Graph g(V,E,w) wird als gewichteter Graph bezeichnet, wenn alle seine Kanten E mit Werten w(e) versehen sind. Die Summe aller Pfeil-Bewertungen eines Weges wird auch als Länge des Weges bezeichnet.
vgl. Folie 259
Definition: Ungerichteter Baum
Ein ungerichteter Baum ist ein zusammenhängender, kreisfreier, ungerichteter Graph.
vgl. Folie 260
Definition: Gerichteter Baum
Ein gerichteter Baum ist ein gerichteter, kreisfreier Graph mit genau einem Ausgangsknoten.
vgl. Folie 260
Definition: Spannbaum
Gegeben sei ein ungerichteter Graph g(V,E,w) mit Kantengewichten. Ein Spannbaum von g(V,E,w) ist ein Subgraph (V´,E´) von (V,E) für den gilt:
- V´ = V, d.h. der Subgraph umfasst alle Knoten von g
- (V´, E´) ist ein Baum, und damit
- (V´, E´) ist zusammenhängend
Definition: Gewicht
Das Gewicht I(V´,E´) eines Spannbaumes ist die Summe aller seiner Kantengewichte.
Definition: Minimaler Spannbaum
Ein minimaler Spannbaum hat das minimale Gewicht unter allen möglichen Spannbäumen.
Definition: Vorgänger, Nachfolger, Nachbarn
In einem gerichteten Graphen heißt ein Knoten j Nachfolger eines Knoten i, wenn ein Weg vom Konten i zum Knoten j existiert. Umgekehrt ist i ein Vorgänger von j. Vorgänger und Nachfolger werden auch als Nachbarn bezeichnet.
Wahr oder falsch?
In ungerichteten Graphen spricht man nur von Nachbarn und nicht von Vorgängern und Nachfolgern.
Wahr!
Was versteht man unter einer Quelle?
Ein Knoten ohne Vorgänger
Was versteht man unter einer Senke?
Ein Knoten ohne Nachfolger
Nenne die Voraussetzungen für den Kruskal-Algorithmus.
Graph muss - endlich - zusammenhängend - schlingenfrei - ungerichtet - gewichtet sein.
Wahr oder falsch?
Wenn für ein Kürzeste-Wege-Problem bzw. Minimales Spannbaum-Problem eine optimale Lösung existiert, dann existiert auch eine ganzzahlige, optimale Lösung, die die Zielfunktion minimiert.
Voraussetzung: xij wurde als reelle Zahl zwischen 0 und 1 definiert.
Wahr!
Bei einem Kürzeste-Wege-Problem bzw. Minimales Spannbaum-Problem kann neben der optimalen Lösung mit ganzzahligen Variablen auch eine nicht-ganzzahlige optimale Lösung existieren. Der optimale ZF-Wert ist eindeutig, während das für den Lösungsvektor nicht gilt.
Voraussetzung: xij wurde als reelle Zahl zwischen 0 und 1 definiert.
Anwendungsbeispiel: Strom/Wasser etc. teilt sich im Graphen auf
Wenn nur der optimale ZF-Wert gesucht wird sollte man auch Werte zwischen 0 und 1 zulassen, um Rechenaufwand zu sparen.
vgl. Folie 244, 245
Sei (V,E) ein Graph und sei e eine Kante mit minimalem Gewicht. Ist die Kante e dann immer im zugehörigen minimalen Spannbaum enthalten?
Nein!
Es kann mehrere Kanten mit dem minimalen Gewicht geben.
Kann man Kruskals Algorithmus auch verwenden, um einem maximalen Spannbaum zu berechnen?
Ja!
Mit größtem Gewicht beginnen und rückwärts gehen.
Stelle das Kürzeste-Wege Problem allgemein als Optimierungsproblem auf.
vgl. Folie 244 bzw. Lösungskatalog S. 46
3 NB: Start, Transport- und Endknoten
Stelle das Minimaler-Spannbaum Problem allgemein als Optimierungsproblem auf.
vgl. Folie 246 bzw. Lösungskatalog S. 47 (Achtung! Definitionsbereich von xij ist falsch angegeben)
2 NB
Stelle das Travelling-Salesman Problem allgemein als Optimierungsproblem auf.
vgl. Lösungskatalog S. 47
3 NB (4 bei gerichteten Kanten)
Was ist die Voraussetzung dafür, dass ein Kürzestes-Weg Problem auf jeden Fall eine ganzzahlige Lösung besitzt, obwohl der Definitionsbereich von xij alle reelen Zahlen zwischen 0 und 1 zulässt?
Wenn alle Kanten des Graphen nicht das gleiche Gewicht haben, teilt sich der Weg nie auf.
vgl. Aufgabenkatalog S. 22 Nr. 2.35 a) ii)
Wie müsste ein Graph aussehen, damit das dazugehörige lineare Program keine Lösung liefert, die als Spannbaum interpretiert werden kann?
- Alle Kanten haben das gleiche Gewicht (–> Möglicherweise nicht-ganzzahlige Lösung. Voraussetzung: Definitionsbereich xij zwischen 0 und 1)
- Graph ist nicht zusammenhängend
- Der Graph ist gerichtet (Spannbäume sind nur für ungerichtete Graphen definiert)
vgl. Aufgabenkatalog S. 22 Nr. 2.35 b) ii)
Wie müsste ein Graph aussehen, damit die Existenz einer zulässigen Lösung des TSP sichergestellt ist?
Auf einem vollständigen Digraph existiert immer eine zulässige und auch eine optimale Lösung für das TSP.
(Was ist mit einem vollständigen schlichten Graph?)
Es wurde ein Bahnnetz mit minimaler Distanz durch den Kruskal Algorithmus gefunden. Wie nennt man die Gesamtlänge in der Graphentheorie?
Gewicht des Spannbaums
Stelle das TSP allgemein verbal als LP auf.
ZF:
1) Minimiere die Summe über das Produkt aus Kanten (bei ungerichteten Kanten beide Richtungen) und Kantengewicht
NB:
2) Alles was aus einem Konten rausgeht = 1
3) Alles was in einen Knoten reingeht = 1
4) Jede ECHTE Teilmenge S von V <= |S| - 1
5) Bei ungerichteten Kanten: Kante von a nach b + Kante von b nach a <= 1
Definitionsbereich:
xij element aus {0,1} (Alternativ xij >= 0 und xij <= 1)
Stelle LP zur Berechnung von minimalen Spannbäumen allgemein verbal als LP auf.
ZF:
1) Minimiere die Summe über das Produkt aus Kanten (ungerichtete Kanten, daher jede Richtung nur einmal) und Kantengewicht
NB:
1) Summe über alle Kanten = n - 1
2) Jede Teilmenge S (nicht echte Teilmenge!) von V <= |S| - 1
Definitionsbereich:
xij element aus {0,1} (Alternativ xij >= 0 und xij <= 1)
