[Frage] 2-zusammenhängender Graph; Pseudocode [Archive]

View Full Version : [Frage] 2-zusammenhängender Graph; Pseudocode

Sensei

25-05-2003, 18:25

Hey!
Hab einen Algon in Pseudocode gemacht für 2-zusammenhängenden Graphen.
Anregungen/Beschwerden herzlich willkommen:

---------------------------------------------------------------
2-ZUSAMMENHÄNGEND_ODER_NICHT()

für alle v € V { markiert[v]==0}

für alle v € V {
/* lösche v aus V und inzidente Kanten */
V' = V\{v}
E = E \ {u,v} für alle u e V

für alle v € V' {
falls (markiert[v]==0) {
DFS(v)
}
Falls nicht (markiert(v)==1) für alle v € V' {
return "Nicht 2 zusammenhängend"
}
}
}
return "2-zusammenhängend"

---------------------------------------------------------------
DFS(v)

markiert[v]==1
für alle w € N(v) {
falls (markiert[v]==0) { DFS(w) }
}

Hab ich was falsch gemacht?

Wolfman

25-05-2003, 19:08

mmm du löscht einen knoten nach dem anderen aus dem baum und versucht danach von den restlichen knoten alle anderen zu erreichen aber das ist nicht 2 fach zusammenhägend....zweifach zusammenhängend bedeutet das man einen knoten v hat und der knoten x der sich auf v-1 und der knoten y also v+1 sich immer noch eine verbindung haben also das keine gelenk knoten existieren ein gelenkknoten ist jener knoten der wenn man man ihn aus der meng löscht den graphen in 2 komponeten teilt und eine graph ist 2 fach zusammen hängend wenn es erst durch die löschung von 2 knoten der graph in 2 komponten auf geteilt wird ....ich schätze so ca ist es aber ich werd mich mal dran versuchen

Sensei

25-05-2003, 19:16

Also im Skript steht nur dass G nach dem löschen eines Knotens aus V (und seiner Inzuidenten Kanten) immer noch zusammenhängend sein muss... und das hab ich hier überprüft denk ich. bin der meinung, dass es so passt.
Du immer mit deinen riesigen Definitionen aus Algorithmenbüchern ;) ... ich machs nur so wies im Skriptum is!
Übrigens ließ mal gaenau: deine Def. is eh die selbe wie meine... denk ich zumindest!

übrigens lösche ich nicht einen knoten nach dem anderen sondern immer einen knoten, dann einen anderen usw.
... und mein algo passt, sag ich :P

wolti

25-05-2003, 19:33

... und mein algo passt, sag ich :P

Denke ich auch. Du solltest aber vielleicht noch die Kanten welcher dieser Knoten v besitzt ebenfalls löschen, da du sonst ein Problem bekommen kannst wenn den Baum mit Hilfe von DFS traversiert.

V = V \ v
E = E \ {u,v} für alle u e V

Grüße,
Wolti

ps: Das mit E daher, da du ja N(v) verwendest, was aus E ermittelt wird. (Jetzt je nach Speicherung des Graphen)

Sensei

25-05-2003, 19:55

ok, wolti, hast recht in dem punkt; habs oben ausgebessert...

Spockman

26-05-2003, 21:20

the_unclean

26-05-2003, 21:34

Dieser Code gibt bei jedem Graph aus, dass er 2-zusammenhängend ist. Anstatt nach dem Entfernen eines Knotens DFS für alle Knoten aus V' aufzurufen, musst Du markiert[v] für alle v aus V' auf 0 setzen, dann für ein beliebiges w aus V' DFS(w) aufrufen. Wenn anschließend für alle x aus V' markiert[x] gleich 1 ist, kannst Du weiter machen, sonst ist der Graph sicher nicht 2-zusammenhängend.
da geb ich ihm recht, dein algo setzt keine markierung wieder auf 0, nachdem ein knoten gelöscht wurde,und nachdem DFS füpr alle Knoten ausgeführt wurde. Dann is v.markiert=1 natürlich für alle v € V nach dem ersten durchlauf, wenn der Graph vorher zusammenhängend war
oder seh ich das falsch?

Sensei

27-05-2003, 08:12

Könnte jemand den Code ausgebessert herschreiben? Danke im Voraus... bin im Moment zu müde und kann mich net konzentrieren.

the_unclean

27-05-2003, 15:00

---------------------------------------------------------------
2-ZUSAMMENHÄNGEND_ODER_NICHT()

für alle v € V {
/* lösche v aus V und inzidente Kanten */
V' = V\{v}
E = E \ {u,v} für alle u e V

für alle v € V' {
falls (markiert[v]==0) {
DFS(v)
}
Falls nicht (markiert(v)==1) für alle v € V' {
return "Nicht 2 zusammenhängend"
Setzte für alle v element V' markiert[v]==0}
}
}
}
return "2-zusammenhängend"

---------------------------------------------------------------
DFS(v)

markiert[v]==1
für alle w € N(v) {
falls (markiert[v]==0) { DFS(w) }
}

Hab ich was falsch gemacht?[/QUOTE]

so okay?
maz

Spockman

27-05-2003, 19:20

Du darfst DFS nicht für ALLE Knoten aus V' aufrufen, da dann automatisch herauskommen würde, dass der Graph 2-zusammenhängend "ist" (was er aber natürlich nicht sein muss!). Du nimmst Dir ein beliebiges w aus V' raus und führst für genau dieses DFS aus. Wenn Du dann alle anderen Knoten in V' erreicht hast, kannst Du weitermachen, sonst ist der Graph nicht 2-zusammenhängend.

für alle v € V {
/* lösche v aus V und inzidente Kanten */
V' = V\{v}
E = E \ {u,v} für alle u e V
für alle v aus V': markiert[v] = 0
für ein beliebiges w aus V': DFS(w)

Falls nicht (markiert(v)==1) für alle x € V':
return "Nicht 2 zusammenhängend"
}
return "2-zusammenhängend"

Sensei

27-05-2003, 19:38

2-ZUSAMMENHÄNGEND_ODER_NICHT()

für alle v € V {
/* lösche v aus V und inzidente Kanten */
V' = V\{v}
E = E \ {u,v} für alle u e V
für alle v aus V': markiert[v] = 0

für ein beliebiges w aus V': DFS(w)

Falls nicht (markiert(v)==1) für alle x € V':
return "Nicht 2 zusammenhängend"
}
return "2-zusammenhängend"

DFS(v)

markiert[v]==1
für alle w € N(v) {
falls (markiert[v]==0) { DFS(w) }
}

Passt das jetzt so? ich denke schon...