Seperti telah disinggung sebelumnya, kita belum memiliki prosedur efisien untuk menentukan lebar suatu poset dan partisi minimum menjadi rantai. Untuk urutan interval, memang ada cara sederhana untuk menemukan keduanya. Penjelasannya cukup dengan membangun hubungan dengan pewarnaan graf interval yang dibahas dalam Bab 5.
Misalkan \(\PXP\) merupakan suatu urutan interval dan misalkan \(\{[a_x,b_x]:x\in X\}\) merupakan interval-interval pada garis bilangan real sedemikian sehingga \(x\lt y\) dalam \(\bfP\) jika dan hanya jika \(b_x\lt a_y\text{.}\) Selanjutnya, misalkan \(\bfG\) merupakan graf interval yang ditentukan oleh keluarga interval ini. Perhatikan bahwa jika \(x\) dan \(y\) merupakan elemen berbeda dari \(X\text{,}\) maka \(x\) dan \(y\) tidak dapat dibandingkan dalam \(\bfP\) jika dan hanya jika \(xy\) merupakan sisi dalam \(\bfG\text{.}\) Dengan kata lain, \(\bfG\) tepat merupakan graf ketakterbandingan dari \(\bfP\text{.}\)
Ingat kembali dari Bab 5 bahwa graf interval merupakan graf sempurna, i.e., \(\chi(\bfG)=\omega(\bfG)\) untuk setiap graf interval \(\bfG\text{.}\) Selain itu, Anda dapat menemukan pewarnaan optimal suatu graf interval dengan menerapkan First Fit pada simpul-simpul menurut urutan linear yang mengikuti urutan titik ujung kiri. Pewarnaan tersebut sekaligus menentukan partisi \(\bfP\) menjadi rantai.
Bahkan, jika Anda ingin melewati bagian mengenai representasi interval, ambillah suatu urutan linear elemen-elemen sebagai \(x_1\text{,}\)\(x_2,\dots,x_n\) sedemikian sehingga \(i\lt j\) setiap kali \(D(x_i)\) merupakan subhimpunan sejati dari \(D(x_j)\text{.}\) Kemudian terapkan First Fit terhadap rantai. Sebagai contoh, untuk urutan interval pada \(10\) titik yang ditampilkan dalam Gambar 6.31, berikut salah satu pelabelan tersebut:
Sekarang terapkan algoritme First Fit pada titik-titik \(\bfP\text{,}\) menurut urutan tersebut, untuk menempatkannya ke dalam rantai \(C_1\text{,}\)\(C_2,\dots\text{.}\) Dengan kata lain, tempatkan \(x_1\) ke rantai \(C_1\text{.}\) Selanjutnya, jika Anda telah menempatkan titik \(x_1\text{,}\)\(x_2,\dots,x_i\) ke dalam rantai, tempatkan \(x_{i+1}\) ke rantai \(C_j\text{,}\) dengan \(j\) sebagai bilangan bulat positif terkecil sedemikian sehingga \(x_{i+1}\) dapat dibandingkan dengan \(x_k\) setiap kali \(1\le k\le i\) dan \(x_k\) telah ditempatkan dalam \(C_j\text{.}\) Sebagai contoh, aturan ini menghasilkan rantai-rantai berikut untuk urutan interval \(\bfP\) yang ditampilkan dalam Gambar 6.31.
Dalam kasus ini, mudah dilihat bahwa partisi rantai tersebut optimal karena lebar \(\bfP\) adalah \(5\) dan \(A=\{a,b,d,i,j\}\) merupakan antirantai dengan \(5\) elemen.
Namun, Anda harus sangat berhati-hati ketika menerapkan First Fit untuk menemukan partisi rantai optimal suatu poset—sama seperti kita harus berhati-hati menggunakan First Fit untuk menemukan pewarnaan optimal graf.
Poset di sisi kiri Gambar 6.33 merupakan poset bertinggi \(2\) pada \(10\) titik. Jika poset tersebut dipartisi menjadi antirantai dengan menerapkan First Fit dan meninjau titik-titik menurut urutan labelnya, akan digunakan \(5\) antirantai. Dapatkah Anda melihat cara memperluas poset ini agar First Fit terpaksa menggunakan sebanyak apa pun antirantai, sambil mempertahankan tinggi poset sebesar \(2\text{?}\)
Di sisi kanan ditampilkan sebuah poset berlebar \(2\text{.}\) Jika poset ini dipartisi menjadi rantai dengan menerapkan First Fit dan meninjau titik-titik menurut urutan labelnya, akan digunakan \(4\) rantai. Dapatkah Anda melihat cara memperluas poset ini agar First Fit terpaksa menggunakan sebanyak apa pun rantai sambil mempertahankan lebar poset sebesar \(2\text{?}\)
Dua diagram Hasse memperlihatkan kegagalan First Fit. Diagram kiri memiliki sepuluh titik dalam dua tingkat, dengan label ganjil di atas dan genap di bawah serta banyak sisi penutup silang. Diagram kanan memiliki dua rantai vertikal pada dua belas titik dengan sisi-sisi penutup diagonal di antaranya.
Secara umum, selalu ada suatu urutan linear pada himpunan dasar poset yang membuat First Fit menemukan partisi optimal menjadi antirantai. Ada pula suatu urutan linear (yang umumnya berbeda dari yang pertama) pada himpunan dasar yang membuat First Fit menemukan partisi optimal menjadi rantai. Namun, tidak ada manfaat mencari urutan-urutan tersebut karena algoritme yang kita kembangkan untuk menemukan partisi antirantai dan rantai optimal bekerja dengan sangat baik.
