Rozmiar maksymalnego dopasowania na wykresie dwudzielnym

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

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$ .

Jednak w przypadku pełnego dwuczęściowego wykresu $K_{n,m}$ Twoja instrukcja jest w posiadaniu.

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 = 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$