in Beispiel 4.7.1 a) steht, man solle möglichst viele Paare unter Beachtung der Akzeptanz und des Bigamieverbots verheiraten, das sei dann ein bipartiter Graph... wenn ich mir nun aber die Abbildung 4.6 anschaue, ist das doch Bigamie vom Feinsten, oder sehe ich das falsch?
KE3 Bipartites Matching
Content
Comments
th-papa
Contributions on this page: 2
View profileIn Abbildung 4.6 bedeuten die duennen Linien moegliche matchings (Akzeptanz gegeben), aber
nur die dick gezeichnete Linie stellt auch ein matching dar. Wenn dieses vorgegeben ist, kannst
du eben keine weiteren hinzufuegen ohne das Bigamieverbot zu verletzen.
Ultimate1337
Contributions on this page: 2
View profileOk, das hab ich so weit verstanden, vielen Dank :)
Ist M in diesem Fall von maximaler Kardinalität, wenn der Knoten links oben mit dem rechts mittig und der Knoten links mittig mit dem rechts unten verknüpft ist?
th-papa
Contributions on this page: 2
View profileJa, so wuerd ich das auch matchen um das Maximum raus zu holen.