Allgemeine Definitionen, Kürzeste Wege und minimaler Spannbaum als LP, Kruskal-Algorithmus Flashcards
(35 cards)
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
