Graph/Einzelne Kanten/Bipartite Strukturen/Aufgabe/Kommentar

Sei ${}\{u_{1},v_{1}\},\dots ,\{u_{m},v_{m}\}$ die ${}m$ disjunkte Kanten von ${}G$. Zu bestimmen ist die Anzahl der bipartiten Zerlegungen

$\{u_{1},v_{1},\dots ,u_{m},v_{m}\}=A\uplus B.$

Man beachte, dass bei einer solchen Zerlegung die Reihenfolge von ${}A$ und ${}B$ keine Rolle spielt, d.h. ie Zerlegungen ${}A\uplus B$ und ${}B\uplus A$ werden als gleich angesehen.

Um eine Zerlegung zu finden, muss man nur einen Knotenpunkt jeder Kante betrachten: Ist ${}u_{i}\in A$, dann ist ${}v_{i}\in B$ und umgekehrt. Also entspricht jede Zerlegung einer Verteilung von ${}\{u_{1},\dots ,u_{m}\}$ auf ${}A$ und ${}B$. Da jedes ${}u_{i}$ entweder in ${}A$ oder ${}B$ sein kann, gibt es insgesamt ${}2^{m}$ Verteilungen. Die Anzahl der bipartiten Zerlegungen ist also ${}2^{m}/2=2^{m-1}$, da die Reihenfolge von ${}A$ und ${}B$ keine Rolle spielt.

Offensichtlich besitz der Graph nur eine optimale Paarung, die alle ${}m$ Kanten enthält.

Zur kommentierten Aufgabe