Größe der maximalen Übereinstimmung im zweigeteilten Diagramm

Stimmt meine Beobachtung, dass die Kardinalität der maximalen Übereinstimmung eines zweigeteilten Graphen G ( U , V , E ) immer gleich min ( | U | , | V | ) ist ?$M$$G(U, V, E)$$\min(|U|, |V|)$

Bei einem zweigeteilten Graphen und einer maximalen Übereinstimmung M von G sehen wir über den Satz von Konig, dass | M | = | C | wobei C eine minimale Scheitelpunktabdeckung für G ist . Ihre Aussage ist lediglich eine Obergrenze für die Größe des möglichen Abgleichs, keine strikte Gleichheit.$G = (U,V,E)$$M$$G$$|M| = |C|$$C$$G$

Das Bild auf der Wikipedia-Seite bietet ein schönes Gegenbeispiel zu Ihrer Behauptung. Wir sehen das , während min ( | U | , | V | ) = 7 .$|M| = 6$$\min(|U|,|V|) = 7$

Doch im Falle eines vollständigen bipartiten Graphen Ihre Aussage gilt.$K_{n,m}$

$|E| = 0$

$U = u_1, u_2, ..., u_n$

$V = v_1, v_2, ... , v_n$

$E = u_1v_1, u_2v_1, ... u_nv_1,$ $v_1u_1, v_2u_1, ... v_nu_1$