Allgemeine Definitionen, Kürzeste Wege und minimaler Spannbaum als LP, Kruskal-Algorithmus

Question 1

Definition: Graph

Answer 1

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.

Question 2

Definition: Endlicher Graph

Answer 2

Ein Graph dessen Menge der Knoten und Kanten endlich ist, heißt endlicher Graph.

Question 3

Definition: Schlichter Graph

Answer 3

Ein Graph ohne parallele Kanten und ohne Schlinge wird als schlichter Graph bezeichnet.

Question 4

Definition: Digraph

Answer 4

Ein schlichter, gerichteter Graph mit endlicher Knotenmenge heißt Digraph.

vgl. Folie 253

Question 5

Definition: Multigraph

Answer 5

Ein Graph mit parallelen Kanten wird als Multigraph bezeichnet.

Question 6

Definition: Weg

Answer 6

Ein Weg ist die Folge von gerichteten Kanten, jeweils vom Pfeilende zur Pfeilspitze.

Question 7

Definition: Zyklus

Answer 7

Ein geschlossener Weg heißt Zyklus.

vgl. Folie 254

Question 8

Definition: Kette

Answer 8

Eine Kette ist die Folge von ungerichteten Kanten oder von gerichteten Kanten, wobei der Richtungssinn keine Rolle spielt.

vgl. Folie 255

Question 9

Definition: Kreis

Answer 9

Eine geschlossene Kette heißt Kreis.

vgl. Folie 255

Question 10

Definition: Vollständiger Digraph

Answer 10

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

Question 11

Definition: Vollständiger schlichter Graph

Answer 11

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

Question 12

Definition: Zusammenhängender Graph

Answer 12

Ein Graph heißt zusammenhängender Graph, wenn jedes Knotenpaar durch mindestens eine Kette verbunden ist.

vgl. Folie 258

Question 13

Definition: Gewichteter Graph

Answer 13

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

Question 14

Definition: Ungerichteter Baum

Answer 14

Ein ungerichteter Baum ist ein zusammenhängender, kreisfreier, ungerichteter Graph.

vgl. Folie 260

Question 15

Definition: Gerichteter Baum

Answer 15

Ein gerichteter Baum ist ein gerichteter, kreisfreier Graph mit genau einem Ausgangsknoten.

vgl. Folie 260

Question 16

Definition: Spannbaum

Answer 16

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

Question 17

Definition: Gewicht

Answer 17

Das Gewicht I(V´,E´) eines Spannbaumes ist die Summe aller seiner Kantengewichte.

Question 18

Definition: Minimaler Spannbaum

Answer 18

Ein minimaler Spannbaum hat das minimale Gewicht unter allen möglichen Spannbäumen.

Question 19

Definition: Vorgänger, Nachfolger, Nachbarn

Answer 19

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.

Question 20

Wahr oder falsch?

In ungerichteten Graphen spricht man nur von Nachbarn und nicht von Vorgängern und Nachfolgern.

Answer 20

Wahr!

Question 21

Was versteht man unter einer Quelle?

Answer 21

Ein Knoten ohne Vorgänger

Question 22

Was versteht man unter einer Senke?

Answer 22

Ein Knoten ohne Nachfolger

Question 23

Nenne die Voraussetzungen für den Kruskal-Algorithmus.

Answer 23

Graph muss
- endlich 
- zusammenhängend
- schlingenfrei
- ungerichtet
- gewichtet
sein.

Question 24

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.

Answer 24

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

Question 25

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?

Answer 25

Nein!

Es kann mehrere Kanten mit dem minimalen Gewicht geben.

Question 26

Kann man Kruskals Algorithmus auch verwenden, um einem maximalen Spannbaum zu berechnen?

Answer 26

Ja!

Mit größtem Gewicht beginnen und rückwärts gehen.

Question 27

Stelle das Kürzeste-Wege Problem allgemein als Optimierungsproblem auf.

Answer 27

vgl. Folie 244 bzw. Lösungskatalog S. 46

3 NB: Start, Transport- und Endknoten

Question 28

Stelle das Minimaler-Spannbaum Problem allgemein als Optimierungsproblem auf.

Answer 28

vgl. Folie 246 bzw. Lösungskatalog S. 47 (Achtung! Definitionsbereich von xij ist falsch angegeben)

2 NB

Question 29

Stelle das Travelling-Salesman Problem allgemein als Optimierungsproblem auf.

Answer 29

vgl. Lösungskatalog S. 47

3 NB (4 bei gerichteten Kanten)

Question 30

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?

Answer 30

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)

Question 31

Wie müsste ein Graph aussehen, damit das dazugehörige lineare Program keine Lösung liefert, die als Spannbaum interpretiert werden kann?

Answer 31

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

Question 32

Wie müsste ein Graph aussehen, damit die Existenz einer zulässigen Lösung des TSP sichergestellt ist?

Answer 32

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

Question 33

Es wurde ein Bahnnetz mit minimaler Distanz durch den Kruskal Algorithmus gefunden. Wie nennt man die Gesamtlänge in der Graphentheorie?

Answer 33

Gewicht des Spannbaums

Question 34

Stelle das TSP allgemein verbal als LP auf.

Answer 34

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)

Question 35

Stelle LP zur Berechnung von minimalen Spannbäumen allgemein verbal als LP auf.

Answer 35

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)