Matching dan Marriage Theorem (Teorema Hall)

Masalah pencocokan (matching) berkaitan dengan pemilihan sisi-sisi pada graf sedemikian sehingga tidak ada dua sisi yang berbagi titik yang sama, khususnya pada konteks graf bipartit.

1. Graf Bipartit & Matching

Definisi (Graf Bipartit & Matching)

Sebuah graf $G = (X \cup Y, E)$ dikatakan bipartit jika himpunan titik $V$ dapat dipartisi menjadi dua himpunan $X$ dan $Y$ sedemikian sehingga setiap sisi menghubungkan satu titik di $X$ dan satu titik di $Y$ .

Sebuah matching $M$ adalah subhimpunan sisi $E$ di mana tidak ada dua sisi di $M$ yang bertemu pada titik yang sama. Sebuah complete matching dari $X$ ke $Y$ adalah matching yang mencakup setiap titik di $X$ .

2. Teorema Hall (Marriage Theorem)

Teorema (Teorema Hall (Marriage Theorem))

Misalkan $G = (X \cup Y, E)$ adalah graf bipartit. Terdapat complete matching yang menjenuhkan setiap titik di $X$ jika dan hanya jika untuk setiap subhimpunan $S \subseteq X$ , berlaku:

$∣ N (S) ∣ \geq ∣ S ∣$

di mana $N (S)$ adalah himpunan tetangga dari semua titik di $S$ (neighborhood set).

Contoh Soal & Pembahasan

Contoh (Aplikasi Teorema Hall)

Sebuah perusahaan memiliki 5 lowongan ( $J_{1} \dots J_{5}$ ) dan 5 pelamar ( $P_{1} \dots P_{5}$ ). Data kualifikasi:

$P_{1}, P_{2}, P_{3} \to {J_{1}, J_{2}}$
$P_{4} \to {J_{3}, J_{4}, J_{5}}$
$P_{5} \to {J_{2}, J_{5}}$

Mungkinkah semua pelamar mendapatkan pekerjaan yang sesuai?

Latihan Soal

✏️ Latihan Soal 1 (Perfect Matching pada Graf Reguler)

Buktikan bahwa setiap graf bipartit $k$ -reguler dengan $k \geq 1$ selalu memiliki perfect matching.

💡 Tampilkan Pembahasan / Solusi

▾

Pembahasan:

Pembahasan:

Berdasarkan Handshaking Lemma, $k ∣ X ∣ = k ∣ Y ∣ ⟹ ∣ X ∣ = ∣ Y ∣$ .
Untuk setiap $S \subseteq X$ , jumlah sisi keluar dari $S$ adalah $k ∣ S ∣$ .
Sisi-sisi ini harus berakhir di $N (S)$ . Kapasitas maksimal sisi yang dapat diterima $N (S)$ adalah $k ∣ N (S) ∣$ .
Maka $k ∣ S ∣ \leq k ∣ N (S) ∣ ⟹ ∣ S ∣ \leq ∣ N (S) ∣$ . Syarat Hall terpenuhi untuk semua $S$ . $■$

Navigasi Sub-Topik

← Sub-Topik Sebelumnya: Graf Eulerian dan Graf Hamiltonian
Sub-Topik Selanjutnya: Fungsi Pembangkit Biasa →

Matching dan Marriage Theorem (Teorema Hall)

1. Graf Bipartit & Matching

2. Teorema Hall (Marriage Theorem)

Contoh Soal & Pembahasan

Latihan Soal

Navigasi Sub-Topik

Materi Terkait (Linked References) (2)

Fungsi Pembangkit Biasa (Ordinary GF)

Graf Eulerian dan Graf Hamiltonian

Diskusi & Tanya Jawab

Title