Zweifach zusammenhängend |
26.05.2016, 22:31 | Auf diesen Beitrag antworten » | |||||
Shizmo | 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... |
|||||
|
||||||
26.05.2016, 23:11 | Auf diesen Beitrag antworten » | |||||
eulerscheZahl | Mit Tarjan findest du Artikulationspunkte und zweifache Zusammenhangskomponenten in Zeit O(|V|+|E|). |
|||||
26.05.2016, 23:39 | Auf diesen Beitrag antworten » | |||||
Shizmo | 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 |
|||||
27.05.2016, 21:05 | Auf diesen Beitrag antworten » | |||||
eulerscheZahl | Tarjan basiert auf einer Tiefensuche. Ein sehr primitiver Algorithmus, der auch prüft, ob ein Graph zweifach zusammenhängend ist:
|
|||||
Anzeige | ||||||
|
||||||
28.05.2016, 00:32 | Auf diesen Beitrag antworten » | |||||
Shizmo | 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.
|
|||||
28.05.2016, 06:13 | Auf diesen Beitrag antworten » | |||||
eulerscheZahl | 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. |
|||||
28.05.2016, 08:50 | Auf diesen Beitrag antworten » | |||||
Shizmo | 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:59 | Auf diesen Beitrag antworten » | |||||
eulerscheZahl | Du darfst nur die Vorwärtskanten zählen. Wenn die Wurzel mehr als eine nicht gestrichelte Kante hat, dann ist sie ein Artikulationspunkt. |
|||||
28.05.2016, 09:25 | Auf diesen Beitrag antworten » | |||||
Shizmo | Egal ob ungerichtet oder gerichtet? Ich hab vergessen dazu zu schreiben, dass es sich um ungerichtete Graphen handelt. |
|||||
28.05.2016, 09:28 | Auf diesen Beitrag antworten » | |||||
eulerscheZahl | 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. |
|||||
28.05.2016, 13:58 | Auf diesen Beitrag antworten » | |||||
Shizmo |
Hast du einen Vorschlag, wie ich das in den bisjetzigen Pseudocode implementieren könnte? |
|||||
28.05.2016, 14:04 | Auf diesen Beitrag antworten » | |||||
eulerscheZahl | So zum Beispiel
edit: du solltest vielleicht auch noch irgendwann true zurückgeben. |
|||||
28.05.2016, 14:31 | Auf diesen Beitrag antworten » | |||||
Shizmo | 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) |
|||||
28.05.2016, 18:37 | Auf diesen Beitrag antworten » | |||||
eulerscheZahl | 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). |
|||||
28.05.2016, 18:45 | Auf diesen Beitrag antworten » | |||||
Shizmo | 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. |
|||||
28.05.2016, 19:23 | Auf diesen Beitrag antworten » | |||||
eulerscheZahl | Kann es sein, dass ich einfach die Negation falsch gesetzt habe? Mein Gedanke war: wenn findArtPoint true zurückgibt, hat der Graph einen Artikulationspunkt. Jetzt gibt der Algorithmus aber false zurück, wenn ein Artikulationspunkt gefunden wird. |
|||||
29.05.2016, 00:31 | Auf diesen Beitrag antworten » | |||||
Shizmo | Wird keiner gefunden gibt er aber auch ein false zurück und start.outDegree ist immer 1. Ich hab grad gemerkt, dass mir dieser Minimum-Vergleich fehlt, vermutlich klappt es deswegen nicht. Versteh aber auch nicht ganz für was der ist. Hab mal eine andere Version, die funktioniert soweit, allerdings nicht für einen trivialen Graph (also mit nur zwei Knoten).
|
|||||
29.05.2016, 07:34 | Auf diesen Beitrag antworten » | |||||
eulerscheZahl |
Es kann sein, dass ein Knoten mehrere Rückkanten hat. Dann sprichst du immer so weit zurück nach oben wie möglich. |
|||||
29.05.2016, 10:35 | Auf diesen Beitrag antworten » | |||||
Shizmo | Okay, aber warum macht man das? Generell, was ist dieses lowlink? |
|||||
29.05.2016, 10:46 | Auf diesen Beitrag antworten » | |||||
eulerscheZahl | Grundüberlegung: Bei der Tiefensuche entsteht ein Baum. Es kann auch keine Querverbindung zwischen den Ästen mit gleicher Wurzel geben. Betrachten wir zwei Knoten u und v: es gibt einen Weg von u nach v, der durch die Tiefensuche gefunden wurde. Wenn es aber keinen anderen Weg gibt, um von v aus wieder über u zu kommen, ist u ein Artikulationspunkt (der einzige Weg von Knoten oberhalb von u nach v führt eben über u). lowlink gibt an, wie weit man maximal zurück nach oben kommt. Kommt man nicht höher als bis u, ist u ein Artikulationspunkt. Sag Bescheid, wenn du meine Vorlesungsmitschrift willst. Da ist der Beweis ausführlicher. |
|||||
29.05.2016, 12:20 | Auf diesen Beitrag antworten » | |||||
Shizmo | Ich glaub es hat grade klick gemacht.
Bin grad nochmal alles durchgegangen und habe mir Tiefensuchbäume aufgezeichnet und somit ist alles viel klarer geworden. Vielen Dank für deine Hilfe!!!! |
|
Verwandte Themen
Die Beliebtesten » |
Die Größten » |
Die Neuesten » |