Subbab 14.3 Partisi Rantai

Dalam Bab 6, kita membahas Teorema Dilworth, yang menyatakan bahwa untuk setiap poset \(\bfP\) berlebar \(w\text{,}\) terdapat partisi \(\bfP\) menjadi \(w\) rantai, tetapi tidak menjadi lebih sedikit rantai. Namun, kita baru dapat menyusun algoritma untuk mencari partisi rantai ini (dan suatu antirantai maksimum) dalam kasus khusus ketika \(\bfP\) merupakan urutan interval. Sekarang, dengan bantuan aliran jaringan, kita dapat menyusun algoritma efisien yang berlaku secara umum bagi semua poset. Untuk melakukannya, kita memerlukan jaringan yang sedikit lebih rumit daripada jaringan pada bagian sebelumnya.

Misalkan titik-titik poset \(\bfP\) adalah \(\{x_1,x_2,\dots,x_n\}\text{.}\) Kita membangun jaringan dari \(\bfP\) yang terdiri atas sumber \(S\text{,}\) muara \(T\text{,}\) serta dua titik \(x'_i\) dan \(x''_i\) untuk setiap titik \(x_i\) dalam \(\bfP\text{.}\) Semua sisi dalam jaringan kita berkapasitas \(1\text{.}\) Kita menambahkan sisi dari \(S\) ke \(x'_i\) untuk \(1\leq i\leq n\) dan dari \(x''_i\) ke \(T\) untuk \(1\leq i\leq n\text{.}\) Tentu saja, jaringan ini belum terlalu berguna karena tidak memiliki sisi dari simpul beraksen prima tunggal ke simpul beraksen prima ganda. Untuk mengatasinya, kita menambahkan sisi berarah dari \(x'_i\) ke \(x''_j\) jika dan hanya jika \(x_i \lt x_j\) dalam \(\bfP\text{.}\)

Contoh yang kita gunakan sepanjang bagian ini adalah poset pada Gambar 14.8(a). Kita menyebut titik-titik poset sebagai \(x_i\text{,}\) dengan \(i\) angka yang tercetak di sebelah titik tersebut dalam diagram.

Langkah pertama ialah membuat jaringan yang ditampilkan pada Gambar 14.8(b). Dalam jaringan ini, semua kapasitas bernilai \(1\text{,}\) sisi-sisinya diarahkan dari bawah ke atas, baris pertama yang terdiri atas sepuluh simpul memuat \(x'_i\) secara berurutan dengan \(x'_1\) di sebelah kiri dan \(x'_{10}\) di sebelah kanan, sedangkan baris kedua yang juga terdiri atas sepuluh simpul memuat \(x''_i\) menurut urutan indeks yang meningkat. Untuk memahami pembentukan jaringan ini, perhatikan bahwa \(x_1\lt x_3\) dalam poset, sehingga terdapat sisi berarah \((x_1',x_3'')\text{.}\) Demikian pula, \(x_4\) lebih kecil daripada \(x_3\text{,}\) \(x_5\text{,}\) dan \(x_9\) dalam poset, sehingga terdapat tiga sisi berarah yang keluar dari \(x_4'\) dalam jaringan. Sebagai contoh ketiga, karena \(x_9\) maksimal dalam poset, tidak ada sisi berarah yang keluar dari \(x_9'\text{.}\)

Kita belum melihat cara mengubah aliran maksimum (atau potongan minimum) dalam jaringan yang baru dibangun menjadi partisi rantai minimum atau antirantai maksimum. Cara kerjanya akan lebih mudah dipahami setelah kita memperoleh aliran maksimum yang telah dipastikan. Alih-alih menjalankan algoritma pelabelan dari aliran nol, kita menaksir sebuah aliran, misalnya aliran pada Gambar 14.9. (Sekali lagi, kita menggunakan konvensi bahwa sisi tebal penuh, sedangkan sisi tipis kosong.)

Setelah membahas bagian yang sudah kita ketahui cara mengerjakannya, kita perlu menjelaskan cara menerjemahkan aliran dan potongan jaringan ini menjadi partisi rantai dan antirantai. Jika terdapat satu unit aliran pada sisi \((x_i',x_j'')\text{,}\) naluri pertama yang baik ialah menempatkan \(x_i\) dan \(x_j\) dalam rantai yang sama pada suatu partisi rantai. Agar berhasil, tentu kita perlu memastikan cara ini tidak menempatkan dua titik yang tak terbandingkan dalam satu rantai. Untuk melihat bahwa semuanya berjalan sebagaimana mestinya, bayangkan kita mulai dari \((x_i',x_j'')\text{,}\) lalu mencari aliran yang keluar dari \(x_j'\text{.}\) Jika ada, aliran itu menuju suatu simpul \(x_k''\text{,}\) sehingga kita dapat menambahkan \(x_k\) ke rantai karena \(x_i\lt x_j\lt x_k\text{.}\) Lanjutkan dengan cara ini sampai mencapai simpul jaringan yang tidak memiliki aliran keluar. Kemudian periksa apakah ada aliran yang masuk ke \(x_i''\text{.}\) Jika ada, aliran itu berasal dari simpul \(x_m'\text{,}\) yang dapat ditambahkan karena \(x_m\lt x_i\lt x_j\text{.}\)

Mari kita lihat bagaimana penerapan proses ini pada aliran dalam Gambar 14.10 menghasilkan partisi rantai. Jika kita mulai dari \(x_1'\text{,}\) terlihat bahwa \((x_1',x_3'')\) penuh, sehingga kita menempatkan \(x_1\) dan \(x_3\) dalam rantai \(C_1\text{.}\) Karena tidak ada aliran yang keluar dari \(x_3'\text{,}\) tidak terdapat elemen yang lebih besar untuk ditambahkan ke rantai. Namun, \(x_1''\) menerima aliran dari \(x_2'\text{,}\) sehingga kita menambahkan \(x_2\) ke \(C_1\text{.}\) Selanjutnya terlihat bahwa \(x_2''\) menerima aliran dari \(x_7'\text{,}\) sehingga sekarang \(C_1=\{x_1,x_2,x_3,x_7\}\text{.}\) Tidak ada aliran yang masuk ke simpul \(x_7''\text{,}\) sehingga pembangunan rantai pertama berhenti. Simpul pertama yang belum ditempatkan dalam rantai adalah \(x_4\text{.}\) Karena \((x_4',x_5'')\) penuh, kita menempatkan \(x_4\) dan \(x_5\) dalam rantai \(C_2\text{.}\) Kemudian kita memeriksa \(x_5'\) dan tidak menemukan aliran keluar. Namun, terdapat aliran yang masuk ke \(x_4''\) dari \(x_6'\text{,}\) sehingga \(x_6\) ditambahkan ke \(C_2\text{.}\) Tidak ada aliran yang masuk ke \(x_6''\text{,}\) sehingga \(C_2=\{x_4,x_5,x_6\}\text{.}\) Sekarang titik pertama yang belum berada dalam rantai adalah \(x_8\text{,}\) sehingga kita menggunakan aliran dari \(x_8'\) ke \(x_9''\) untuk menempatkan \(x_8\) dan \(x_9\) dalam rantai \(C_3\text{.}\) Sekali lagi, tidak ada aliran yang keluar dari \(x_9'\text{,}\) sehingga kita memeriksa \(x_8''\text{,}\) yang menerima aliran dari \(x_{10}'\text{.}\) Penambahan \(x_{10}\) ke \(C_3\) menghasilkan \(C_3=\{x_8,x_9,x_{10}\}\text{.}\) Karena setiap titik kini berada dalam suatu rantai, kita dapat berhenti.