Shizmo
Tripel-As
Dabei seit: 16.10.2015
Beiträge: 174
|
|
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...
|
|
26.05.2016 22:31 |
|
|
Shizmo
Tripel-As
Dabei seit: 16.10.2015
Beiträge: 174
|
|
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
|
|
26.05.2016 23:39 |
|
|
Shizmo
Tripel-As
Dabei seit: 16.10.2015
Beiträge: 174
|
|
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) |
|
|
|
28.05.2016 00:32 |
|
|
|
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.
__________________ Syntax Highlighting fürs Board (Link)
|
|
28.05.2016 06:13 |
|
|
|
Shizmo
Tripel-As
Dabei seit: 16.10.2015
Beiträge: 174
|
|
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?
|
|
28.05.2016 13:58 |
|
|
Shizmo
Tripel-As
Dabei seit: 16.10.2015
Beiträge: 174
|
|
Hey danke fuer deine Antwort, aber egal was hier der Startknoten wäre, jeder hat Grad > 1 , aber es gibt keinen Artikulationspunkt.
|
|
28.05.2016 08:50 |
|
|
Shizmo
Tripel-As
Dabei seit: 16.10.2015
Beiträge: 174
|
|
Egal ob ungerichtet oder gerichtet?
Ich hab vergessen dazu zu schreiben, dass es sich um ungerichtete Graphen handelt.
|
|
28.05.2016 09:25 |
|
|
|
|
|