matching pada graf bipartit

Untuk setiap himpunan S dari simpul di G. Didefinisikan neighbour S di G sebagai himpunan semua simpul yang bertetangga dengan sisi di S. Susunan ini dinotasikan N(S). Maka G merupakan sebuah graf bipartit dengan partisi (X,Y). Dalam banyak aplikasinya kita berharap menemukan sebuah matching dari G yang saturates setiap simpul di X.

Teorema 2.2 (Hall, 1935) Misal G adalah graf bipartit dengan partisi (X,Y). Maka G mengandung sebuah matching saturates setiap simpul di X jika dan hanya jika │N(S)│≥ │S│ untuk setiap S ⊆ X. (2.2)

Bukti : Asumsikan G mengandung matching M yang saturates tiap simpul di X, misalkan S adalah subset X. Karena tiap simpul di S matched ke simpul di N(S) dalam M, kita jelas mempunyai │N(S)│≥ │S│.

Kebalikannya, asumsikan bahwa G adalah sebuah graf bipartit memenuhi teorema (2.2), dan misalkan G tidak mempunyai matching yang saturates tiap simpul di X. Ambil kontradiksi, misalkan M* menjadi matching maksimum dari G. M* tidak semua matching saturated di X. Misal u sebuah M*–Unsaturated simpul di X. Misal Z adalah himpunan semua simpul yang terhubung dengan u dengan lintasan M*–alternating. Karena M* adalah sebuah matching maksimum, oleh teorema (2.1) Bahwa u adalah satu – satunya simpul M*–Unsaturated dalam Z. Misal S = Z ∩ X dan T = Z ∩ Y

Jelas, S\{u} matching pada M* dengan simpul di T. Oleh karena itu

│T│ = │S│- 1 (2.3)

Dan N(S) T. Jadi

N(S) = T (2.4)

Karena setiap simpul di N(S) terhubung pada u oleh lintasan M*–alternating.

(2.3) dan (2.4) Mengimplikasikan bahwa

│N(S)│=│S│ – 1 < │S│

Terjadi kontadiksi asumsi (2.2)

Pembuktian diatas menyediakan sebuah dasar algoritma yang baik untuk menemukan sebuah matching maksimum dalam sebuah graf bipartit, algoritma tersebut algoritma Hungarian.

Corollary Jika G adalah k–regular graf bipartit dengan k > 0, maka G mempunyai matching sempurna.

Bukti. Misal G adalah k–regular bipartit dengan partisi (X,Y). Karena G k–regular, k│X│=│E│= k│Y│, karena k > 0, sehingga│X│=│Y│. Misal S himpunan bagian dari X dan misalkan E₁ dan E₂ himpunan sisi incident dengan simpul di S dan N(S). Oleh definisi N(S), E₁ ⊆ E₂ dan oleh karena itu

k│N(S)│=│ E₂│≥│ E₁│= k │S│

Mengikuti │N(S)│ ≥│S│ karena teorema 2.2 G mempunyai matching M–saturating setiap simpul di X. maka│X│=│Y│, M adalah matching sempurna.