 3D-Matching und Max-Flow |
Damasus
Grünschnabel
Dabei seit: 02.08.2013
Beiträge: 2
 |
|
Guten morgen zusammen,
ich interessiere mich, ohne eine relavanten Hintergrund, für folgendes Problem. Es geht um die Probleme 3D-Matching (NP-vollständig) und Max-Flow (liegt in P).
Angenommen ich habe nun ein 3D-Matching Problem vor mir liegen (Mengen X, Y, Z). Was ist der Unterschied zu Max-Flow? Könnte ich nicht einfach eine Quelle und Senke einfügen. Quelle mit den Elementen aus X verbinden und die Senke mit Elementen aus Z. Als Kapazität wähle ich 1 und die Elemente aus Y verdoppele ich und füge eine Kante mit Kapazität 1 dazu, d.h. ich garantiere damit, dass nur eine Einheit über diesen Knoten geht (Stichwort: Knotenkapazität). Nun bestimme ich den maximalen Fluss.
Irgendwo ist natürlich ein Denkfehler, aber wo? Oder ist P=NP? ;-p
|
|
02.08.2013 10:07 |
|
|
ed209
Routinier
Dabei seit: 07.09.2006
Beiträge: 324
|
|
Hi Damasus,
Bei solchen Problemen ist es immer gut, die Definitionen mit anzugeben, oder zu verlinken. Ich bezieh mich mal auf die Definitionen der englischen Wikipedia: https://en.wikipedia.org/wiki/3-dimensional_matching und https://en.wikipedia.org/wiki/Maximum_flow_problem
Um Dich zu widerlegen brauchen wir nur ein einziges Gegenbeispiel bei dem dein Problem und das Problem auf das du abbildest nicht dasselbe Ergebnis hervorbringen. Das hier ist das simpelste 3D-Matching Problem auf das ich gekommen bin.
X = (x0, x1), Y = (y0, y1) und Z = (z0, z1)
T = { (x0, y0, z0), (x0, y1, z1), (x1, y1, z0) }
Da jeweils zwei Tripel immer eine Überschneidung haben, enthält das beste Matching nur ein Tripel.
Wenn wir das jetzt nach deiner Methode (wenn ich sie richtig verstanden habe) auf ein Maxflow problem abbilde, dann ist der Maxflow 2
Gruß,
ED
|
|
|
03.08.2013 16:01 |
|
|
Damasus
Grünschnabel
Dabei seit: 02.08.2013
Beiträge: 2
|
|
Das ist natürlich absolut richtig. Vielen Dank dafür schonmal.
Siehst du eine Verbindung zwischen den zwei Problemen? Ist das 3D-Matching in irgendeiner Form eine Verallgemeinerung des Max-Flow Problems oder sind das doch zwei ganz unterschiedliche Probleme?
|
|
|
04.08.2013 12:03 |
|
|
ed209
Routinier
Dabei seit: 07.09.2006
Beiträge: 324
|
|
Hi
Wenn man ein bisschen in der Wikipedia schnüffel ist das 3D Matching eine erweiterung vom Bipartite Graph Matching problem, das in der tat auf Maxflow abgebildet werden kann.
https://en.wikipedia.org/wiki/Bipartite_...ipartite_graphs
Aber im Endeffekt bleibt 3D Matching NP-Schwer und Maxflow liegt in P, da wirst du nicht so schnell auf eine Lösung kommen. (Ja ich hab es in meiner Jugend auch probiert zu zeigen daß P = NP oder das Gegenteil, aber es hat nie egklappt 
)
ED
|
|
|
04.08.2013 14:58 |
|
|
|
