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