Lewati ke konten utama

Subbab 16.1 Algoritma Daring

Banyak penerapan kombinatorika berlangsung secara dinamis dan daring. Jarang sekali kita memiliki semua informasi tentang tantangan suatu masalah sebelum keadaan memaksa kita mengambil keputusan. Sebagai contoh, keputusan untuk melanjutkan proyek konstruksi besar harus dibuat beberapa tahun sebelum pembangunan dimulai; keputusan investasi dibuat berdasarkan informasi hari ini dan mungkin tampak sangat tidak bijaksana setelah berita esok tersedia; dan keputusan untuk melompat keluar dari pesawat dengan parasut jarang dapat dibatalkan.
Dalam bagian ini, kita menyajikan dua contoh untuk menggambarkan masalah daring dalam konteks kombinatorial. Contoh pertama berkaitan dengan pewarnaan graf. Sebagaimana lazim dalam pembahasan algoritma daring, kita meninjau permainan dua orang dengan pemain yang disebut Pemberi Warna dan Pembangun. Kedua pemain terlebih dahulu menyepakati suatu kelas graf \(\cgC\text{,}\) lalu permainan berlangsung dalam serangkaian ronde. Pada ronde \(1\text{,}\) Pembangun menyajikan satu simpul dan Pemberi Warna memberinya sebuah warna. Pada setiap ronde berikutnya, Pembangun menyajikan simpul baru dan memberikan informasi lengkap tentang simpul-simpul terdahulu yang bertetangga dengannya. Selanjutnya, Pemberi Warna harus memberi simpul baru itu warna yang berbeda dari semua warna yang sebelumnya ia berikan kepada tetangga-tetangganya.

Contoh 16.1.

Bahkan jika Pembangun dibatasi untuk membangun lintasan dengan \(4\) simpul, Pemberi Warna dapat dipaksa menggunakan tiga warna. Pada Ronde 1, Pembangun menyajikan simpul \(x\) dan Pemberi Warna mewarnainya. Pada Ronde 2, Pembangun menyajikan simpul \(y\) dan menyatakan bahwa \(x\) dan \(y\) tidak bertetangga.
Sekarang Pemberi Warna memiliki pilihan. Ia dapat memberi \(x\) dan \(y\) warna yang sama, atau memilih warna baru untuk \(y\text{.}\) Jika Pemberi Warna memberi \(x\) dan \(y\) warna yang berbeda, maka pada Ronde 3 Pembangun menyajikan simpul \(z\) dan menyatakan bahwa \(z\) bertetangga dengan \(x\) maupun \(y\text{.}\) Pemberi Warna kini terpaksa menggunakan warna ketiga pada \(z\text{.}\) Pada Ronde \(4\text{,}\) Pembangun menambahkan simpul \(w\) yang bertetangga dengan \(y\text{,}\) tetapi tidak dengan \(x\) ataupun \(z\text{;}\) namun, kerugiannya sudah terjadi.
Sebaliknya, jika Pemberi Warna memberi \(x\) dan \(y\) warna yang sama, maka pada Ronde 3 Pembangun menyajikan simpul \(z\text{,}\) dengan \(z\) bertetangga dengan \(x\text{,}\) tetapi tidak dengan \(y\text{.}\) Pemberi Warna harus menggunakan warna kedua pada \(z\text{,}\) yang berbeda dari warna yang ia berikan kepada \(x\) dan \(y\text{.}\) Pada Ronde 4, Pembangun menyajikan simpul \(w\) yang bertetangga dengan \(z\) dan \(y\text{,}\) tetapi tidak dengan \(x\text{.}\) Pemberi Warna harus menggunakan warna ketiga pada \(w\text{.}\)
Perhatikan bahwa lintasan merupakan pohon, dan pohon merupakan hutan. Hasil berikut menunjukkan bahwa meskipun hutan mudah diwarnai secara luring, kita menghadapi tantangan nyata ketika harus bekerja secara daring. Untuk membantu mencatat warna-warna yang digunakan Pemberi Warna, kita memakai notasi dari Bab 5 dan menulis \(\phi(x)\) untuk warna yang diberikan Pemberi Warna kepada simpul \(x\text{.}\)

Bukti.
Ketika \(n=1\text{,}\) Pembangun cukup menyajikan satu simpul. Ketika \(n=2\text{,}\) dua simpul yang bertetangga sudah cukup. Ketika \(n=3\text{,}\) Pembangun membangun lintasan dengan \(4\) simpul sebagaimana diuraikan dalam Contoh 16.1. Sekarang andaikan bahwa untuk suatu \(k\ge3\text{,}\) Pembangun memiliki strategi \(S_i\) yang memaksa Pemberi Warna menggunakan \(i\) warna pada hutan dengan paling banyak \(2^{i-1}\) simpul, untuk setiap \(i=1,2,\dots,k\text{.}\) Berikut cara Pembangun memaksa penggunaan \(k+1\) warna.
Pertama, untuk setiap \(i=1,2,\dots,k\text{,}\) Pembangun mengikuti strategi \(S_i\) guna membangun hutan \(F_i\) dengan paling banyak \(2^{i-1}\) simpul tempat Pemberi Warna dipaksa menggunakan \(i\) warna. Selain itu, apabila \(1\le i\lt j\le k\text{,}\) tidak ada sisi antara simpul-simpul dalam \(F_i\) dan simpul-simpul dalam \(F_j\text{.}\)
Selanjutnya, Pembangun memilih sebuah simpul \(y_1\) dari \(F_1\text{.}\) Karena Pemberi Warna menggunakan dua warna pada \(F_2\text{,}\) terdapat simpul \(y_2\) dalam \(F_2\) sehingga \(\phi(y_2)\neq \phi(y_1)\text{.}\) Karena Pemberi Warna menggunakan tiga warna pada \(F_3\text{,}\) terdapat simpul \(y_3\) dalam \(F_3\) sehingga semua warna dalam \(\{\phi(y_1),\phi(y_2),\phi(y_3)\}\) berbeda. Dengan demikian, Pembangun dapat memilih simpul-simpul \(y_1,y_2,\dots,y_k\) dengan \(y_i\in F_i\) sedemikian sehingga warna-warna \(\phi(y_i)\) memenuhi \(\phi(y_i)\neq \phi(y_j)\) apabila \(i\neq j\text{.}\) Pembangun kemudian menyajikan simpul baru \(x\) dan menyatakan bahwa \(x\) bertetangga dengan semua simpul dalam \(\{y_1,y_2,\dots,y_k\}\text{,}\) tetapi tidak dengan simpul lainnya. Jelas bahwa graf yang dihasilkan merupakan hutan, dan Pemberi Warna terpaksa memakai warna untuk \(x\) yang berbeda dari \(k\) warna yang sebelumnya ia berikan kepada simpul-simpul dalam \(\{y_1,y_2,\dots, y_k\}\text{.}\) Selain itu, jumlah seluruh simpul paling banyak \(1+[1+2+4+8+\dots+2^{k-1}]=2^k\text{.}\)

Diskusi 16.3.

Bob membaca bukti tersebut dan bertanya apakah kasus \(k=2\) dan \(k=3\) benar-benar perlu ditangani secara terpisah. Bukankah cukup dengan mencatat bahwa kasus \(k=1\) berlaku secara sepele? Carlos mengatakan ya.

Subbagian 16.1.1 Memperoleh Hasil yang Cukup Baik dalam Lingkungan Daring

Teorema 16.2 sebaiknya dipandang sebagai hasil negatif. Sulit membayangkan keluarga graf yang lebih mudah diwarnai daripada hutan, tetapi dalam lingkungan daring graf-graf dalam keluarga ini sulit diwarnai. Di sisi lain, dalam keadaan tertentu kita dapat memperoleh hasil yang cukup baik secara daring: mungkin tidak sebaik hasil luring yang benar-benar optimal, tetapi cukup baik untuk berguna. Di sini kita menyajikan contoh yang sangat elegan mengenai himpunan terurut parsial.
Ingat bahwa poset \(P\) bertinggi \(h\) dapat dipartisi menjadi \(h\) antirantai—dengan secara rekursif menghapus himpunan elemen minimal. Namun, berapa banyak antirantai yang diperlukan dalam lingkungan daring? Sekarang Pembangun membangun poset \(P\) satu titik demi satu, sedangkan Pemberi Warna membangun partisi \(P\) menjadi antirantai. Pada setiap ronde, Pembangun menyajikan titik baru \(x\) dan mencantumkan titik-titik terdahulu yang masing-masing lebih kecil daripada \(x\text{,}\) lebih besar daripada \(x\text{,}\) dan tak terbandingkan dengan \(x\text{.}\) Selanjutnya, Pemberi Warna menempatkan \(x\) ke dalam suatu antirantai. Hal ini dilakukan dengan menambahkan \(x\) ke antirantai yang sudah memuat satu atau lebih titik terdahulu, atau dengan menempatkan \(x\) dalam antirantai baru.

Bukti.
Penting untuk dicatat bahwa Pemberi Warna tidak perlu mengetahui nilai \(h\) terlebih dahulu. Sebagai contoh, Pembangun mungkin merencanakan bahwa pada akhirnya nilai \(h\) akan menjadi \(300\text{,}\) tetapi informasi ini tidak memengaruhi strategi Pemberi Warna.
Ketika titik baru \(x_n\) memasuki \(P\text{,}\) Pemberi Warna menghitung nilai \(r\) dan \(s\text{.}\) Di sini \(r\) adalah bilangan bulat terbesar sehingga terdapat rantai \(C\) dengan \(r\) titik dalam \(\{x_1,x_2,\dots,x_n\}\) yang mempunyai \(x_n\) sebagai elemen terkecilnya. Demikian pula, \(s\) adalah bilangan bulat terbesar sehingga terdapat rantai \(D\) dengan \(s\) titik dalam \(\{x_1,x_2,\dots,x_n\}\) yang mempunyai \(x_n\) sebagai elemen terbesarnya. Pemberi Warna lalu menempatkan \(x_n\) dalam himpunan \(A(r,s)\text{,}\) dengan klaim bahwa setiap dua titik dalam himpunan ini tak terbandingkan. Untuk melihat bahwa klaim tersebut benar, tinjau saat pertama ketika Pembangun menyajikan titik baru \(x\text{,}\) Pemberi Warna menempatkan \(x\) dalam \(A(r,s)\text{,}\) dan sudah terdapat titik \(y\) dalam \(A(r,s)\) sedemikian sehingga \(x\) dan \(y\) terbandingkan.
Ketika \(y\) disajikan, pada saat itu terdapat rantai \(C'\) dengan \(r\) titik yang mempunyai \(y\) sebagai elemen terkecilnya. Terdapat pula rantai \(D\) dengan \(s\) titik yang mempunyai \(y\) sebagai elemen terbesarnya.
Sekarang andaikan \(y>x\) dalam \(P\text{.}\) Kita dapat menambahkan \(x\) ke \(C'\) untuk membentuk rantai dengan \(r+1\) titik yang mempunyai \(x\) sebagai elemen terkecilnya. Hal ini menyiratkan bahwa \(x\) tidak ditempatkan dalam \(A(r,s)\text{.}\) Demikian pula, jika \(y\lt x\) dalam \(P\text{,}\) kita dapat menambahkan \(x\) ke \(D\) untuk membentuk rantai dengan \(s+1\) titik yang mempunyai \(x\) sebagai elemen terbesarnya. Sekali lagi, hal ini menyiratkan bahwa \(x\) tidak ditempatkan dalam \(A(r,s)\text{.}\)
Jadi, Pemberi Warna memang telah menyusun strategi yang baik untuk mempartisi \(P\) menjadi antirantai, tetapi berapa banyak antirantai yang ia gunakan? Pertanyaan ini sama dengan menanyakan banyaknya pasangan terurut \((i,j)\) bilangan bulat positif yang memenuhi batasan \(i+j-1\le h\text{.}\) Kita telah mempelajari cara menyelesaikan pertanyaan semacam ini dalam Bab 2. Tentu saja, jawabannya adalah \(\binom{h+1}{2}\text{.}\)
Strategi Pemberi Warna begitu sederhana dan alami sehingga mungkin saja strategi yang lebih rumit menghasilkan partisi yang lebih efisien. Ternyata tidak.

Bukti.
Strategi \(S_1\) cukup menyajikan satu titik. Sekarang andaikan teorema berlaku untuk suatu bilangan bulat \(h\ge1\text{.}\) Kita menunjukkan cara kerja strategi \(S_{h+1}\text{.}\)
Pertama, Pembangun mengikuti strategi \(S_h\) untuk membentuk poset \(P_1\text{.}\) Kemudian ia mengikuti strategi itu untuk kedua kalinya guna membentuk poset \(P_2\text{,}\) dengan setiap titik \(P_1\) tak terbandingkan dengan setiap titik \(P_2\text{.}\) Sekarang kita meninjau dua kasus. Mula-mula andaikan Pemberi Warna telah menggunakan \(h+1\) antirantai atau lebih pada himpunan elemen maksimal \(P_1\cup P_2\text{.}\) Dalam kasus ini, Pembangun mengikuti strategi \(S_h\) untuk ketiga kalinya guna membangun poset \(P_3\text{,}\) dengan setiap titik \(P_3\) lebih kecil daripada semua elemen maksimal \(P_1\cup P_2\) dan tak terbandingkan dengan semua titik lainnya.
Jelas bahwa tinggi poset yang dihasilkan paling besar \(h+1\text{.}\) Selain itu, Pemberi Warna harus menggunakan \(h+1+\binom{h+1}{2}=\binom{h+2}{2}\) antirantai untuk mempartisi poset tersebut, dan ia telah menggunakan \(h+1\) antirantai pada himpunan elemen maksimal.
Jadi, tinggal meninjau kasus ketika Pemberi Warna menggunakan suatu himpunan \(W\) yang terdiri atas \(h\) antirantai pada elemen-elemen maksimal \(P_1\text{,}\) dan menggunakan tepat \(h\) antirantai yang sama pada elemen-elemen maksimal \(P_2\text{.}\) Pembangun kemudian menyajikan titik baru \(x\) dan menyatakannya lebih besar daripada semua titik \(P_1\) serta tak terbandingkan dengan semua titik \(P_2\text{.}\) Pemberi Warna harus menempatkan \(x\) dalam suatu antirantai yang tidak termasuk dalam \(W\text{.}\)
Pembangun lalu mengikuti strategi \(S_h\) untuk ketiga kalinya, tetapi sekarang semua titik \(P_3\) lebih kecil daripada \(x\) dan elemen-elemen maksimal \(P_2\text{.}\) Sekali lagi, Pemberi Warna telah dipaksa menggunakan \(h+1\) antirantai berbeda pada elemen-elemen maksimal dan seluruhnya \(\binom{h+2}{2}\) antirantai.
SblmKe AtasLnjt