Anzahl perfekte Matchings |
16.06.2016, 11:11 | petaaa | Auf diesen Beitrag antworten » | ||
Anzahl perfekte Matchings Hallo, ich bräuchte einen kleinen Tipp bei folgendem Beispiel. Ich soll zeigen, dass die Anzahl der perfekten Matching im vollständigen Graph mit 2n Knoten, ist. Meine Ideen: Also meine Überlegung wäre folgendes. Ich habe eine Menge von 2n Knoten. Jeden davon muss ich einen anderen Knoten zuordnen. Und ich suche nach der Anzahl der verschiedenen Möglichkeiten wie ich das tun kann. Das ist doch dann die Anzahl der fixpunktfreien Permutationen der Menge [2n]. Für [n] haben wir diese schon mal durch das Inklusion-Exklusion-Prinzip berechnet, nämlich Wie komme ich jetzt aber davon, auf Oder stimmt meine Überlegung überhaupt nicht? |
||||
16.06.2016, 12:41 | HAL 9000 | Auf diesen Beitrag antworten » | ||
Ist eigentlich sehr leicht mit Permutationen mit Wiederholung erklärbar: Wir haben Farben und wir wollen jede Farbe genau zweimal verwenden, um die Knoten zu färben. Dann gibt es genau solche Färbungen. Da aber bei einem solchen gefundenen Matching eine Permutation der n Farben untereinander nichts an den Paarungen an sich ändert, sind jeweils dieser Färbungen im Matching-Sinne identisch, damit muss noch durch diese Farbenpermutationszahl dividiert werden: .
Der Zusammenhang erschließt sich mir in keinster Weise. |
||||
16.06.2016, 15:43 | petaaa | Auf diesen Beitrag antworten » | ||
Ja, danke! Diese Erklärung verstehe ich! Bin mittlerweile schon draufgekommen, dass meine Überlegung mit den Permutationen nicht wirklich funktionieren kann. |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|