Registrierung Kalender Mitgliederliste Teammitglieder Suche Häufig gestellte Fragen Zur Startseite

Informatiker Board » Suche » Suchergebnis » Hallo Gast [Anmelden|Registrieren]
Zeige Beiträge 1 bis 15 von 174 Treffern Seiten (12): [1] 2 3 nächste » ... letzte »
Autor Beitrag
Thema: Spannbaum
Shizmo

Antworten: 10
Hits: 6.250
01.06.2016 18:27 Forum: Algorithmen


Okay, vielen Dank smile
Thema: Spannbaum
Shizmo

Antworten: 10
Hits: 6.250
01.06.2016 16:50 Forum: Algorithmen


Zitat:
Original von eulerscheZahl
[...]
Das heißt aber, dass alle Knoten im Kreis in C liegen (oder in dessen Komplement).[...]


Hier komm ich leider nicht ganz mit, warum?
Thema: Spannbaum
Shizmo

Antworten: 10
Hits: 6.250
01.06.2016 09:54 Forum: Algorithmen


Zitat:
Original von eulerscheZahl
[...] Die größte Kante des Kreises würde dann aber nicht über den Schnitt gehen.


Ah ich glaub ich versteh schon, ich habe es so gemeint (Bild 1), aber das kann ja nicht sein oder? Weil der nördlichste und südlichste Knoten bereits eine Zusammenhangskomponente sind, richtig?? Also gibt es nur noch dieses Szenario (Bild 2).?
Thema: Spannbaum
Shizmo

Antworten: 10
Hits: 6.250
01.06.2016 09:39 Forum: Algorithmen


Aber angenommen es gibt bei deinem Beispielgraphen noch einen Knoten 5 der rechts in der Mitte ist und eine (gestrichelte) Kante nach 1 hat mit Gewicht 5. Dann wäre beim Schnitt ja 4 die leichteste Kante und es bildet sich ein Kreis. verwirrt
Thema: Spannbaum
Shizmo

Antworten: 10
Hits: 6.250
01.06.2016 09:18 Forum: Algorithmen


Danke für deine Antwort!!
Ich versteh nicht ganz wie du Kreise ausschließt, es gibt zwar immer nur eine eindeutige leichte Kante, aber die könnte beim Schnitt ja auch so liegen, dass sich ein Kreis bildet.?

Wenn das jetzt geklärt wäre, dann:
Zitat:
[...] nimm zwei nicht verbundene Teile und finde die leichteste Kante.


Wenn ich das (vermutlich |V|-1 mal) gemacht habe bin ich auch schon fertig oder?
Thema: Spannbaum
Shizmo

Antworten: 10
Hits: 6.250
Spannbaum 31.05.2016 23:52 Forum: Algorithmen


Hallo Wink

Zitat:
Gegeben ist ein ungerichteter gewichteter Graph G=(V,E). Zeigen Sie, dass G einen eindeutigen minimalen Spannbaum besitzt, wenn für jeden Schnitt (C,V-C) von G eine eindeutige leichte Kante existiert die (C,V-C) kreuzt.


Ich nehme gerne Vorschläge entgegen großes Grinsen großes Grinsen

LG
Thema: Zweifach zusammenhängend
Shizmo

Antworten: 20
Hits: 11.171
29.05.2016 12:20 Forum: Algorithmen


Ich glaub es hat grade klick gemacht.

Zitat:
Original von eulerscheZahl
Grundüberlegung:
Bei der Tiefensuche entsteht ein Baum.
[...]


Bin grad nochmal alles durchgegangen und habe mir Tiefensuchbäume aufgezeichnet und somit ist alles viel klarer geworden.

Vielen Dank für deine Hilfe!!!!
Thema: Zweifach zusammenhängend
Shizmo

Antworten: 20
Hits: 11.171
29.05.2016 10:35 Forum: Algorithmen


Okay, aber warum macht man das? Generell, was ist dieses lowlink?
Thema: Zweifach zusammenhängend
Shizmo

Antworten: 20
Hits: 11.171
29.05.2016 00:31 Forum: Algorithmen


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).

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:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
time = 0
isBiconnected = true

for each v in V
   v.color = weiß
   v.PI = NIL

BICONNECTED(startNode)


return isBiconnected
--------------------------

BICONNECTED(u)

u.color = gray
u.d = time
u.l = u.d

time++

for each v in Adj[u]
   if v.color == white
      v.PI = u
      MDFS-visit(v)

      /* Kleineren Low-Wert des Kindes uebernehmen. */
      u.l = min{u.l, v.l}

      /* u ist Artikulationspunkt */
      if v.l > u.d
         isBiconnected = false
         return

   /* Rueckwaertskante */
   if v.color == gray and u.PI != v
      /* Merken, welche am weitesten zurueck reicht. */
      u.l = min{u.l, v.d}

u.color = black
Thema: Zweifach zusammenhängend
Shizmo

Antworten: 20
Hits: 11.171
28.05.2016 18:45 Forum: Algorithmen


Hja, das glaub ich dir geschockt

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.
Thema: Zweifach zusammenhängend
Shizmo

Antworten: 20
Hits: 11.171
28.05.2016 14:31 Forum: Algorithmen


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)
Thema: Zweifach zusammenhängend
Shizmo

Antworten: 20
Hits: 11.171
28.05.2016 13:58 Forum: Algorithmen


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?
Thema: Zweifach zusammenhängend
Shizmo

Antworten: 20
Hits: 11.171
28.05.2016 09:25 Forum: Algorithmen


Egal ob ungerichtet oder gerichtet?
Ich hab vergessen dazu zu schreiben, dass es sich um ungerichtete Graphen handelt.
Thema: Zweifach zusammenhängend
Shizmo

Antworten: 20
Hits: 11.171
28.05.2016 08:50 Forum: Algorithmen


Hey danke fuer deine Antwort, aber egal was hier der Startknoten wäre, jeder hat Grad > 1 , aber es gibt keinen Artikulationspunkt. verwirrt

Thema: Zweifach zusammenhängend
Shizmo

Antworten: 20
Hits: 11.171
28.05.2016 00:32 Forum: Algorithmen


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. großes Grinsen

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)
Zeige Beiträge 1 bis 15 von 174 Treffern Seiten (12): [1] 2 3 nächste » ... letzte »