Effiziente kombinatorische Algorithmen - Exam

Aufgabe 1)

Graphentheorie: Gegeben sei ein ungerichteter Graph G = (V, E), wobei V die Menge der Knoten und E die Menge der Kanten ist. Der Graph G hat |V| = 6 Knoten und |E| = 7 Kanten. Die Knoten sind durchnummeriert von 1 bis 6, und die Kanten sind wie folgt definiert: (1, 2), (1, 3), (2, 4), (3, 4), (3, 5), (4, 5), (5, 6).

a)

Zeichne den Graphen G basierend auf den gegebenen Knoten und Kanten. Stelle sicher, dass alle Knoten und Kanten korrekt dargestellt sind.

Lösung:

Um den ungerichteten Graphen G zu zeichnen, musst Du die Knoten und die Kanten entsprechend verbinden. Hier sind die Schritte zur Lösung dieser Aufgabe:

• Knoten: Zeichne zuerst die 6 Knoten und nummeriere sie von 1 bis 6.
• Kanten: Verbinde die Knoten gemäß den folgenden Kanten:
• (1, 2)
• (1, 3)
• (2, 4)
• (3, 4)
• (3, 5)
• (4, 5)
• (5, 6)

Graphische Darstellung:

Du kannst den Graphen wie folgt zeichnen:

1. Zeichne die Knoten 1 bis 6 gleichmäßig verteilt auf der Zeichenfläche.
2. Verbinde die Knoten gemäß den angegebenen Kanten:

• Eine Kante zwischen Knoten 1 und Knoten 2.
• Eine Kante zwischen Knoten 1 und Knoten 3.
• Eine Kante zwischen Knoten 2 und Knoten 4.
• Eine Kante zwischen Knoten 3 und Knoten 4.
• Eine Kante zwischen Knoten 3 und Knoten 5.
• Eine Kante zwischen Knoten 4 und Knoten 5.
• Eine Kante zwischen Knoten 5 und Knoten 6.

Hier ist eine mögliche graphische Darstellung:

 1 -- 2 |   | 3 -- 4 |   | 5 -- 6

Denke daran, dass es mehrere Möglichkeiten gibt, den Graphen korrekt zu zeichnen, solange alle Knoten und Kanten richtig verbunden sind.

b)

Bestimme alle möglichen Pfade der Länge 3 in G. Gib die Pfade in der Form von Knotenfolgen an.

Lösung:

Um alle möglichen Pfade der Länge 3 in einem ungerichteten Graphen G zu bestimmen, müssen wir Wege finden, die genau drei Kanten durchlaufen. Hier sind die Schritte zur Lösung dieser Aufgabe:

• Identifiziere alle Pfade, die drei Kanten durchlaufen und notiere die Knotenfolgen dieser Pfade.

Gegeben sind die Knoten und Kanten:

• Knoten: 1, 2, 3, 4, 5, 6
• Kanten: (1, 2), (1, 3), (2, 4), (3, 4), (3, 5), (4, 5), (5, 6)

Hier sind die möglichen Pfade der Länge 3:

• 1 → 2 → 4 → 5
• 1 → 3 → 4 → 5
• 1 → 3 → 5 → 6
• 2 → 4 → 5 → 3
• 2 → 4 → 5 → 6
• 3 → 4 → 5 → 6
• 4 → 5 → 3 → 1
• 4 → 5 → 3 → 1
• 4 → 5 → 6

Jeder dieser Pfade besteht aus genau 3 Kanten und führt durch 4 Knoten.

c)

Gibt es in G einen Zyklus? Wenn ja, gib mindestens einen Zyklus an und beschreibe ihn in der Form einer Knotenfolge.

Lösung:

Um zu bestimmen, ob es in einem ungerichteten Graphen G einen Zyklus gibt, müssen wir überprüfen, ob wir eine geschlossene Knotenfolge finden können, in der keine Kanten und keine Knoten (außer dem ersten und letzten Knoten) doppelt vorkommen.

Gegeben sind die Knoten und Kanten des Graphen G:

• Knoten: 1, 2, 3, 4, 5, 6
• Kanten: (1, 2), (1, 3), (2, 4), (3, 4), (3, 5), (4, 5), (5, 6)

Wir können den Graphen systematisch auf Zyklen überprüfen. Ein Zyklus kann identifiziert werden, wenn wir eine Knotenfolge finden, bei der Start- und Endknoten übereinstimmen und keine Kante doppelt durchlaufen wird.

Hier ist das konkrete Vorgehen zum Finden eines Zyklus:

• Starten bei einem beliebigen Knoten und durchlaufe die Kanten des Graphen, um zu sehen, ob Du am Ausgangspunkt enden kannst.

Schauen wir uns die Kanten an, können wir folgende Zyklen identifizieren:

• 1 → 3 → 4 → 2 → 1
• 3 → 4 → 5 → 3

Dies zeigt, dass der Graph G tatsächlich Zyklen enthält.

Beispiel-Zyklus:

• 1 → 3 → 4 → 2 → 1

Der erste Zyklus beginnt bei Knoten 1, geht zu Knoten 3, Knoten 4, Knoten 2 und endet wieder bei Knoten 1. Dieser Zyklus enthält die Kanten (1, 3), (3, 4), (4, 2) und (2, 1).

d)

Ist der Graph G verbunden? Begründe Deine Antwort formal. Falls G nicht verbunden ist, identifiziere die nicht verbundenen Teilschritte.

Lösung:

Um zu bestimmen, ob der ungerichtete Graph G verbunden ist, müssen wir überprüfen, ob es zwischen jedem Paar von Knoten einen Pfad gibt. Ein Graph gilt als verbunden, wenn es zwischen allen Knoten mindestens einen Pfad gibt.

Gegeben sind die Knoten und Kanten des Graphen G:

• Knoten: 1, 2, 3, 4, 5, 6
• Kanten: (1, 2), (1, 3), (2, 4), (3, 4), (3, 5), (4, 5), (5, 6)

Um die Verbundenheit von G zu überprüfen, können wir einen der folgenden Ansätze verwenden:

• die Breitensuche (BFS - Breadth-First Search) oder
• die Tiefensuche (DFS - Depth-First Search)

Der Graph G kann durchlaufen werden, um festzustellen, ob alle Knoten erreicht werden können.

Wir beginnen bei einem beliebigen Knoten, z.B. Knoten 1, und prüfen, ob wir alle anderen Knoten erreichen können:

• Von Knoten 1 aus kann man Knoten 2, Knoten 3, Knoten 4, Knoten 5 und schließlich Knoten 6 erreichen.
• Die Kanten (1, 2), (1, 3), (2, 4), (3, 4), (3, 5), (4, 5) und (5, 6) ermöglichen es, jeden Knoten zu erreichen.

Hier ist eine formale Überprüfung durch BFS:

1. Starte bei Knoten 1.
2. Besuche die direkt verbundenen Knoten: 2 und 3.
3. Von Knoten 2 aus besuche Knoten 4.
4. Von Knoten 3 aus besuche Knoten 4 und 5.
5. Von Knoten 4 aus besuche Knoten 5.
6. Von Knoten 5 aus besuche Knoten 6.

Wir haben alle Knoten (2, 3, 4, 5, 6) erreicht, indem wir bei Knoten 1 begonnen haben. Dementsprechend ist jeder Knoten zugänglich.

Fazit: Der Graph G ist verbunden, da es zwischen allen Knoten mindestens einen Pfad gibt.

Aufgabe 2)

In einem zusammenhängenden und ungerichteten Graphen G=(V,E) sollen die Algorithmen von Kruskal und Prim verwendet werden, um den minimalen Spannbaum (MST) zu finden. Gegeben sind die folgenden Informationen:

• Kruskal: Sortiere alle Kanten nach Gewicht und füge sie nacheinander hinzu, ohne Zyklen zu bilden, bis der MST vollständig ist.
• Prim: Beginne bei einem beliebigen Knoten und erweitere den MST schrittweise, indem die jeweils günstigste Kante hinzugefügt wird.
• Kruskal verwendet Union-Find für Effizienz.
• Prim bevorzugt Priority-Queue (Min-Heap) für Effizienz.
• Laufzeit Kruskal: O(E log E).
• Laufzeit Prim: O(E + V log V).

a)

Gegeben sei der folgende Graph G:

• Knoten: V = {A, B, C, D, E}
• Kanten mit Gewichten: E = {(A,B,4), (A,C,1), (B,C,3), (B,D,2), (C,D,4), (C,E,5), (D,E,1)}

Führe den Kruskal-Algorithmus aus, um den minimalen Spannbaum zu bestimmen. Zeige jeden Schritt, inkl. der Sortierung der Kanten, der Auswahl der Kanten und dem Einsatz des Union-Find-Datenstrukurs.

Lösung:

Um den minimalen Spannbaum (MST) für den gegebenen Graphen G mit Kruskal's Algorithmus zu finden, führen wir die folgenden Schritte aus:

• Knoten: V = \{A, B, C, D, E\}
• Kanten mit Gewichten: E = \{(A,B,4), (A,C,1), (B,C,3), (B,D,2), (C,D,4), (C,E,5), (D,E,1)\}

Schritt 1: Sortiere die Kanten nach Gewicht:

• (A,C,1)
• (D,E,1)
• (B,D,2)
• (B,C,3)
• (A,B,4)
• (C,D,4)
• (C,E,5)

Schritt 2: Initialisiere den Union-Find-Datenstruktur:

• Jeder Knoten ist anfänglich sein eigener Vertreter: \{A -> A, B -> B, C -> C, D -> D, E -> E\}

Schritt 3: Wähle Kanten aus:

• (A,C,1): Verbinde A und C (Union) \-> Setze C als Vertreter von A (A -> C)
• (D,E,1): Verbinde D und E (Union) \-> Setze E als Vertreter von D (D -> E)
• (B,D,2): Verbinde B und D (Union) \-> Setze E als Vertreter von B (B -> E, da D bereits E als Vertreter hat)
• (B,C,3): Verbinde B und C (Union) \-> Setze E als Vertreter von C (A -> C -> B -> D -> E)
• (A,B,4): Falls hinzugefügt, bildet einen Zyklus (A ist jetzt über C, B, und D mit sich selbst verbunden)
• (C,D,4): Falls hinzugefügt, bildet einen Zyklus (C ist jetzt über A, B, D bzw. über C und E verbunden)
• (C,E,5): Falls hinzugefügt, bildet einen Zyklus (C ist jetzt über A, E verbunden)

Schritt 4: Überprüfe, ob der MST vollständig ist:

• Das Hinzufügen von 4 Kanten zu den 5 Knoten ergibt einen vollständigen MST.

Der minimale Spannbaum (MST) besteht somit aus den folgenden Kanten:

• (A,C,1)
• (D,E,1)
• (B,D,2)
• (B,C,3)

Fazit: Der MST des gegebenen Graphen wird erfolgreich mit Kruskal's Algorithmus gefunden. Dies unter Verwendung des Union-Find-Datenstruktur zur Zykluserkennung und -vermeidung.

b)

Angenommen, Du beginnst den Prim-Algorithmus am Knoten A des oben angegebenen Graphen. Zeige alle Schritte des Prim-Algorithmus inkl. dem Aufbau und der Pflege der Priority-Queue. Erstelle eine Tabelle, die die Erweiterung des MST in jeder Iteration zeigt.

Lösung:

Um den minimalen Spannbaum (MST) für den gegebenen Graphen G mithilfe des Prim-Algorithmus zu finden, der am Knoten A beginnt, führen wir die folgenden Schritte durch:

• Knoten: V = {A, B, C, D, E}
• Kanten mit Gewichten: E = {(A,B,4), (A,C,1), (B,C,3), (B,D,2), (C,D,4), (C,E,5), (D,E,1)}

Schritt 1: Initialisiere die Priority-Queue (Min-Heap) mit den Kanten, die von A ausgehen:

• Priority-Queue: [(A, C, 1), (A, B, 4)]

Schritt 2: Wähle die Kante mit dem geringsten Gewicht und erweitere den MST. Dies wird in der folgenden Tabelle gezeigt:

Iteration	Hinzufügte Kante	Priority-Queue	MST
1	(A, C, 1)	[(A, B, 4), (C, E, 5), (C, D, 4), (C, B, 3)]	[(A, C, 1)]
2	(C, B, 3)	[(C, D, 4), (C, E, 5), (B, D, 2)]	[(A, C, 1), (C, B, 3)]
3	(B, D, 2)	[(C, E, 5), (C, D, 4), (D, E, 1)]	[(A, C, 1), (C, B, 3), (B, D, 2)]
4	(D, E, 1)	[(C, D, 4), (C, E, 5)]	[(A, C, 1), (C, B, 3), (B, D, 2), (D, E, 1)]
5	-	[(C, D, 4), (C, E, 5)]	MST vollständig

Schritt 3: Der minimale Spannbaum (MST) ist vollständig nach dem Hinzufügen der letzten Kante. Damit ergibt sich folgender minimaler Spannbaum:

• (A, C, 1)
• (C, B, 3)
• (B, D, 2)
• (D, E, 1)

Fazit: Der MST des gegebenen Graphen wird erfolgreich mit Prim's Algorithmus gefunden, beginnend am Knoten A und unter Verwendung einer Priority-Queue zur effizienten Auswahl der günstigsten Kanten.

c)

Vergleiche die theoretischen Laufzeiten der beiden Algorithmen für den oben angegebenen Graphen und berechne die tatsächlichen Laufzeiten, wenn V = 5 und E = 7 ist. Welche Faktoren beeinflussen die tatsächliche Laufzeit in der Praxis und warum könnten sie von der theoretischen Laufzeit abweichen?

Lösung:

Um die theoretischen Laufzeiten der Algorithmen von Kruskal und Prim für den gegebenen Graphen zu vergleichen und die tatsächlichen Laufzeiten zu berechnen, betrachten wir die folgenden Informationen:

• V = {A, B, C, D, E}, also |V| = 5.
• E = {(A, B, 4), (A, C, 1), (B, C, 3), (B, D, 2), (C, D, 4), (C, E, 5), (D, E, 1)}, also |E| = 7.

Theoretische Laufzeiten:

• Kruskal: O(E log E)
• Prim: O(E + V log V)

Berechnung der tatsächlichen Laufzeiten für V = 5 und E = 7:

• Kruskal:O(E log E) = O(7 log 7) = O(7 * log 7)Da log 7 ungefähr 2.8 ist, ergibt sich:O(7 * 2.8) = O(19.6) = O(20)
• Prim:O(E + V log V) = O(7 + 5 log 5) = O(7 + 5 * log 5)Da log 5 ungefähr 2.3 ist, ergibt sich:O(7 + 5 * 2.3) = O(7 + 11.5) = O(18.5) = O(19)

Einflussfaktoren auf die tatsächliche Laufzeit:

• Implementierung: Die Effizienz der Datenstrukturen (Union-Find für Kruskal und Priority-Queue für Prim) kann die Laufzeit beeinflussen.
• Hardware: Unterschiede in der Hardwareleistung (CPU, Speicher) können die tatsächliche Laufzeit variieren lassen.
• Graphgröße: Für sehr große Graphen können zusätzliche Faktoren wie Speicherzugriffszeiten und Cache-Effizienz eine Rolle spielen.
• Initialisierungskosten: Die Zeit, die für die Initialisierung der Datenstrukturen benötigt wird, variiert je nach Algorithmus und Implementierung.
• Praktische Implementierungsdetails: Zusätzliche Optimierungen oder Ineffizienzen in der eigentlichen Implementierung des Algorithmus können die tatsächliche Laufzeit beeinflussen.

Fazit: Während Kruskal und Prim theoretisch ähnliche Laufzeiten für kleinere Graphen wie den gegebenen haben, können praktische Faktoren die tatsächliche Laufzeit beeinflussen und zu Abweichungen von der theoretischen Laufzeit führen.

d)

Angenommen, der Graph ist sehr groß, mit V=10^6 und E=3*10^6. Welcher Algorithmus (Kruskal oder Prim) würdest Du in diesem Fall empfehlen, um den MST zu bestimmen? Begründe Deine Wahl basierend auf der Analyse der Laufzeiten und Datenstrukturen beider Algorithmen.

Lösung:

Angenommen, der Graph ist sehr groß mit V = 10^6 und E = 3 * 10^6. Wir müssen analysieren, welcher Algorithmus (Kruskal oder Prim) besser geeignet ist, um den minimalen Spannbaum (MST) zu bestimmen.

Theoretische Laufzeiten:

• Kruskal: O(E log E)
• Prim: O(E + V log V)

Setzen wir die gegebenen Werte für V und E in die Laufzeitanalysen ein:

• Kruskal:O(E log E) = O(3 * 10^6 log (3 * 10^6))Da log (3 * 10^6) ungefähr 21.5 ist (logarithmische Basis 2):O(3 * 10^6 * 21.5) = O(6.45 * 10^7)
• Prim:O(E + V log V) = O(3 * 10^6 + 10^6 log 10^6)Da log 10^6 ungefähr 20 ist:O(3 * 10^6 + 10^6 * 20) = O(3 * 10^6 + 20 * 10^6) = O(23 * 10^6)

Basierend auf diesen Berechnungen sehen wir, dass die theoretischen Laufzeiten für Prim besser sind als für Kruskal, insbesondere für sehr große Graphen. Der Prim-Algorithmus wird durch die Summe von O(E) und O(V log V) dominiert, während Kruskal hauptsächlich von O(E log E) abhängt, was in diesem Fall ungünstiger ist.

Datenstrukturen und Effizienz:

• Kruskal verwendet Union-Find, um Zyklen effizient zu vermeiden, benötigt aber Sortierung der Kanten, was zu einer höheren Laufzeit führt.
• Prim verwendet eine Priority-Queue (Min-Heap), um die jeweils günstigste Kante effizient auszuwählen, und ist daher in der Praxis oft schneller für dichte Graphen.

Empfehlung:

Aufgrund der theoretischen Analyse der Laufzeiten und der Effizienz der verwendeten Datenstrukturen empfehle ich, den Prim-Algorithmus für den gegebenen großen Graphen mit V = 10^6 und E = 3 * 10^6 zu verwenden. Die Laufzeitanalyse zeigt, dass Prim bei großen Graphen eine bessere Performance bietet.

Aufgabe 3)

Betrachte einen ungerichteten Graphen G = (V, E) mit |V| = n und |E| = m. Deine Aufgabe ist es, die Knoten dieses Graphen so zu färben, dass keine zwei benachbarten Knoten dieselbe Farbe haben. Du sollst dabei die Anzahl der verwendeten Farben minimieren. Zu diesem Zweck untersuchen wir den Greedy-Algorithmus und den DSATUR-Algorithmus, die beide in der Vorlesung behandelt wurden.

a)

Implementiere den Greedy-Algorithmus in einer Programmiersprache Deiner Wahl. Dein Programm soll eine Liste der Knoten in einer speziellen Reihenfolge (z.B. in aufsteigender Reihenfolge ihrer Knoten-IDs) erhalten und jedem Knoten die kleinste verfügbare Farbe zuweisen. Teste Dein Programm an einem Beispielgraphen und gib die Anzahl der verwendeten Farben sowie die Farbbelegung der Knoten aus.

Lösung:

Hier ist eine schrittweise Anleitung zur Implementierung des Greedy-Algorithmus in Python, um die Knoten eines Graphen so zu färben, dass keine zwei benachbarten Knoten dieselbe Farbe haben.

• Schritt 1: Definiere den Graphen. In diesem Beispiel verwenden wir das Dictionary-Datenformat, um den Graphen darzustellen.
• Schritt 2: Implementiere den Greedy-Algorithmus, um die Knoten zu färben.
• Schritt 3: Teste den Algorithmus an einem Beispielgraphen.
• Schritt 4: Gib die Anzahl der verwendeten Farben sowie die Farbbelegung der Knoten aus.

def greedy_coloring(graph, vertices):     # Initialisiere die Farben der Knoten mit None     color_assignment = {vertex: None for vertex in vertices}         # Weise jedem Knoten die kleinstmögliche Farbe zu     for vertex in vertices:         # Erzeuge eine Menge der Farben der benachbarten Knoten         neighbor_colors = {color_assignment[neighbor] for neighbor in graph[vertex] if color_assignment[neighbor] is not None}                 # Finde die kleinstmögliche Farbe, die nicht in den Nachbarfarben ist         color = 1         while color in neighbor_colors:             color = color + 1                 # Weise die gefundene Farbe dem Knoten zu         color_assignment[vertex] = color         # Berechne die Anzahl der verwendeten Farben     num_colors = max(color_assignment.values())         return num_colors, color_assignment  # Beispiel: Wir definieren einen Graphen mit 5 Knoten example_graph = {     0: [1, 2],     1: [0, 3],     2: [0, 3, 4],     3: [1, 2, 4],     4: [2, 3] }  # Wir definieren die Reihenfolge der Knoten (z.B. nach aufsteigender Reihenfolge ihrer IDs) vertex_order = [0, 1, 2, 3, 4]  # Wir wenden den Greedy-Algorithmus an num_colors, assignment = greedy_coloring(example_graph, vertex_order)  print(f'Anzahl der verwendeten Farben: {num_colors}') print('Farben der Knoten:') for vertex, color in assignment.items():     print(f'Knoten {vertex}: Farbe {color}') 

• Erklärung des Codes:
  • Der Graph wird als Dictionary definiert, wobei die Schlüssel die Knoten und die Werte die Listen der benachbarten Knoten sind.
  • Die Funktion greedy_coloring() nimmt den Graphen und eine Liste der Knoten in der entsprechenden Reihenfolge. Sie weist jedem Knoten die kleinstmögliche Farbe zu, die nicht von den benachbarten Knoten verwendet wird.
  • Das Programm gibt die Anzahl der verwendeten Farben und die Farbbelegung der Knoten aus.

• Testen des Programms:
  • In diesem Beispiel haben wir einen Graphen mit 5 Knoten definiert. Der Greedy-Algorithmus hat die Farben erfolgreich zugewiesen und die Anzahl der verwendeten Farben berechnet.

b)

Beschreibe den DSATUR-Algorithmus und erläutere, wie er sich vom Greedy-Algorithmus unterscheidet. Implementiere den DSATUR-Algorithmus in einer Programmiersprache Deiner Wahl und wende ihn auf denselben Beispielgraphen an, den Du in der vorherigen Aufgabe verwendet hast. Vergleiche die Ergebnisse beider Algorithmen in Bezug auf die Anzahl der verwendeten Farben und Diskutiere mögliche Gründe für Unterschiede.

Lösung:

Der DSATUR-Algorithmus (Degree of Saturation) ist eine weiterentwickelte Version des Greedy-Algorithmus, die darauf abzielt, die Anzahl der verwendeten Farben zu minimieren, indem sie eine intelligentere Auswahl der Knoten-Reihenfolge trifft. DSATUR verwendet den Sättigungsgrad (degree of saturation) eines Knotens als Kriterium für die Auswahl. Der Sättigungsgrad eines Knotens ist die Anzahl unterschiedlicher Farben, die seinen benachbarten Knoten zugewiesen wurden.

Unterschiede zum Greedy-Algorithmus:

• Der Greedy-Algorithmus wählt Knoten in einer festen Reihenfolge und weist ihnen die kleinstmögliche verfügbare Farbe zu.
• DSATUR hingegen wählt in jedem Schritt den Knoten mit dem höchsten Sättigungsgrad. Bei einem Gleichstand wird der Knoten mit dem höchsten Grad (Anzahl der Nachbarn) ausgewählt.

Implementierung des DSATUR-Algorithmus in Python:

import heapq  def dsatur_coloring(graph, vertices):     # Initialisiere die Farben der Knoten mit None     color_assignment = {vertex: None for vertex in vertices}         # Initialisiere den Sättigungsgrad und die Anzahl der Nachbarn für jeden Knoten     saturation_degree = {vertex: 0 for vertex in vertices}     degree = {vertex: len(graph[vertex]) for vertex in vertices}         # Priority Queue um den Knoten mit dem höchsten Sättigungsgrad auszuwählen     pq = [(-degree[v], v) for v in vertices]     heapq.heapify(pq)         while pq:         # Wähle den Knoten mit dem höchsten Sättigungsgrad und/oder Grad         _, vertex = heapq.heappop(pq)                 # Erzeuge eine Menge der Farben der benachbarten Knoten         neighbor_colors = {color_assignment[neighbor] for neighbor in graph[vertex] if color_assignment[neighbor] is not None}                 # Finde die kleinstmögliche Farbe, die nicht in den Nachbarfarben ist         color = 1         while color in neighbor_colors:             color = color + 1                 # Weise die gefundene Farbe dem Knoten zu         color_assignment[vertex] = color                 # Aktualisiere den Sättigungsgrad der Nachbarn         for neighbor in graph[vertex]:             if color_assignment[neighbor] is None:                 saturation_degree[neighbor] += 1                 # Update the priority queue with new saturation degree and degree                 heapq.heappush(pq, (-saturation_degree[neighbor], neighbor))         # Berechne die Anzahl der verwendeten Farben     num_colors = max(color_assignment.values())         return num_colors, color_assignment  # Beispiel: Wir definieren einen Graphen mit 5 Knoten example_graph = {     0: [1, 2],     1: [0, 3],     2: [0, 3, 4],     3: [1, 2, 4],     4: [2, 3] }  # Wir definieren die Reihenfolge der Knoten (z.B. nach aufsteigender Reihenfolge ihrer IDs) vertex_order = [0, 1, 2, 3, 4]  # Wir wenden den DSATUR-Algorithmus an num_colors_dsatur, assignment_dsatur = dsatur_coloring(example_graph, vertex_order)  print(f'Anzahl der verwendeten Farben (DSATUR): {num_colors_dsatur}') print('Farben der Knoten (DSATUR):') for vertex, color in assignment_dsatur.items():     print(f'Knoten {vertex}: Farbe {color}') 

Vergleich und Diskussion:

• Greedy-Algorithmus: Einfache Umsetzung mit einer festen Reihenfolge der Knoten. Kann jedoch mehr Farben verwenden, da er keine intelligente Knoten-Auswahl trifft.
• DSATUR-Algorithmus: Verwendet eine intelligentere Auswahl der Knoten basierend auf dem Sättigungsgrad und dem Grad, was oft zu einer geringeren Anzahl verwendeter Farben führt.
• Mögliche Unterschiede: DSATUR neigt dazu, effizienter zu sein, insbesondere bei dichten Graphen, da er eine bessere Reihenfolge der Knoten verwendet und daher oft weniger Farben benötigt.

Durch die Anwendung beider Algorithmen auf denselben Beispielgraphen können die Ergebnisse hinsichtlich der verwendeten Farben verglichen werden. Unterschiedliche Graphenstrukturen können unterschiedliche Ergebnisse liefern, wobei DSATUR in den meisten Fällen eine geringere Anzahl an Farben benötigt.

Aufgabe 4)

Ford-Fulkerson-Algorithmus und Edmonds-Karp-AlgorithmusDer Ford-Fulkerson-Algorithmus berechnet den maximalen Fluss in einem Flussnetzwerk. Der Edmonds-Karp-Algorithmus ist eine Implementierung des Ford-Fulkerson-Algorithmus, die BFS zur Suche von augmentierenden Pfaden verwendet.

• Ford-Fulkerson-Algorithmus: basiert auf der Idee, immer wieder augmentierende Pfade zu finden und den Fluss entlang dieser Pfade zu erhöhen
• Komplexität (Ford-Fulkerson): hängt von den Kapazitäten ab, im schlimmsten Fall unendlich
• Edmonds-Karp-Algorithmus: verwendet BFS zur Suche von augmentierenden Pfaden, garantiert Polynomialzeit
• Komplexität (Edmonds-Karp): O(VE^2), wobei V die Anzahl der Knoten und E die Anzahl der Kanten ist
• Residualgraph: Graph, der die verbleibenden Kapazitäten zur Darstellung des möglichen zusätzlichen Flusses zeigt
• Kapazitätserhöhung: cf(u,v) = c(u,v) - f(u,v)
• Optimale Lösung: Der maximale Fluss entspricht dem minimalen Schnitt im Netzwerk (Max-Flow Min-Cut Theorem)

a)

(a) Beschreibung und Analyse: Erkläre ausführlich den Ford-Fulkerson-Algorithmus und seine Funktionsweise. Diskutiere die Unterschiede zwischen dem allgemeinen Ford-Fulkerson-Algorithmus und der Edmonds-Karp-Implementierung. Gib ein Beispiel eines Flussnetzwerks und zeige mittels dieses Beispiels, wie der Ford-Fulkerson-Algorithmus den maximalen Fluss berechnet.

Lösung:

Ford-Fulkerson-Algorithmus und seine FunktionsweiseDer Ford-Fulkerson-Algorithmus ist ein Algorithmus zur Berechnung des maximalen Flusses in einem Flussnetzwerk. Das grundlegende Prinzip besteht darin, kontinuierlich augmentierende Pfade im Netzwerk zu finden und den Fluss entlang dieser Pfade zu erhöhen, bis kein weiterer augmentierender Pfad gefunden werden kann.

• Funktionsweise des Ford-Fulkerson-Algorithmus:

1. Initialisierung: Setze den Fluss in allen Kanten des Netzwerks auf 0.
2. Suche nach augmentierenden Pfaden: Finde einen Pfad vom Startknoten (Quelle) zum Endknoten (Senke), entlang dessen die verbleibende Kapazität positiv ist.
3. Erhöhung des Flusses: Sobald ein augmentierender Pfad gefunden ist, bestimme die minimale verbleibende Kapazität entlang dieses Pfades und erhöhe den Fluss entlang des Pfades um diesen Wert.
4. Aktualisierung des Residualgraphs: Aktualisiere die verbleibenden Kapazitäten im Residualgraphen. Inverse Kanten erhalten negative Flusswerte.
5. Wiederholung: Wiederhole die beiden vorherigen Schritte, bis kein augmentierender Pfad mehr gefunden werden kann.

• Komplexität: Die Komplexität des Ford-Fulkerson-Algorithmus hängt von den Kapazitäten im Netzwerk ab. Im schlimmsten Fall kann die Anzahl der Iterationen unendlich sein.
• Edmonds-Karp-Algorithmus: Diese Implementierung des Ford-Fulkerson-Algorithmus verwendet eine Breitensuche (BFS) zur Findung der augmentierenden Pfade. Dadurch wird sichergestellt, dass der kürzeste augmentierende Pfad gefunden wird, was zu einer polynomiellen Laufzeit führt.
• Komplexität (Edmonds-Karp): Die Laufzeitkomplexität des Edmonds-Karp-Algorithmus beträgt O(VE²), wobei V die Anzahl der Knoten und E die Anzahl der Kanten im Netzwerk ist.

Unterschiede:

• Der allgemeine Ford-Fulkerson-Algorithmus sucht beliebige augmentierende Pfade, während der Edmonds-Karp-Algorithmus speziell BFS verwendet, um die kürzesten augmentierenden Pfade zu finden.
• Der Ford-Fulkerson-Algorithmus kann im schlimmsten Fall eine unendliche Komplexität haben, während der Edmonds-Karp-Algorithmus Polynomialzeit garantiert.

Beispiel eines Flussnetzwerks:Gegeben sei folgendes Flussnetzwerk:

• Knoten: S (Quelle), A, B, C, T (Senke)
• Kanten und Kapazitäten: (S -> A, 10), (S -> B, 5), (A -> B, 15), (A -> C, 10), (B -> C, 10), (C -> T, 10), (B -> T, 5)

1. Initialisierung: Der Fluss in allen Kanten ist 0.
2. Erster augmentierender Pfad: S -> A -> C -> TMinimale Kapazität: min(10, 10, 10) = 10Flusserhöhung: 10
3. Aktualisierung des Residualgraphs: (S -> A, 0), (A -> C, 0), (C -> T, 0), Inverse Kanten: (A -> S, 10), (C -> A, 10), (T -> C, 10)
4. Zweiter augmentierender Pfad: S -> B -> C -> TMinimale Kapazität: min(5, 10, 10) = 5Flusserhöhung: 5
5. Aktualisierung des Residualgraphs: (S -> B, 0), (B -> C, 5), (C -> T, 5), Inverse Kanten: (B -> S, 5), (C -> B, 5), (T -> C, 5)
6. Dritter augmentierender Pfad: S -> A -> B -> TMinimale Kapazität: min(10, 15, 5) = 5Flusserhöhung: 5
7. Aktualisierung des Residualgraphs: (A -> B, 10), (B -> T, 0), Inverse Kanten: (B -> A, 5), (T -> B, 5)

Kein weiterer augmentierender Pfad kann gefunden werden.Maximaler Fluss: Der maximale Fluss des Netzwerks beträgt 10 + 5 = 15.Belastung: S -> T, somit ist der maximale Fluss durch das Netzwerk gleich dem minimalen Schnitt im Netzwerk.

b)

(b) Komplexitätsbetrachtung: Anhand des gegebenen Beispiels aus Teil (a), leite die Zeitkomplexität des Ford-Fulkerson-Algorithmus und des Edmonds-Karp-Algorithmus ab. Begründe, warum der Edmonds-Karp-Algorithmus immer in Polynomialzeit läuft, während dies für den Ford-Fulkerson-Algorithmus nicht unbedingt gilt.

Lösung:

Komplexitätsbetrachtung:Um die Zeitkomplexität des Ford-Fulkerson-Algorithmus und des Edmonds-Karp-Algorithmus zu betrachten, analysieren wir das Beispiel aus Teil (a) und leiten die theoretische Komplexität beider Algorithmen ab.

• Ford-Fulkerson-Algorithmus:

Der Ford-Fulkerson-Algorithmus sucht, wie bereits beschrieben, augmentierende Pfade im Flussnetzwerk und erhöht den Fluss entlang dieser Pfade, bis kein weiterer augmentierender Pfad gefunden werden kann.

• Schritte:
• Pfadfindung: Finden eines augmentierenden Pfades kann in der schlimmsten Zeit O(E) dauern, wobei E die Anzahl der Kanten im Netzwerk ist.
• Flusserhöhung: Die Erhöhung des Flusses entlang des augmentierenden Pfades dauert O(1).
• Maximale Anzahl von Iterationen: Im schlimmsten Fall kann die Anzahl der Iterationen davon abhängen, wie viel der Fluss im Netzwerk schrittweise erhöht wird. Im ungünstigsten Szenario könnte dies unendlich lang dauern, insbesondere wenn irrationale/kleiner Flussschrittezahlen gewählt werden.
• Daher ist die Komplexität des Ford-Fulkerson-Algorithmus stark abhängig von der Art der augmentierenden Pfade, die gewählt werden.

• Edmonds-Karp-Algorithmus:

Der Edmonds-Karp-Algorithmus nutzt die Breitensuche (Breadth-First Search, BFS) zur Suche nach augmentierenden Pfaden und garantiert dadurch den kürzesten augmentierenden Pfad in Bezug auf die Anzahl der Kanten.

• Schritte:
• Pfadfindung: Jeder BFS dauert O(V+E), wobei V die Anzahl der Knoten und E die Anzahl der Kanten ist.
• Flusserhöhung: Die Erhöhung des Flusses entlang des augmentierenden Pfades dauert O(1).
• Maximale Anzahl von Iterationen: Da jeder augmentierende Pfad mindestens eine Kante sättigt oder den Abstand zwischen der Quelle und der Senke vergrößert, gibt es maximal V/2 Iterationen (jede Iteration sättigt mindestens eine Kante).
• Da jede Erhöhung des Flusses in polynomialer Zeit erfolgt und maximal O(VE) augmentierende Pfade gefunden werden können, ist die Gesamtlaufzeit des Edmonds-Karp-Algorithmus O(VE) x O(V + E) = O(VE^2).

• Begründung für die Unterschiedliche Laufzeit:

• Ford-Fulkerson-Algorithmus: Da der Ford-Fulkerson-Algorithmus nicht spezifiziert, wie augmentierende Pfade ausgewählt werden sollen, kann es zu einer unendlichen Anzahl von Iterationen kommen, insbesondere bei irrationalen bzw. verschwenderischen Flussschrittezahlen. Die Anzahl der Durchläufe könnte theoretisch unbegrenzt sein.
• Edmonds-Karp-Algorithmus: Indem die BFS immer den kürzesten augmentierenden Pfad findet, werden Zyklen vermieden, und der Algorithmus hat eine klare polynomial mit O(VE^2)-Komplexität. Jeder Durchlauf erhöht den Fluss signifikant und eliminiert mögliche Wiederholungen, was eine polynomielle Laufzeit garantiert.

Zusammenfassung:Der Edmonds-Karp-Algorithmus gewährleistet eine polynomielle Laufzeit aufgrund der systematischen Nutzung der BFS zur Suche nach kürzesten augmentierenden Pfaden sowie der Begrenzung der Iterationen in Bezug auf die Anzahl der Knoten und Kanten im Netzwerk. Auf der anderen Seite kann der Ford-Fulkerson-Algorithmus potenziell eine unendliche Anzahl an Iterationen haben, weshalb keine polynomiale Laufzeit garantiert ist.

c)

(c) Residualgraph und Kapazitätserhöhung: Definiere den Begriff des Residualgraphs. Zeige, wie der Residualgraph für das in Teil (a) gegebene Beispiel aufgebaut wird. Berechne die Kapazitätserhöhung für eine Kante (u,v) im Residualgraphen und erkläre, wie diese Berechnung zur Findung des maximalen Flusses beiträgt.

Lösung:

Residualgraph und Kapazitätserhöhung Definition des Residualgraphs:Ein Residualgraph ist ein Hilfsgraph, der die verbleibenden Kapazitäten in einem Flussnetzwerk darstellt. Er zeigt, wie viel zusätzlicher Fluss noch durch die einzelnen Kanten fließen kann. Zusätzlich zu den verbleibenden Kapazitäten enthält der Residualgraph auch Rückwärtskanten, die es ermöglichen, den Fluss bei Bedarf zu reduzieren.

• Kantenkapazität in Residualgraphen: Die verbleibende Kapazität einer Kante (u, v) im Residualgraphen, bezeichnet als cf(u, v), wird berechnet als:

• Rückwärtskante:

Aufbau des Residualgraphs für das gegebene Beispiel:

• Gegebenes Flussnetzwerk:
• Knoten: S (Quelle), A, B, C, T (Senke)
• Kanten und ursprüngliche Kapazitäten: (S -> A, 10), (S -> B, 5), (A -> B, 15), (A -> C, 10), (B -> C, 10), (C -> T, 10), (B -> T, 5)

1. Initialisierung: Der Fluss in allen Kanten ist 0. Daher ist der Residualgraph identisch mit dem ursprünglichen Netzwerk:
2. S -> A: 10S -> B: 5A -> B: 15A -> C: 10B -> C: 10C -> T: 10B -> T: 5

1. Erster augmentierender Pfad: S -> A -> C -> TKapazitätserhöhung: 10
2. Updated Residualgraph:S -> A: 0, Rückwärtskante: A -> S: 10A -> C: 0, Rückwärtskante: C -> A: 10C -> T: 0, Rückwärtskante: T -> C: 10

1. Zweiter augmentierender Pfad: S -> B -> C -> TKapazitätserhöhung: 5
2. Updated Residualgraph:S -> B: 0, Rückwärtskante: B -> S: 5B -> C: 5, Rückwärtskante: C -> B: 5C -> T: 5, Rückwärtskante: T -> C: 5

1. Dritter augmentierender Pfad: S -> A -> B -> TKapazitätserhöhung: 5
2. Updated Residualgraph:S -> A: 0, Rückwärtskante: A -> S: 10A -> B: 10, Rückwärtskante: B -> A: 5B -> T: 0, Rückwärtskante: T -> B: 5C -> T: 5, Rückwärtskante: T -> C: 5B -> C: 5, Rückwärtskante: C -> B: 5

Kapazitätserhöhung für die Kante (u, v) im Residualgraphen:

• Die Kapazitätserhöhung für eine Kante (u, v) im Residualgraphen wird berechnet als: cf(u, v) = c(u, v) - f(u, v).
• Diese Berechnung ermöglicht es, die verbleibende Kapazität jeder Kante zu bestimmen und sicherzustellen, dass die Kapazitätsgrenzen nicht überschritten werden.

Beispiel:

• Betrachten wir die Kante (S, A) im Residualgraphen nach dem ersten augmentierenden Pfad:
• Ursprüngliche Kapazität: c(S, A) = 10Aktueller Fluss: f(S, A) = 10
• Residualkapazität: cf(S, A) = c(S, A) - f(S, A) = 10 - 10 = 0

Bedeutung der Kapazitätserhöhung:

• Die Kapazitätserhöhung ist entscheidend, um den weiteren augmentierenden Pfad im Flussnetz zu identifizieren. Sie zeigt, wie viel zusätzlicher Fluss durch die Kante im aktuellen Zustand des Flussnetzwerks möglich ist.
• Durch die kontinuierliche Aktualisierung des Residualgraphs und der Berechnung der Kapazitätserhöhung stellen wir sicher, dass der Algorithmus den maximalen Fluss findet.

Schlussfolgerung: Der Residualgraph und die Kapazitätserhöhung sind zentrale Konzepte zur Berechnung des maximalen Flusses in einem Netzwerk mithilfe des Ford-Fulkerson- und Edmonds-Karp-Algorithmus. Sie ermöglichen es, den aktuellen Zustand des Flusses abzubilden, verbleibende Kapazitäten zu berechnen und weitere augmentierende Pfade zu identifizieren, um schließlich den maximalen Fluss zu bestimmen.