Maximales bipartites Matching < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
Hallo zusammen!
Ich überlege schon seit einiger Zeit, wie man mit dem Edmond-Karp Algorithmus das maximale gewichtete bipartite Matching (MGBM) berechnen kann. Leider weiß ich nicht mehr weiter und hoffe, dass mir jemand aus der Mathematik, der sich ein wenig mit Graphtheorie der Informatik beschäftigt hat, weiterhelfen kann.
Also Gegeben ein Graph G(A+B,E), zwei Knotenmengen A und B, sowie Kanten E mit gewichten [mm] W_e.
[/mm]
Das MGBM Problem kann ja auf das max-flow problem reduziert werden, in dem man zwei neue Knoten s,t einführt, kapazitäten der Kanten auf 1 und die Kantengewichte auf [mm] -W_e [/mm] setzt.
Mir ist die funktionsweise, die ja auf den Ford-Fulkerson (FF) basiert, schon einigermaßen klar. Der Unterschied zum FF besteht ja darin, dass der Weg mittels BFS gesucht und der kürzeste gewählt wird. Das Problem hierbei ist ja zunächst, dass alle Wege gleich lang sind. Welchen wählt man dann. Wenn man stupide nach Greedy immer den leichtesten wählt, so bekommt man nicht die optimale Lösung :-(
Also wie muss ich da vorgehen. Hoffentlich weiß das jemand!!
Vielen Dank!!
Biomaster
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:20 So 30.07.2006 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
