Subbab 15.1 Pewarnaan Simpul-Simpul Persegi

Mari kita mulai dengan mewarnai simpul-simpul sebuah persegi menggunakan warna putih dan emas. Jika posisi persegi pada bidang dibuat tetap, terdapat \(2^4=16\) pewarnaan yang berbeda. Pewarnaan-pewarnaan tersebut ditunjukkan pada Gambar 15.1.

Namun, jika persegi itu kita bayangkan sebagai bingkai logam dengan manik-manik putih atau emas pada setiap sudut dan bingkainya boleh diputar serta dibalik, kita menyadari bahwa banyak pewarnaan tersebut ekuivalen. Sebagai contoh, jika pewarnaan \(C_7\) dicerminkan terhadap garis vertikal yang membagi persegi menjadi dua, kita memperoleh pewarnaan \(C_9\text{.}\) Jika pewarnaan \(C_2\) diputar \(90^\circ\) searah jarum jam, kita memperoleh pewarnaan \(C_3\text{.}\) Dalam banyak keadaan, kita ingin menganggap pewarnaan-pewarnaan ekuivalen semacam itu sebagai satu pewarnaan. (Ingat kembali contoh pembuka kita tentang kalung yang terbuat dari manik-manik berwarna. Tidak masuk akal membedakan dua kalung jika salah satunya dapat diputar dan dibalik sehingga menjadi kalung yang lain.)

Untuk menentukan secara sistematis berapa banyak pewarnaan pada Gambar 15.1 yang tidak ekuivalen, kita harus memikirkan transformasi-transformasi yang dapat diterapkan pada persegi dan pengaruh setiap transformasi terhadap pewarnaannya. Sebelum memeriksa pengaruh transformasi terhadap pewarnaan, mari kita lihat terlebih dahulu bagaimana transformasi itu menyusun ulang simpul-simpulnya. Kita beri nomor \(1\) pada simpul kiri atas, \(2\) pada simpul kanan atas, \(3\) pada simpul kanan bawah, dan \(4\) pada simpul kiri bawah. Rotasi \(90^\circ\) searah jarum jam kita nyatakan dengan \(r_1\text{.}\) Transformasi \(r_1\) memindahkan simpul pada posisi \(1\) ke posisi \(2\text{,}\) simpul pada posisi \(2\) ke posisi \(3\text{,}\) simpul pada posisi \(3\) ke posisi \(4\text{,}\) dan simpul pada posisi \(4\) ke posisi \(1\text{.}\) Agar ringkas, kita tulis \(r_1(1) =2\text{,}\) \(r_1(2)=3\text{,}\) etc. Kita juga dapat memutar persegi \(180^\circ\) searah jarum jam dan menyatakan rotasi tersebut dengan \(r_2\text{.}\) Dalam hal ini, kita memperoleh \(r_2(1) = 3\text{,}\) \(r_2(2)=4\text{,}\) \(r_2(3)= 1\text{,}\) dan \(r_2(4)=2\text{.}\) Perhatikan bahwa transformasi \(r_2\) dapat diperoleh dengan menerapkan \(r_1\) dua kali berturut-turut. Selain itu, rotasi \(270^\circ\) searah jarum jam, yaitu \(r_3\text{,}\) dapat diperoleh dengan menerapkan \(r_1\) tiga kali berturut-turut. (Rotasi berlawanan arah jarum jam tidak perlu dibahas secara terpisah karena pengaruhnya sama dengan rotasi searah jarum jam, meskipun dengan sudut yang berbeda.)

Untuk mencerminkan persegi, terdapat empat sumbu pencerminan: vertikal, horizontal, diagonal bergradien positif, dan diagonal bergradien negatif. Pencerminan-pencerminan tersebut berturut-turut kita nyatakan dengan \(v\text{,}\) \(h\text{,}\) \(p\text{,}\) dan \(n\text{.}\) Perhatikan bahwa \(v(1) = 2\text{,}\) \(v(2) = 1\text{,}\) \(v(3) = 4\text{,}\) dan \(v(4) = 3\text{.}\) Untuk pencerminan terhadap sumbu horizontal, kita mempunyai \(h(1) = 4\text{,}\) \(h(2) = 3\text{,}\) \(h(3)=2\text{,}\) dan \(h(4)= 1\text{.}\) Untuk \(p\text{,}\) kita mempunyai \(p(1) = 3\text{,}\) \(p(2) = 2\text{,}\) \(p(3)=1\text{,}\) dan \(p(4)=4\text{.}\) Terakhir, untuk \(n\) kita memperoleh \(n(1) = 1\text{,}\) \(n(2) = 4\text{,}\) \(n(3) = 3\text{,}\) dan \(n(4)=2\text{.}\) Masih ada satu transformasi yang harus disebutkan: transformasi yang tidak mengubah persegi disebut transformasi identitas dan dinyatakan dengan \(\iota\text{.}\) Transformasi ini memenuhi \(\iota(1)=1\text{,}\) \(\iota(2)=2\text{,}\) \(\iota(3)=3\text{,}\) dan \(\iota(4)=4\text{.}\)

Setelah mengidentifikasi kedelapan transformasi persegi, mari kita buat tabel yang menunjukkan pewarnaan pada Gambar 15.1 yang tetap tidak berubah ketika setiap transformasi diterapkan. Tidak mengherankan bahwa transformasi identitas membiarkan semua pewarnaan tetap. Karena \(r_1\) memindahkan simpul secara siklis, hanya \(C_1\) dan \(C_{16}\) yang tetap tidak berubah ketika transformasi itu diterapkan. Pada setiap pewarnaan yang menggunakan lebih dari satu warna, akan ada simpul berwarna tertentu yang berpindah ke posisi dengan warna lain. Sekarang perhatikan pewarnaan yang ditetapkan oleh \(v\text{,}\) yaitu pencerminan terhadap sumbu vertikal. Agar suatu pewarnaan tetap, warna pada posisi \(1\) harus sama dengan warna pada posisi \(2\text{,}\) dan warna pada posisi \(3\) harus sama dengan warna pada posisi \(4\text{.}\) Karena itu, kita mengharapkan \(2\cdot 2 = 4\) pewarnaan yang tidak berubah oleh \(v\text{.}\) Dari Gambar 15.1, terlihat bahwa pewarnaan tersebut ialah \(C_1\text{,}\) \(C_6\text{,}\) \(C_8\text{,}\) dan \(C_{16}\text{.}\) Analisis serupa untuk lima transformasi lainnya menghasilkan Gambar 15.2.

Pada tahap ini, wajar jika kita bertanya ke mana pembahasan ini menuju. Bagaimanapun, kita sedang mencoba menghitung banyak pewarnaan yang tidak ekuivalen, sedangkan Gambar 15.2 sama sekali tidak mengelompokkan pewarnaan berdasarkan cara suatu transformasi mengubah satu pewarnaan menjadi pewarnaan lain. Ternyata terdapat hubungan yang berguna antara menghitung pewarnaan tak ekuivalen dan menentukan banyak pewarnaan yang ditetapkan oleh setiap transformasi. Untuk mengembangkan hubungan ini, mula-mula kita perlu membahas relasi ekuivalensi yang dihasilkan oleh aksi transformasi-transformasi persegi pada himpunan \(\cgC\) dari seluruh pewarnaan-\(2\) persegi. (Lihat kembali Subbab B.13 untuk menyegarkan definisi relasi ekuivalensi.) Perhatikan bahwa penerapan suatu transformasi pada persegi dengan simpul-simpul berwarna menghasilkan persegi lain dengan simpul-simpul berwarna. Sebagai contoh, penerapan transformasi \(r_1\) pada persegi dengan pewarnaan \(C_{12}\) menghasilkan persegi dengan pewarnaan \(C_{13}\text{.}\) Kita mengatakan bahwa transformasi-transformasi persegi bertindak pada himpunan pewarnaan \(\cgC\text{.}\) Aksi ini kita nyatakan dengan menambahkan tanda bintang pada nama transformasi. Sebagai contoh, \(r_1^*(C_{12})=C_{13}\) dan \(v^*(C_{10})=C_{11}\text{.}\)

Jika \(\tau\) merupakan transformasi persegi dengan \(\tau^*(C_i) = C_j\text{,}\) kita mengatakan bahwa pewarnaan \(C_i\) dan \(C_j\) ekuivalen dan menulis \(C_i\sim C_j\text{.}\) Karena \(\iota^*(C)=C\) untuk setiap \(C\in\cgC\text{,}\) relasi \(\sim\) bersifat refleksif. Jika \(\tau_1^*(C_i) = C_j\) dan \(\tau_2^*(C_j) = C_k\text{,}\) maka \(\tau_2^*(\tau_1^*(C_i)) = C_k\text{,}\) sehingga \(\sim\) bersifat transitif. Untuk melengkapi verifikasi bahwa \(\sim\) merupakan relasi ekuivalensi, kita harus menunjukkan bahwa relasi ini bersifat simetris. Untuk itu, kita memerlukan konsep invers transformasi \(\tau\text{,}\) yaitu transformasi \(\tau\inv\) yang membatalkan apa pun yang dilakukan oleh \(\tau\text{.}\) Sebagai contoh, invers \(r_1\) ialah rotasi berlawanan arah jarum jam sebesar \(90^\circ\text{,}\) yang pengaruhnya terhadap letak simpul sama dengan \(r_3\text{.}\) Jika \(\tau^*(C_i) = C_j\text{,}\) maka \({\tau^{-1}}^*(C_j) = C_i\text{,}\) sehingga \(\sim\) bersifat simetris.

Sebelum membuktikan secara umum hubungan antara banyak pewarnaan tak ekuivalen (kelas-kelas ekuivalensi terhadap \(\sim\)) dan banyak pewarnaan yang ditetapkan oleh suatu transformasi, mari kita lihat bentuk hubungan itu pada contoh kita. Dari Gambar 15.1, terlihat bahwa \(\sim\) mempartisi \(\cgC\) menjadi enam kelas ekuivalensi. Dua kelas masing-masing memuat satu pewarnaan (seluruh simpul putih dan seluruh simpul emas). Satu kelas memuat dua pewarnaan (\(C_{10}\) dan \(C_{11}\)). Terakhir, tiga kelas masing-masing memuat empat pewarnaan (satu simpul emas, satu simpul putih, dan empat pewarnaan sisanya yang masing-masing menggunakan dua simpul dari setiap warna). Sekarang perhatikan kembali Gambar 15.2 dan jumlahkan banyak pewarnaan yang ditetapkan oleh setiap transformasi. Kita memperoleh \(48\text{;}\) ketika \(48\) dibagi dengan banyak transformasi (\(8\)), hasilnya \(6\text{,}\) tepat banyak kelas ekuivalensi! Ternyata hal ini sama sekali bukan kebetulan, sebagaimana akan segera kita lihat. Namun, terlebih dahulu kita memperkenalkan konsep grup permutasi untuk menggeneralisasi himpunan transformasi persegi tersebut.