Seite 1 von 1

Programmieraufgabe: Starker Zusammenhang

Verfasst: 21. Jan 2016 15:49
von Stefan1992
Hallo,

muss denn der generierte Graph zwangsweise anti-symmetrisch sein? Oder kann es auch tatsächliche Rückkanten zwischen zwei Knoten geben?
Ich weiß noch nicht ganz, ob es mir letztendlich etwas bringt, falls einzelne Kanten symmetrisch sind, um den Graph stark zusammenhängend zu bekommen.

Ich hoffe, ich verrate im Folgenden nicht zu viel von einer möglichen Lösung.

Momentan bestimme ich zufällig die Position von n Knoten. Dann lege ich eine Triangulation über diese Knoten und erhalte somit einen "maximal" planaren Graphen. Die Richtung jeder Kante bestimme ich dann jeweils per Zufall.
Mein erster Ansatz, den erstellten Graphen stark zusammenhängend zu bekommen, war nun, einen Algorithmus zu schreiben, der testet, ob der Graph stark zusammenhängend ist. Damit lasse ich dann solange eine neue zufällige Richtungsbelegung der Kanten erzeugen, bis der Graph stark zusammenhängend ist. Offensichtlich ist an meinem Ansatz etwas falsch, da ich in eine Endlosschleife laufe und sich mir nicht eröffnet, warum dies nicht funktionieren sollte.

Bis zur Eigenschaft des starken Zusammenhangs habe ich den Triangulationsansatz verwendet, da ich somit eine feste Laufzeit des Algorithmus hatte und das Aussehen des Graphen trotzdem immer interessant variiert.
Doch nun frage ich mich, ob das die richtige Herangehensweise war, da ich massiv Probleme habe, den Graphen stark zusammenhängend zu bekommen.

Eine weitere Idee wäre jetzt, die starken Zusammenhangskomponenten zu bestimmen und lediglich Rückkanten für die einzelnen Komponenten zu erstellen.

Re: Programmieraufgabe: Starker Zusammenhang

Verfasst: 22. Jan 2016 10:30
von Prof. Karsten Weihe
Stefan1992 hat geschrieben: muss denn der generierte Graph zwangsweise anti-symmetrisch sein?
Ich habe mir noch einmal das PDF zur Programmieraufgabe aus moodle heruntergeladen, um sicherzustellen, dass ich exakt die Version vor Augen habe, die auch Sie sehen. Dort finde ich keine Treffer mit Suche nach "symm", aber folgenden Satz: "Der ZG [i.e. Zufallsgenerator] generiert einen gerichteten Graphen, der zu jeder vorhandenen Kante auch die Rückwärtskante enthält."

KW

Re: Programmieraufgabe: Starker Zusammenhang

Verfasst: 22. Jan 2016 10:48
von Stefan1992
Prof. Karsten Weihe hat geschrieben:"Der ZG [i.e. Zufallsgenerator] generiert einen gerichteten Graphen, der zu jeder vorhandenen Kante auch die Rückwärtskante enthält."
KW
Ah. Ich weiß nicht wieso. Aber irgendwie hatte ich das so verstanden, als müsste das dann "intern" und getrennt voneinander gespeichert werden, da es vielleicht für einen der zu implementierenden Algorithmen wichtig wäre (ich habe mir die Algorithmen noch nicht im Detail angeschaut).
Vielen Dank für Ihre Antwort!

Grüße