Graphentheorie < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:19 Mo 16.06.2008 | | Autor: | Gitarist |
| Aufgabe | | Algorithmus zu berechnung von minimalem Schnitt in gerichteten Graphen |
Hallo!
Ich würde gerne ein Algorithmus wissen, der mir einen minimalen Schnitt im gerichteten Graphen liefert. Graph ist ungewichtet.
Vielen Dank im Voraus !!!
|
|
| |
|
Hallo Gitarist! (falls du übrigens den Gitarrenspieler meinst, dann musst du dich bitte mit zwei "r" schreiben...)
> Ich würde gerne ein Algorithmus wissen, der mir einen
> minimalen Schnitt im gerichteten Graphen liefert. Graph ist
> ungewichtet.
Wofür brauchst du das denn? Und was für Kenntnisse hast du? Ich denke, nach dem Max-Flow-Min-Cut-Theorem dürfte dir jeder Algorithmus, der einen maximalen Fluss berechnet, helfen. Du kannst einfach zwei Knoten als Quelle und Senke hinzu definieren und alle Kantenkosten auf 1 setzen, das sollte genau dein Problem sein. (sofern ich mich nicht vertue, bin schon wieder ein bisschen aus dem Thema raus...)
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 08:45 Di 17.06.2008 | | Autor: | bazzzty |
> > Ich würde gerne ein Algorithmus wissen, der mir einen
> > minimalen Schnitt im gerichteten Graphen liefert. Graph ist
> > ungewichtet.
>
> Wofür brauchst du das denn? Und was für Kenntnisse hast du?
> Ich denke, nach dem Max-Flow-Min-Cut-Theorem dürfte dir
> jeder Algorithmus, der einen maximalen Fluss berechnet,
> helfen. Du kannst einfach zwei Knoten als Quelle und Senke
> hinzu definieren und alle Kantenkosten auf 1 setzen, das
> sollte genau dein Problem sein. (sofern ich mich nicht
> vertue, bin schon wieder ein bisschen aus dem Thema
> raus...)
Du irrst. So bekommt man nur einen minimalen s-t-Schnitt für das gewählte Quelle/Senke-Paar. Ein minimaler Schnitt im Graphen muß ja nicht genau diese beiden separieren. Und selbst wenn: Ein Schnitt auf einem gerichteten Graphen ist nicht symmetrisch definiert. Gezählt werden nur vorwärts geschnittene Kanten. Die einfachste Lösung ist natürlich, einfach alle (geordneten) Paare als Quelle und Senke durchzuprobieren, das wären dann quadratisch viele Anwendungen eines Flußmaximierungsalgos Deiner Wahl (Ford&Fulkerson, Edmonds&Karp, Goldberg&Tarjan usw).
Ich bin mir nicht sicher, was es da noch "maßgeschneidertes" gibt. Für ungerichtete Graphen gibt es z.B. den Algorithmus von Stoer und Wagner, aber für gerichtete Graphen fällt mir spontan nix ein.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:32 Di 17.06.2008 | | Autor: | Gitarist |
Hallo, Leute !!!
Danke schön für die schnelle Antwort!!! Hat mich sehr gefreut!
Das Probelm ist, z. B. Ford-Fulkenson, wie setze ich die Flusskosten auf die Kanten? Die Kantenkosten setze ich auf 1 und muss dann jeden Knoten einzeln betrachten, und zwar, wieviel reinfließt und wieviel rausfließt. Und dementsprechend setze ich dann die Flusskosten ein? Oder wie geht das?
Um Schnitt in gerichteten Graphen grob auszurechnen, habe ich schon die Paare gezält und diejenigen rausgenommen, die am häufigsten drankammen. Algorithmus hat expotenzielle Laufzeit. So macht man das eben nicht. Also die Frage bleibt offen: Ich nabe zwei ausgezeichnete Knoten, und möchte den minimalen Schnitt ausrechnen, wie geht das? In ungerichteten Graphen geht's einfach...
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 15:04 Di 17.06.2008 | | Autor: | bazzzty |
Mir wird leider immer unklarer, was Dein Problem ist.
Um einen minimalen s-t-Schnitt zu gegebenen s und t zu berechnen, berechnest Du einen maximalen Fluß (z.B. mit Ford-Fulkerson) und machst dann eine Erreichbarkeitssuche im Residualgraphen. Kantenkapazitäten sind überall eins, Knotenkapazitäten oder Kosten gibt es keine. Was davon ist unklar?
|
|
|
| |
|
mein Problem ist, dass ich nicht weiss, wie man zu den Kanten Flusskosten assoziiert. wie geht das? wir haben ungewichteten Graph, aber was sind die Flusskosten? wo bekomme ich die?
|
|
|
| |
|
wir müssen beim Ford-Fulkenson augmentierenden Weg berechnen, aber woher weiss ich, was meine Flusskosten sind? :))
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:14 Di 17.06.2008 | | Autor: | Gitarist |
Leute, ich glaube, mein Problem ist, dass ich nicht verstanden habe, wie man den Fluss vom Anfang an überhaupt berechnet. könnt ihr mir das bitte erklären? besten Dank im voraus!!!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 09:33 Mi 18.06.2008 | | Autor: | bazzzty |
Den Eindruck habe ich auch.
Gegeben ist ein gerichteter Graph mit zwei ausgezeichneten Knoten s,t (oder q,s), und Kantenkapazitäten. Dann berechnet man mit Ford-Fulkerson (siehe auch ![[]](/images/popup.gif) Wikipedia) einen maximalen Fluß.
Kantenkosten, Knotenkapazitäten oder Knotenkosten sind alles zusätzliche Einschränkungen an Flußprobleme, die hier gar nichts zu suchen haben.
Lies Dir mal den Wikipedia-Eintrag zu FF durch, klarer kann ich das sicher nicht erklären.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:08 Mi 09.07.2008 | | Autor: | Gitarist |
Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
Hallo Leute!!!
Es geht immer noch um die Berechnung des maximalen Flusses. Wie implementiert man das den? Z.B folgendes:
1 ford_fulkerson(G, s, t) {
2 foreach (Kante (u,v) 2 E)} {
3 f[u,v] = 0; f[v,u] = 0
4 }
5
6 while (p = tiefensuche_pfad(s t, Gf)) {
7kapazität_p=min(restkapazität(u,v): (u,v) 2 p)
8
9 foreach (Kante (u,v) 2 p) {
10 f[u,v] = f[u,v] + kapazit¨at_p
11 f[v,u] = -f[u,v]
12 }
13 }
14
15 return f
16 }
Ist zwar im Pseudocode, aber nirgendwo werden die Rüchkanten definiert.
Meine Frage ist: wie sage ich dem Rechner, dass neue Kanten - Rückkanten im Graphen aufgetaucht sind? Muss man die neuen Kanten -Rüchkanten zum Graphen extra hinzufügen? Oder wie geht das?
Um eine Antwort werde ich euch sehr Dankbar !!!!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 10:03 Do 10.07.2008 | | Autor: | bazzzty |
Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
> Es geht immer noch um die Berechnung des maximalen Flusses.
> Wie implementiert man das den? Z.B folgendes:
>
> 1 ford_fulkerson(G, s, t) {
> 2 foreach (Kante (u,v) 2 E)} {
> 3 f[u,v] = 0; f[v,u] = 0
> 4 }
Okay, Du hast also ein ungerichtetes Netzwerk, d.h. auf einer Kante kann theoretisch in beiden Richtungen was fließen, sehe ich das richtig? Andernfalls brauchst Du sowieso nur einen Flußwert f[u,v].
Ich würde aber unabhängig davon nur eine Variable verwenden, nämlich f[u,v], die dann einen Wert zwischen -Kantenkapazität und +Kantenkapazität annimmt. Im einfachsten Fall, wenn jede Kante nur einfach genutzt werden kann also zwischen -1 und 1.
> 6 while (p = tiefensuche_pfad(s t, Gf)) {
Hier liegt der Hund begraben. Du suchst im Residualgraphen [mm]G_f[/mm]. Entweder Du beschreibst den explizit oder Du mußt die Tiefensuche selbst schreiben, und zwar so, daß die Tiefensuche nur Kanten vorwärts verwendet, bei denen [mm]f[u,v]-Kapazitaet[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
. Wenn sich der Fluß verändert, stehen damit automatisch "neue" Kanten zur Verfügung, und die Differenz ist jeweils auch Schranke an die Pfadkapazität.
> 7kapazität_p=min(restkapazität(u,v): (u,v) 2 p)
> 8
> 9 foreach (Kante (u,v) 2 p) {
> 10 f[u,v] = f[u,v] + kapazit¨at_p
> 11 f[v,u] = -f[u,v]
> 12 }
> 13 }
Wie gesagt, ich würde schon die Nutzung der f[u,v] und f[v,u] überdenken.
|
|
|
| |
|
| Aufgabe | | mehrfache Kanten, minimaler Schitt |
Danke schön!!!!!!!!!! Vielen Dank!!!!
Was passiert, wenn ich mehrfache Kanten habe? Was mache ich dann? Geht das überhaupt? Eigentlich habe ich als Ausgangsgraph einen gerichteten ungewichteten Graphen mit ausgezeichneten Knoten "S" und "T", also sind meine Kantenkapazitäten alle gleich 1. Und wie gehe ich damit um? Und wie komme ich im Endeffekt auf meinen minimalen Schnitt in meinem ungewichteten gerichteten Graphen mit Mehrfachkanten?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 02:36 Fr 11.07.2008 | | Autor: | Gitarist |
Hallo noch mal!
ich glaube, ich hab' alles verstanden, bis auf das Problem mit mehfachen Kanten. wie gehe ich damit um? wenn ich einen ungewichteten Graphen habe und mehrfache Kanten, dann kann ich praktisch solche Kanten duch eine ersetzen und das Gewicht dieser Kante zuordnen, ist das richtig??
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:22 Sa 12.07.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:20 Do 19.06.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:20 Do 19.06.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
