Größe der maximalen Übereinstimmung im zweigeteilten Diagramm

9

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

Ultrajohn
quelle

Antworten:

12

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)MG|M|=|C|CG

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

Geben Sie hier die Bildbeschreibung ein

Doch im Falle eines vollständigen bipartiten Graphen Ihre Aussage gilt.Kn,m

Nicholas Mancuso
quelle
9

|E|=0

U=u1,u2,...,un

V=v1,v2,...,vn

E=u1v1,u2v1,...unv1, v1u1,v2u1,...vnu1

Hugomg
quelle
natürlich. Mann, das nächste Mal muss ich versuchen, zuerst nachzudenken, bevor ich hier etwas frage.
Ultrajohn