Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
--- Praktische Informatik (http://www.informatikerboard.de/board/board.php?boardid=6)
---- Algorithmen (http://www.informatikerboard.de/board/board.php?boardid=17)
----- Zweifach zusammenhängend (http://www.informatikerboard.de/board/thread.php?threadid=3057)
Geschrieben von Shizmo am 26.05.2016 um 22:31:
Zweifach zusammenhängend
Hallo, ich soll einen Algorithmus in Pseudocode angeben, der einen Graphen prüft, ob er zweifach zusammenhängend ist oder nicht.
Ich bin mir noch nicht ganz sicher, wie es am einfachsten ist, dies zu prüfen. Erst dachte ich mir es würde reichen, wenn ich prüfe, dass jeder Knoten mindestens 2 Ausgangskanten hat, aber das reicht nicht. Also irgendwie muss es immer ein Kreis sein. Hmm...
Geschrieben von eulerscheZahl am 26.05.2016 um 23:11:
Mit
Tarjan findest du Artikulationspunkte und zweifache Zusammenhangskomponenten in Zeit O(|V|+|E|).
Geschrieben von Shizmo am 26.05.2016 um 23:39:
Danke für deine Antwort.
Die Laufzeit ist in dem Fall egal, ich werde den morgen mal durchgehen und versuchen zu verstehen.
Aber hast du vllt noch eine Idee, auf welche Eigenschaften ich noch überprüfen muss.
Wollte es eigtl auf der Basis von DFS oder so machen, falls das überhaupt möglich ist.
LG
Geschrieben von eulerscheZahl am 27.05.2016 um 21:05:
Tarjan basiert auf einer Tiefensuche.
Ein sehr primitiver Algorithmus, der auch prüft, ob ein Graph zweifach zusammenhängend ist:
| code: |
1:
2:
3:
4:
5:
|
Für jedes Knotenpaar s,t in G:
finde einen Weg von s nach t
G' = G ohne Knoten auf Weg zwischen s und t
wenn s und t in G' nicht mehr verbunden sind, ist der Graph nicht zweifach zusammenhängend, also gib FALSCH zurück
gib WAHR zurück |
|
Geschrieben von Shizmo am 28.05.2016 um 00:32:
Hallo, danke für deine Antwort, hab mir jetzt den Tarjan-Algorithmus etwas angeschaut und hab eine etwas abgespecktere Version entdeckt und diese noch etwas bearbeitet.
Mein Problem ist allerdings, dass der Startknoten nicht überprüft wird und immer wenn er bei diesem am Ende angelangt, false ausgibt. Ansonsten könnte es evtl funktionieren.
| code: |
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
|
//Initialisieren
for each n in G
n.visited = false
n.dfs = NIL
n.lowlink = NIL
n.PI = NIL
counter = 0
findArtPoint(start)
//Eigentliches Programm
findArtPoint(Vertex v)
v.visited = true
v.dfs = counter++
v.lowlink = v.dfs
for each w in Adj[v]
if (! w.visited) {
w.PI = v
findArtPoint(w);
if (w.lowlink >= v.dfs)
return false
else if (v.PI != w)
v.lowlink = Minimum(v.lowlink, w.dfs) |
|
Geschrieben von eulerscheZahl am 28.05.2016 um 06:13:
Wenn der Startknoten einen Grad > 1 hat, ist er Artikulationspunkt. Das liegt daran, dass die Teiläste untereinander nicht verbunden sind und deshalb jeder Weg von einem Ast zum anderen über den Startknoten laufen muss.
Du musst also nur noch den Grad des Startknotens prüfen.
Geschrieben von Shizmo am 28.05.2016 um 08:50:
Hey danke fuer deine Antwort, aber egal was hier der Startknoten wäre, jeder hat Grad > 1 , aber es gibt keinen Artikulationspunkt.
Geschrieben von eulerscheZahl am 28.05.2016 um 08:59:
Du darfst nur die Vorwärtskanten zählen. Wenn die Wurzel mehr als eine nicht gestrichelte Kante hat, dann ist sie ein Artikulationspunkt.
Geschrieben von Shizmo am 28.05.2016 um 09:25:
Egal ob ungerichtet oder gerichtet?
Ich hab vergessen dazu zu schreiben, dass es sich um ungerichtete Graphen handelt.
Geschrieben von eulerscheZahl am 28.05.2016 um 09:28:
Bei der Tiefensuche machst du daraus einen gerichteten Graphen.
Dass es um einen ungerichteten Graphen geht war klar. Sonst würde es starke Zusammenhangskomponente heißen, nicht zweifache.
Beim gerichteten Graphen kommen noch mehr Kantentypen hinzu: Crosskanten (zwischen den Zusammenhangskomponenten) und Vorwärtskanten, die über mehrere Knoten gehen.
Geschrieben von Shizmo am 28.05.2016 um 13:58:
| Zitat: |
Original von eulerscheZahl
[...]
Du musst also nur noch den Grad des Startknotens prüfen. |
Hast du einen Vorschlag, wie ich das in den bisjetzigen Pseudocode implementieren könnte?
Geschrieben von eulerscheZahl am 28.05.2016 um 14:04:
So zum Beispiel
| code: |
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
|
//Initialisieren
for each n in G
n.visited = false
n.dfs = NIL
n.lowlink = NIL
n.PI = NIL
n.outDegree = 0
counter = 0
bool biconnected = !findArtPoint(start) && start.outDegree == 1
//Eigentliches Programm
findArtPoint(Vertex v)
v.visited = true
v.dfs = counter++
v.lowlink = v.dfs
for each w in Adj[v]
if (! w.visited) {
w.PI = v
n.outDegree++
findArtPoint(w);
if (w.lowlink >= v.dfs)
return false
else if (v.PI != w)
v.lowlink = Minimum(v.lowlink, w.dfs) |
|
edit: du solltest vielleicht auch noch irgendwann true zurückgeben.
Geschrieben von Shizmo am 28.05.2016 um 14:31:
Hmm, also Zeile 24 soll v.outDegree++ heißen oder?
Wenn ich aber so einen Graph habe (Anhang) wird false returned und der StartKnoten hat zu dem Zeitpunkt auch den outDegree-Wert = 1, also true, was aber nicht stimmt. (Der linke Knoten ist der Startknoten)
Geschrieben von eulerscheZahl am 28.05.2016 um 18:37:
Ja, das hätte ein v werden sollen.
Wo ist denn das Problem bei deinem Graphen (tut mir leid, ich bin gerade denkfaul nach 2.5h
Programmierwettbewerb).
Geschrieben von Shizmo am 28.05.2016 um 18:45:
Hja, das glaub ich dir
Linker Knoten = A, mittlerer B und rechter Knoten = C.
A.visited = true
A.dfs = 1
A.lowlink = 1
B.Pi = A
A.outDegree = 1
B.visited = true
B.dfs = 2
B.lowlink = 2
C.Pi = B
B.outDegree = 1
C.visited = true
C.dfs = 3
C.lowlink = 3
if (C.lowlink >= B.dfs) (3>2) => return false
=> bool biconnected = true && start.outDegree == 1
Also true.
Aber der Graph ist nicht biconnected.
Forensoftware: Burning Board, entwickelt von WoltLab GmbH