Wie lautet die maximale Anzahl perfekter Machtings in einem vollständigen paaren Graphen ?

1 Antwort

Sei {U,V} die Partition des Graphen in seiner zwei unabhängigen Komponenten (ich habe den genauen Begriff vergessen, aber du weißt hoffentlich, was ich meine). Seien m := |U| und n := |V|.

Lemma. in einem vollständigen bipartiten Graphen G mit Partition {U,V} sind die Matching 1 zu 1 durch die injektiven partiellen Funktionen ƒ : A ⟶ B mit A ⊆ U und B ⊆ V. 

Folgerung. in einem vollständigen bipartiten Graphen G mit Partition {U,V} sind die Matching 1 zu 1 durch die maximalen (bzgl. Funktionerweiterungen) injektiven partiellen Funktionen ƒ : A ⟶ B mit A ⊆ U und B ⊆ V. Falls G endlich (sodass U, V endlich sind) und |U| ≤ |V|, so gilt dies nur dann, wenn A=U.

Mithilfe dieser Charakterisierung können wir aufzählen:

Fall 1. |U| ≤ |V|. Dann v(G) = # Inj. Funktionen ƒ : U ⟶ V. Dies ist gleich n! / (n–m)!.

Fall 2. |V| ≤ |U|. Durch Symmetrie v(G) = # Inj. Funktionen ƒ : V ⟶ U. Dies ist gleich m! / (m–n)!

In allen Fällen gilt v(G) = Max{m,n}! / |m–n|!

Was möchtest Du wissen?