• "Studienservice.de, eine Seite von und für Fernstudenten der FernUni Hagen, ersetzt den Smalltalk in der Mensa" Handelsblatt Karriere

KE3 Bipartites Matching

Unser Sponsor SAP 4 Students
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?
 
In 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.
 
Ok, 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?
 
Oben