Rozmiar maksymalnego dopasowania na wykresie dwudzielnym

9

Czy w mojej obserwacji mam rację, że liczność maksymalnego dopasowania M wykresu dwudzielnego G(U,V,E) jest zawsze równy min(|U|,|V|)?

ultrajohn
źródło

Odpowiedzi:

13

Biorąc dwudzielny wykres G=(U,V,E) a maksymalna dopasowanie M z G poprzez Koniga twierdzenia widzimy |M|=|C|gdzie C jest minimalna pokrywa wierzchołek o G . Twoje stwierdzenie stanowi jedynie górną granicę wielkości możliwego dopasowania, a nie ścisłą równość.

Obraz na stronie wikipedii stanowi miły kontrprzykład dla twojego roszczenia. Widzimy, że |M|=6 , podczas gdy min(|U|,|V|)=7 .

wprowadź opis zdjęcia tutaj

Jednak w przypadku pełnego dwuczęściowego wykresu Kn,m Twoja instrukcja jest w posiadaniu.

Nicholas Mancuso
źródło
9

Nie. Na przykład rozważmy przypadek, w którym obie strony są rozłączone lub przypadek, w którym duża grupa węzłów jest połączona z tym samym pojedynczym węzłem:|E|=0

U=u1,u2,...,un

V=v1,v2,...,vn

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

hugomg
źródło
oczywiście. człowieku, następnym razem muszę najpierw pomyśleć, zanim o coś zapytam.
ultrajohn