Matematika Diskret Sebuah Pengantar Terbuka, Edisi Keempat

Kita mengakhiri bab ini dengan satu contoh tambahan masalah teori graf untuk menggambarkan keragaman dan keluasan bidang tersebut.

Misalkan Anda memiliki graf bipartit \(G\text{.}\) Graf ini terdiri atas dua himpunan simpul \(A\) dan \(B\text{,}\) dengan sejumlah sisi yang menghubungkan beberapa simpul dalam \(A\) dengan beberapa simpul dalam \(B\) (dan, tentu saja, tidak ada sisi di antara dua simpul yang keduanya berada dalam \(A\) atau keduanya berada dalam \(B\)). Pencocokan dari \(A\) adalah subhimpunan sisi sedemikian sehingga setiap simpul \(A\) bersisian dengan tepat satu sisi dalam subhimpunan itu, dan tidak ada simpul dalam \(B\) yang bersisian dengan lebih dari satu sisi dalam subhimpunan tersebut. Dalam penerapannya, kita akan mengasumsikan bahwa \(|A| = |B|\) (kedua himpunan memiliki jumlah simpul yang sama), sehingga setiap simpul pada graf bersisian dengan tepat satu sisi dalam pencocokan.

¹¹

Apa yang kita sebut pencocokan kadang-kadang disebut pencocokan sempurna atau pencocokan lengkap. Istilah tersebut digunakan karena pencocokan yang tidak sempurna juga menarik untuk dipelajari. Kita akan menyebutnya pencocokan parsial.

Sedikit konteks dapat mempermudah pemahaman. Anggap simpul-simpul dalam \(A\) merepresentasikan mahasiswa dalam suatu kelas, dan simpul-simpul dalam \(B\) merepresentasikan topik presentasi. Kita menempatkan sisi dari simpul \(a \in A\) ke simpul \(b \in B\) jika mahasiswa \(a\) ingin mempresentasikan topik \(b\text{.}\) Tentu saja, beberapa mahasiswa ingin mempresentasikan lebih dari satu topik, sehingga simpul mereka akan berderajat lebih dari 1. Sebagai pengajar, Anda ingin memberikan satu topik tersendiri kepada setiap mahasiswa. Jadi, Anda ingin menemukan pencocokan dari \(A\text{:}\) Anda memilih suatu subhimpunan sisi sedemikian sehingga setiap mahasiswa dipasangkan dengan tepat satu topik, dan tidak ada topik yang dipasangkan dengan dua mahasiswa.

¹²

Dahulu, contoh baku untuk pencocokan adalah masalah perkawinan, dengan \(A\) terdiri atas para lelaki di suatu kota, \(B\) terdiri atas para perempuan, dan suatu sisi merepresentasikan perkawinan yang disetujui kedua pihak. Pencocokan kemudian merepresentasikan cara para tetua kota menikahkan semua orang di kota tersebut, tanpa memperbolehkan poligami. Demi kepekaan politis, kita memilih konteks yang lebih progresif.

Pertanyaannya adalah: kapan suatu graf bipartit memuat pencocokan dari \(A\text{?}\) Untuk mulai menjawab pertanyaan ini, perhatikan hal-hal yang dapat menghalangi suatu graf memuat pencocokan. Pengamatan ini belum tentu memberi kita syarat yang menjamin bahwa graf memang memiliki pencocokan, tetapi setidaknya merupakan titik awal.

Salah satu alasan \(G\) tidak dapat memiliki pencocokan ialah adanya simpul dalam \(A\) yang tidak bertetangga dengan simpul mana pun dalam \(B\) (sehingga berderajat 0). Apa lagi yang dapat menghalanginya? Bagaimana jika dua mahasiswa sama-sama hanya menyukai satu topik yang sama? Setelah topik tersebut diberikan kepada mahasiswa pertama, tidak ada lagi topik yang disukai mahasiswa kedua, sehingga keadaannya sama saja seolah-olah mahasiswa kedua berderajat 0. Atau, bagaimana jika tiga mahasiswa hanya menyukai dua topik di antara mereka? Sekali lagi, setelah satu mahasiswa diberi suatu topik, keadaan ini berkurang menjadi kasus sebelumnya, yaitu dua mahasiswa hanya menyukai satu topik. Penalaran ini dapat diteruskan untuk semakin banyak mahasiswa.

Sekarang seharusnya jelas bahwa jika terdapat sekelompok \(n\) mahasiswa yang secara bersama-sama menyukai paling banyak \(n-1\) topik, maka pencocokan mustahil dibentuk. Pernyataan ini berlaku untuk setiap nilai \(n\) dan setiap kelompok yang terdiri atas \(n\) mahasiswa.

Untuk menyatakannya dalam bahasa teori graf, misalkan Anda memiliki himpunan simpul \(S \subseteq A\text{.}\) Definisikan \(N(S)\) sebagai himpunan semua tetangga dari simpul-simpul dalam \(S\text{.}\) Dengan kata lain, \(N(S)\) memuat semua simpul (dalam \(B\)) yang bertetangga dengan sedikitnya satu simpul dalam \(S\text{.}\) (Dalam graf mahasiswa/topik, \(N(S)\) adalah himpunan topik yang disukai mahasiswa-mahasiswa dalam \(S\text{.}\)) Pembahasan di atas dapat diringkas sebagai berikut.

Apakah konversnya benar? Misalkan \(G\) memenuhi syarat pencocokan \(|N(S)| \ge |S|\) untuk semua \(S \subseteq A\) (setiap himpunan simpul memiliki tetangga yang jumlahnya paling sedikit sama dengan jumlah simpul dalam himpunan tersebut). Apakah ini berarti bahwa suatu pencocokan ada? Ternyata, ya. Syarat perlu yang jelas tersebut juga merupakan syarat cukup.

¹³

Hal semacam ini sering terjadi dalam teori graf. Jika contoh-contoh penyangkal yang jelas dapat dihindari, kita sering memperoleh hasil yang diinginkan.

Teorema ini pertama kali dibuktikan oleh Philip Hall pada 1935.

¹⁴

Terdapat pula versi tak hingga dari teorema ini, yang dibuktikan oleh Marshall Hall, Jr. Kesamaan nama mereka hanyalah kebetulan; kedua Hall tersebut tidak memiliki hubungan keluarga.

Terdapat cukup banyak pembuktian yang berbeda untuk teorema ini – pencarian singkat di internet dapat menjadi titik awal.

Selain penerapannya pada masalah perkawinan dan topik presentasi mahasiswa, pencocokan memiliki berbagai macam penerapan. Kita mengakhiri pembahasan dengan salah satu contohnya.