Mathematik online lernen im Mathe-Forum. Nachhilfe online
Startseite » Forum » Perfekte Matchings im Vollständigen Graphen

Perfekte Matchings im Vollständigen Graphen

Universität / Fachhochschule

Graphentheorie

Tags: Graphentheorie

 
Antworten Neue Frage stellen Im Forum suchen
Neue Frage
SebiMath

SebiMath aktiv_icon

22:19 Uhr, 23.06.2016

Antworten
Hallo,
Ich weiß das die Anzahl der perfekten Matchings im Vollständigen Graphen K2n gegeben ist als 2n!n!*2n. Jetzt würde ich aber auch noch gerne wissen warum das so ist, in meiner Literatur steht kein Beweis oder ähnliches.

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich benötige bitte nur das Ergebnis und keinen längeren Lösungsweg."
Online-Nachhilfe in Mathematik
Antwort
pwmeyer

pwmeyer aktiv_icon

07:50 Uhr, 24.06.2016

Antworten
Hallo,

eine Erklärung ist:

Nummeriere die Knoten, bilde alle Permutationen -(2n)! Möglichkeiten und definiere das Matching durch Paar in diese Reihenfolge

(k1,k2,k3,k4,k5,.....)→{{k1,k2},{k3,k4},...

Jedes Paar wird doppelt erfasst - als (k1,k2) und (k2,k1)- also ist durch 2n zu dividieren. Die Reihenfolge innerhalb des Matchings ist egal, daher Division durch n!

Alternativ geht auch Induktion.

Gruß pwm
Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.