Aufgabe 3
In der nachstehenden Tabelle sind die Entfernungen von fünf Universitätsstandorten im südlichen Niedersachsen notiert. Bestimmen Sie mit dem Algorithmus von Christofides eine Rundreise durch die Standorte.
Gehen Sie dazu wie folgt vor:
1. Führen Sie den Kruskal-Algorithmus aus, um einen minimalen Spannbaum zu bestimmen.
(a) Sortieren Sie die ungerichteten Kanten aufsteigend nach Gewicht.
(b) Notieren Sie im Ablaufprotokoll drei Spalten: Kanten im Spannbaum; aktuell betrachtete Kante; verworfene Kanten. Beim Ablaufprotokoll können Sie mit Gänsefüßchen andeuten, dass alle Kanten aus dem vorigen Schritt übernommen werden und Sie müssen nur die aktuell betrachtete Kante explizit einordnen. Wenn Sie erkennen, dass der minimale Spannbaum fertig ist müssen Sie den Kruskal-Algorithmus nicht weiter durchführen.
(c) Geben Sie den minimalen Spannbaum \( S \) an.
2. Bestimmen Sie ein gewichtsminimales, perfektes Matching \( M \) auf der Menge aller Knoten mit ungeradem Grad in \( S \), setze \( S^{\prime}:=S \cup M \) :
(a) Geben Sie die Menge \( U \) der Knoten mit ungeradem Grad in \( S \) an.
(b) Bestimmen Sie ein gewichtsminimales, perfektes Matching \( M \) auf \( U \) (mit den Kantengewichten aus der Entfernungstabelle); indem Sie alle Möglichkeiten ausprobieren.
(c) Geben Sie \( S^{\prime}:=S \cup M \) an.
3. Geben Sie einen Eulerkreis \( K \) in \( S^{\prime} \) an.
4. Verkürzen Sie den Eulerkreis \( K \) durch Überspringen mehrfach besuchter Knoten:
(a) Gehen Sie den Eulerkreis \( K \) in \( H I \) beginnend ab. Sobald Sie einen Knoten \( v \) zum zweiten Mal besuchen, ersetzen Sie den Weg über diesen Knoten durch eine direkte Kante zwischen Vorgänger und Nachfolgerknoten von \( v \) in \( K \) (außer natürlich, wenn \( v \) schon der Endknoten ist).
$$\begin{array}{||l|l|l|l|l|l||} \hline & H & HI & GÖ & CLZ & BS \\ \hline \hline H & 0 & 29 & 94 & 75 & 55 \\ HI & 29 & 0 & 69 & 46 & 41 \\ GÖ & 94 & 69 & 0 & 41 & 91 \\ CLZ & 75 & 46 & 41 & 0 & 52 \\ BS & 55 & 41 & 91 & 52 & 0 \\ \hline \end{array} l z$$
Ansatz:
Ab der Teilaufgage 2 komme ich nicht mehr weiter
