Ingat bahwa graf bipartit \(\GVE\) adalah graf yang simpul-simpulnya dapat diwarnai secara layak hanya dengan dua warna. Jelas bahwa pewarnaan semacam itu mempartisi \(V\) menjadi dua himpunan bebas \(V_1\) dan \(V_2\text{,}\) sehingga semua sisi berada di antara \(V_1\) dan \(V_2\text{.}\) Graf bipartit mempunyai banyak penerapan berguna, khususnya ketika kita memiliki dua jenis objek berbeda dan suatu hubungan yang hanya bermakna di antara objek-objek berlainan jenis. Sebagai contoh, misalkan terdapat sekumpulan pekerja dan sekumpulan pekerjaan yang dapat mereka lakukan. Kita dapat memandang para pekerja sebagai himpunan \(V_1\) dan pekerjaan sebagai \(V_2\text{,}\) lalu menambahkan sisi dari pekerja \(w\in V_1\) ke pekerjaan \(j\in V_2\) jika dan hanya jika \(w\) memenuhi syarat untuk mengerjakan \(j\text{.}\)
Jika \(\GVE\) suatu graf, himpunan \(M\subseteq E\) disebut pencocokan dalam \(\bfG\) apabila tidak ada dua sisi dalam \(M\) yang berbagi titik ujung. Jika \(v\) suatu simpul yang menjadi titik ujung sisi dalam \(M\text{,}\) kita mengatakan bahwa \(M\) menjenuhkan \(v\text{,}\) atau bahwa \(v\) dijenuhkan oleh \(M\text{.}\) Ketika \(\bfG\) bipartit dengan \(V=V_1\cup V_2\text{,}\) suatu pencocokan memasangkan simpul-simpul dalam \(V_1\) dengan simpul-simpul dalam \(V_2\) sedemikian sehingga tidak ada simpul yang dipasangkan dengan lebih dari satu simpul lain. Biasanya kita ingin mencari pencocokan maksimum, yaitu pencocokan yang memuat sebanyak mungkin sisi. Dalam graf bipartit, kita biasanya menetapkan himpunan \(V_1\) dan \(V_2\text{,}\) lalu mencari pencocokan maksimum dari \(V_1\) ke \(V_2\text{.}\) Dalam contoh pekerja dan pekerjaan, masalah pencocokan menjadi pencarian penugasan pekerja kepada pekerjaan sedemikian sehingga
setiap pekerja ditugaskan kepada pekerjaan yang memenuhi kualifikasinya (artinya, terdapat sebuah sisi),
Sebagai contoh, pada Gambar 14.3, sisi-sisi tebal membentuk pencocokan dari \(V_1\) ke \(V_2\text{.}\) Misalkan Anda adalah manajer para pekerja ini (di bagian bawah) dan harus menugaskan mereka kepada pekerjaan (di bagian atas). Apakah sumber daya benar-benar digunakan sebaik mungkin jika hanya empat dari enam pekerja yang mendapat pekerjaan? Tidak ada cara langsung untuk menambah jumlah pekerja yang bertugas, sebab dua pekerja yang saat ini belum mendapat tugas tidak mampu melakukan pekerjaan mana pun yang belum diberikan. Namun, mungkin terdapat penugasan yang lebih efisien jika beberapa penugasan diatur ulang. Jika ada, bagaimana cara menemukannya? Jika tidak ada, bagaimana Anda meyakinkan atasan bahwa tidak terdapat penugasan pekerja kepada pekerjaan yang lebih baik?
Pada akhir bagian ini, kita akan melihat secara singkat suatu teorema tentang pencocokan dalam graf bipartit yang memberi tahu secara tepat kapan terdapat penugasan pekerja kepada pekerjaan yang memastikan setiap pekerja memperoleh pekerjaan. Namun, mula-mula kita ingin melihat cara menggunakan aliran jaringan untuk mencari pencocokan maksimum dalam graf bipartit. Algoritma yang kita berikan cukup baik, tetapi bukan algoritma paling efisien yang diketahui bagi masalah ini sehingga kemungkinan tidak digunakan dalam praktik. Meskipun demikian, algoritma ini merupakan contoh yang baik tentang penggunaan aliran jaringan untuk menyelesaikan masalah kombinatorial. Jaringan yang kita gunakan dibentuk dari graf bipartit \(\bfG\) dengan menambahkan sisi dari sumber \(S\) ke setiap simpul \(V_1\) dan sisi dari setiap simpul \(V_2\) ke muara \(T\text{.}\) Sisi-sisi di antara \(V_1\) dan \(V_2\) diarahkan dari \(V_1\) ke \(V_2\text{,}\) dan setiap sisi diberi kapasitas \(1\text{.}\)Gambar 14.4 memuat jaringan yang bersesuaian dengan graf kita pada Gambar 14.2. Semua sisi dalam jaringan ini diarahkan dari bawah ke atas dan semuanya berkapasitas \(1\text{.}\) Simpul-simpul dalam \(V_1\) adalah \(x_1,\dots,x_6\) menurut urutan dari kiri ke kanan, sedangkan simpul-simpul dalam \(V_2\) adalah \(y_1,\dots, y_7\) dari kiri ke kanan.
Setelah menerjemahkan graf bipartit menjadi jaringan, kita perlu membahas kesesuaian antara pencocokan dan aliran jaringan. Untuk mengubah pencocokan \(M\) menjadi aliran jaringan, mula-mula kita menempatkan satu unit aliran pada sisi-sisi pencocokan tersebut. Agar alirannya sah, kita juga harus menempatkan satu unit aliran pada sisi-sisi dari \(S\) menuju simpul-simpul \(V_1\) yang dijenuhkan oleh \(M\text{.}\) Karena setiap simpul ini bersisian dengan tepat satu sisi dalam \(M\text{,}\) aliran keluar dari masing-masing simpul bernilai \(1\text{,}\) sama dengan aliran masuknya. Demikian pula, menyalurkan satu unit aliran menuju \(T\) dari setiap simpul \(V_2\) yang dijenuhkan oleh \(M\) memenuhi hukum kekekalan bagi simpul-simpul yang tersisa. Untuk arah sebaliknya, cukup perhatikan bahwa sisi-sisi penuh dari \(V_1\) ke \(V_2\) dalam aliran bernilai bulat membentuk suatu pencocokan. Jadi, kita dapat mencari pencocokan maksimum dari \(V_1\) ke \(V_2\) dengan menjalankan algoritma pelabelan pada jaringan terkait untuk memperoleh aliran maksimum.
Dengan barisan prioritas \(S,T,x_1,x_2,\dots,x_6,y_1,y_2,\dots,y_7\) sebagai pengganti urutan pseudoalfabetis yang biasa kita gunakan, algoritma pelabelan menghasilkan label-label berikut.
Karena kita sudah mengetahui bahwa aliran ini maksimum, kita juga ingin membuktikan bahwa pencocokan yang ditemukan bersifat maksimum. Lagi pula, atasan tidak akan senang jika kemudian mengetahui bahwa algoritma canggih yang Anda nyatakan menghasilkan penugasan optimal justru membiarkan pekerja kelima (\(x_5\)) tanpa pekerjaan, padahal keenam pekerja sebenarnya dapat ditugaskan. Mari kita periksa simpul mana saja yang diberi label oleh algoritma pelabelan Ford-Fulkerson pada pelaksanaan terakhir. Terdapat tiga simpul berlabel (\(x_3\text{,}\)\(x_4\text{,}\) dan \(x_5\)) dari \(V_1\text{,}\) tetapi hanya dua simpul berlabel (\(y_4\) dan \(y_5\)) dari \(V_2\text{.}\) Perhatikan bahwa \(y_4\) dan \(y_5\) merupakan satu-satunya simpul yang bertetangga dengan \(x_3\text{,}\)\(x_4\text{,}\) atau \(x_5\) dalam \(\bfG\text{.}\) Jadi, bagaimanapun kita memilih sisi pencocokan dari \(\{x_3,x_4,x_5\}\text{,}\) salah satu simpul tersebut akan tetap tidak jenuh. Dengan demikian, salah satu pekerja pasti tidak memperoleh pekerjaan. (Dalam contoh kita, pekerja itu adalah pekerja kelima, tetapi sisi pencocokan dapat dipilih secara berbeda sehingga salah satu pekerja lainlah yang tidak memperoleh tugas.)
Fenomena yang baru saja kita amati tidak hanya berlaku dalam contoh ini. Bahkan, dalam setiap graf bipartit \(\GVE\) dengan \(V=V_1\cup V_2\) yang tidak memiliki pencocokan yang menjenuhkan semua simpul \(V_1\text{,}\) kita akan menemukan konfigurasi serupa. Hal ini dinyatakan oleh teorema Hall yang terkenal, yang kita berikan berikut ini.
Misalkan \(\GVE\) suatu graf bipartit dengan \(V=V_1\cup V_2\text{.}\) Terdapat pencocokan yang menjenuhkan semua simpul \(V_1\) jika dan hanya jika, untuk setiap subhimpunan \(A\subseteq V_1\text{,}\) himpunan \(N\subseteq V\) yang terdiri atas tetangga simpul-simpul dalam \(A\) memenuhi \(|N|\geq |A|\text{.}\)
