URL:         /axel/graph_ws0001_blatt8.html
 
 
 

Aufgabe 15 bcc - letzter Teil - (4 + 2 Punkte)

Ändern Sie den Algorithmus für die starke Zusammenhangskomponente so ab, dass die Zweifachzusammenhangskomponenten berechnet werden. Warum funktioniert der Algorithmus? Führen Sie ein instruktives Beispiel vor.
 
 
 
 

Aufgabe 16 bcc - Programm - (4  Programmierpunkte)

Implementieren Sie die Berechnung der bcc. Eingabe ist ein ungerichteter Graph im bekannten Nachbarschaftslistenformat. (Aufgabe 4). Analog dem BFS Durchlauf soll das Ergebnis wieder in einem Vektor (Länge = Anzahl Knoten) abgespeichert werden. Um den Beginn einer neuen bcc zu Erkennen soll, der erste Knoten einer neuen bcc als negative Zahl notiert werden. D.h. abzugeben ist eine Funktion

bcc(int *nachbarschaftsliste, int startknoten, int *zweifachzusammenhangskomponenten)
 

Abgabe mit ausführlichen Kommentar und Namen bis 11.1. unter der email axel.kohnert@uni-bayreuth.de.
 
 
 

Aufgabe 17 Wegealgebra (3+3 Punkte)

Ein Hamiltonweg ist ein Weg der alle Knoten des Graphen genau einmal besucht und am Ausgangsknoten endet. Finde alle Hamiltonwege im folgenden Graphen

a) mit der Gauss Methode
b) mit der double sweep Methode