ne da dürftest du richtig liegen... der graph war nicht bipartit und es war kein matching möglich.
Hallo,
die Aufgabe 5 aus der Klausur für Wirtschaftsinformatiker hat folgermaßen gelautet:
"Untersuche ob folgender Graph bipartit ist und ob es ein perfektes Matching gibt"
Somit waren zwei Aufgaben zu beantworten:
1) Bipartit Eigenschaft prüfen
2) Perfektes Matching finden
Zu 1) Bipartit Eigenschaft prüfen
Der Graph war bipartit!
Die Punkte auf der linken + rechten Seite haben eine Menge gebildet die nicht untereinander verbunden waren.
Die Punkte in der mittleren Spalte haben wiederum die Gegenmenge gebildet.
Wäre der Graph nicht bipartit hätten direkte Verbindungen zwischen Punkte der selben Menge existieren müssen.
Es gab aber keine senkrechte Verbindungen zwischen den Punkten oder Verbindungen von der linken zur rechten Seite. Alle Verbindungen sind also immer über die mittlere Spalte gelaufen, daher war die bipartit Eigenschaft des Graphen erfüllt.
Zu 2) Perfektes Matching finden
Es gab kein perfektes Matching, da drei Knoten aus der mittleren Menge sich auf zwei gleiche Knoten der restlichen Menge festgelegt haben.