Subbab 5.5 Graf Planar

Mari kita kembali ke persoalan memasang saluran air, listrik, dan gas alam menuju tiga rumah yang dibahas pada pendahuluan bab ini. Bagaimana kita dapat memodelkan persoalan tersebut dengan graf? Cara yang paling tepat ialah membuat satu simpul untuk setiap layanan utilitas dan satu simpul untuk masing-masing dari ketiga rumah. Pertanyaannya kemudian ialah apakah kita dapat menggambar graf yang memiliki sisi dari setiap layanan utilitas ke setiap rumah tanpa ada sisi yang saling berpotongan. Graf ini ditampilkan pada Gambar 5.30. Anda seharusnya mengenalinya sebagai graf bipartit lengkap \(\bfK_{3,3}\) yang telah diperkenalkan sebelumnya dalam bab ini.

Contoh saluran utilitas ini mungkin terasa agak dibuat-buat, sebab sebenarnya tidak ada alasan kuat yang menghalangi penyedia layanan untuk menanam salurannya pada kedalaman berbeda. Namun, pertanyaan apakah suatu graf dapat digambar pada bidang sehingga sisi-sisinya hanya berpotongan di simpul telah lama dipelajari dalam matematika dan memiliki penerapan yang berguna. Salah satu penerapannya muncul dalam perancangan mikrocip dan papan sirkuit. Dalam konteks tersebut, bahannya begitu tipis sehingga menempatkan sambungan pada kedalaman berbeda tidak mungkin dilakukan atau sangat terbatas. Banyak matematika mendalam mendasari bidang ini, dan bagian ini dimaksudkan untuk memperkenalkan beberapa konsep utamanya.

Yang dimaksud dengan penggambaran suatu graf ialah cara mengaitkan simpul-simpulnya dengan titik-titik pada bidang Kartesius \(\reals^2\) dan sisi-sisinya dengan busur poligonal sederhana yang kedua ujungnya merupakan titik yang dikaitkan dengan kedua simpul ujung sisi tersebut. Busur poligonal dapat dipandang sebagai urutan berhingga ruas garis, dengan titik akhir setiap ruas garis menjadi titik awal ruas berikutnya; busur poligonal sederhana tidak memotong dirinya sendiri. (Pemilihan busur poligonal alih-alih kurva sembarang sebenarnya tidak menjadi kendala, sebab setiap kurva dapat dihampiri dengan ruas-ruas garis yang sangat, sangat, sangat pendek.) Penggambaran planar suatu graf adalah penggambaran yang membuat busur-busur poligonal bagi dua sisi hanya berpotongan pada titik yang mewakili simpul yang bersisian dengan kedua sisi tersebut. Suatu graf disebut planar apabila memiliki penggambaran planar. Muka dari penggambaran planar suatu graf adalah daerah yang dibatasi oleh sisi dan simpul serta tidak memuat simpul atau sisi lain.

Gambar 5.31 menampilkan penggambaran planar suatu graf dengan \(6\) simpul dan \(9\) sisi. Perhatikan bahwa salah satu sisinya digambar sebagai busur poligonal sejati, bukan sebagai ruas garis lurus. Penggambaran ini menentukan \(5\) daerah, karena daerah tak terbatas yang mengelilingi gambar juga dihitung.

Gambar 5.32 menampilkan penggambaran planar graf lengkap \(\bfK_4\text{.}\) Penggambaran ini memiliki \(4\) simpul, \(6\) sisi, dan \(4\) muka.

Walaupun hasil \(2\) pada kedua penggambaran planar tersebut mungkin tampak sebagai kebetulan, sebenarnya ada prinsip yang lebih umum, dan prinsip ini berlaku bagi setiap penggambaran planar dari setiap graf planar.

Sesungguhnya, bilangan \(2\) di sini berasal dari sifat mendasar bidang, dan terdapat teorema-teorema yang bersesuaian untuk permukaan lain. Namun, kita hanya memerlukan hasil dalam bentuk yang dinyatakan di atas.

Kontraposisi teorema ini—yakni bahwa graf dengan \(n\) simpul dan lebih dari \(3n-6\) sisi tidak planar—biasanya merupakan bentuk hasil yang paling berguna. Sebagai contoh, kita telah melihat pada Gambar 5.32 bahwa \(\bfK_4\) planar. Bagaimana dengan \(\bfK_5\text{?}\) Graf ini memiliki \(5\) simpul dan \(C(5,2)=10 > 9 = 3\cdot 5-6\) sisi, sehingga tidak planar. Akibatnya, untuk \(n\geq 5\text{,}\) graf \(\bfK_n\) tidak planar karena mengandung \(\bfK_5\text{.}\) Penting untuk dicatat bahwa Teorema 5.34 bukanlah satu-satunya alat untuk menentukan apakah suatu graf planar. Untuk melihat hal ini, mari kembali ke persoalan menggambar \(\bfK_{3,3}\) pada bidang. Graf ini memiliki \(6\) simpul dan \(9\) sisi, sehingga lolos uji Teorema 5.34. Namun, setelah mencoba selama beberapa menit untuk menggambar \(\bfK_{3,3}\) pada bidang tanpa sisi yang berpotongan, Anda akan segera menduga bahwa hal itu mustahil dilakukan—dan dugaan Anda benar!

Untuk melihat mengapa \(\bfK_{3,3}\) tidak planar, kita harus kembali ke Rumus Euler dan sekali lagi menghitung insidensi sisi–muka. Pada \(\bfK_{3,3}\text{,}\) setiap sisi harus menjadi bagian dari batas dua muka, sedangkan setiap muka dibatasi oleh suatu siklus. Selain itu, karena graf ini bipartit, tidak ada siklus ganjil. Jadi, dengan menghitung insidensi sisi–muka dari sisi, terdapat \(2m = 18\) insidensi. Misalkan \(f_k\) menyatakan banyaknya muka yang dibatasi oleh siklus dengan panjang \(k\text{;}\) maka \(f= f_4 + f_6\text{.}\) Dengan menghitung insidensi dari muka, terdapat \(4f_4 + 6f_6\) insidensi. Menurut Rumus Euler, banyaknya muka \(f\) haruslah \(5\text{,}\) sehingga \(4f_4+6f_6\geq 20\text{.}\) Namun, penghitungan dari sisi memberikan \(2m=4f_4+6f_6\text{,}\) yang menghasilkan \(18\geq 20\text{;}\) ini jelas mustahil. Jadi, \(\bfK_{3,3}\) tidak planar.

Pada titik ini, Anda mungkin bertanya, “Lalu apa gunanya?” Kita telah mencurahkan cukup banyak upaya untuk menunjukkan bahwa \(\bfK_5\) dan \(\bfK_{3,3}\) tidak planar. Jelas bahwa setiap graf yang mengandung salah satunya juga tidak planar. Namun, karena jumlah graf sangat banyak, Anda mungkin menduga bahwa pekerjaan ini tidak akan pernah selesai. Untungnya tidak demikian: pada dasarnya, keplanaran ditentukan hanya oleh kedua graf tersebut, seperti yang segera akan kita lihat.

Jika \(\GVE\) adalah graf dan \(uv\in E\text{,}\) kita dapat membentuk graf baru \(\bfG'\) yang disebut subdivisi elementer dari \(\bfG\) dengan menambahkan simpul baru \(v'\) dan mengganti sisi \(uv\) dengan sisi \(uv'\) dan \(v'v\text{.}\) Dengan kata lain, \(\bfG'\) memiliki himpunan simpul \(V'=V\cup\{v'\}\) dan himpunan sisi \(E'=(E-\{uv\})\cup \{uv',v'v\}\text{.}\) Dua graf \(\bfG_1\) dan \(\bfG_2\) disebut homeomorfik apabila keduanya dapat diperoleh dari graf yang sama melalui suatu barisan subdivisi elementer, yang boleh saja trivial.

Graf homeomorfik dibahas karena dua graf homeomorfik memiliki sifat yang sama dalam hal penggambarannya pada bidang. Untuk melihatnya, perhatikan apa yang terjadi pada \(\bfK_5\) jika kita melakukan subdivisi elementer pada salah satu sisinya. Graf tersebut jelas tetap tidak planar. Bahkan, jika subdivisi elementer dilakukan pada sembarang sisi suatu graf yang tidak planar, graf hasilnya juga tidak planar. Teorema sangat mendalam berikut dibuktikan oleh matematikawan Polandia Kazimierz Kuratowski pada tahun 1930. Pembuktiannya berada di luar cakupan buku ini.

Teorema Kuratowski memberikan cara yang berguna untuk memeriksa apakah suatu graf planar. Walaupun mencari secara manual subgraf yang homeomorfik dengan \(\bfK_5\) atau \(\bfK_{3,3}\) tidak selalu mudah, terdapat algoritma efisien untuk menguji keplanaran yang memanfaatkan karakterisasi ini. Untuk melihat penerapan teorema tersebut, perhatikan graf Petersen pada Gambar 5.18. Graf Petersen memiliki \(10\) simpul dan \(15\) sisi, sehingga lolos uji Teorema 5.34. Selain itu, argumen dengan Rumus Euler untuk membuktikan bahwa \(\bfK_{3,3}\) tidak planar sudah cukup rumit, jadi kita tentu tidak ingin mengulang pendekatan itu untuk graf Petersen. Untuk menggunakan Teorema Kuratowski, kita perlu memutuskan apakah akan mencari subgraf yang homeomorfik dengan \(\bfK_5\) atau dengan \(\bfK_{3,3}\text{.}\) Walaupun graf Petersen tampak sangat mirip dengan \(\bfK_5\text{,}\) sesungguhnya graf itu sekaligus terlalu mirip dan terlalu berbeda untuk memuat subgraf yang homeomorfik dengan \(\bfK_5\text{,}\) sebab setiap simpulnya berderajat \(3\text{.}\) Karena itu, kita mencari subgraf dari graf Petersen yang homeomorfik dengan \(\bfK_{3,3}\text{.}\) Perhatikan bahwa \(\bfK_{3,3}\) mengandung siklus dengan panjang \(6\) serta tiga sisi yang menghubungkan pasangan simpul yang berseberangan pada siklus tersebut. Kita mengenali sebuah siklus-enam pada graf Petersen, menggambarnya sebagai segi enam, dan menempatkan empat simpul sisanya di dalam siklus. Penggambaran ini ditampilkan pada Gambar 5.36. Subgraf yang homeomorfik dengan \(\bfK_{3,3}\) diperoleh dengan menghapus simpul hitam; setelah itu, semua simpul putih berderajat dua dan masing-masing beserta dua sisi yang bersisian dengannya (digambar tebal) dapat diganti dengan satu sisi.

Kita menutup bagian ini dengan persoalan yang menghubungkan pembahasan sekarang dengan topik pewarnaan graf. Pada tahun 1852, Francis Guthrie, seorang Inggris yang ketika itu sedang belajar untuk menjadi pengacara dan kemudian menjadi profesor matematika di Afrika Selatan, mencoba mewarnai peta wilayah-wilayah administratif di Inggris sedemikian rupa sehingga setiap dua wilayah yang berbagi suatu ruas batas (artinya bersentuhan di lebih dari satu titik) diberi warna berbeda. Ia menyadari bahwa empat warna saja sudah cukup dan tidak berhasil menggambar peta apa pun yang memerlukan lima warna. (Ia dapat menemukan peta yang memang memerlukan empat warna; salah satu contohnya ditampilkan pada Gambar 5.37.)

Mungkinkah setiap peta dapat diwarnai hanya dengan empat warna? Guthrie menanyakan persoalan ini kepada saudaranya, Frederick Guthrie, yang merupakan mahasiswa matematika di University College, London. Frederick kemudian menyampaikannya kepada salah seorang gurunya, Augustus de Morgan, yang terkenal melalui Hukum de Morgan. Dengan cara inilah lahir salah satu persoalan paling terkenal—atau paling masyhur karena kesulitannya—dalam teori graf, yang selama satu abad dikenal sebagai Masalah Empat Warna dan kini sebagai Teorema Empat Warna. De Morgan sangat tertarik pada Masalah Empat Warna dan menyampaikannya kepada Sir William Rowan Hamilton, matematikawan Irlandia terkemuka yang namanya diabadikan dalam istilah siklus Hamilton. Namun, Hamilton tidak menganggap persoalan tersebut menarik. Ia termasuk sedikit orang yang pernah mempertimbangkan Masalah Empat Warna tanpa terpikat olehnya.

Kita akan segera melanjutkan pembahasan sejarah Teorema Empat Warna, tetapi terlebih dahulu kita perlu mengubah persoalan pewarnaan peta menjadi pertanyaan teori graf. Wajar jika setiap daerah dipasangkan dengan satu simpul. Karena daerah-daerah yang berbagi batas harus memiliki warna berbeda, kita menempatkan sisi di antara dua simpul jika dan hanya jika daerah yang bersesuaian memiliki batas bersama. (Sebagai contoh, peta pada Gambar 5.37 bersesuaian dengan graf \(\bfK_4\text{.}\)) Konstruksi ini menghasilkan graf planar, sebab sisi-sisinya dapat digambar melalui ruas batas bersama. Sebaliknya, dengan sedikit pemikiran, Anda dapat melihat bahwa dari penggambaran planar suatu graf dapat dibuat peta yang setiap simpulnya menjadi sebuah daerah dan setiap sisinya menjadi ruas batas bersama. Jadi, Masalah Empat Warna dapat dinyatakan sebagai “Apakah setiap graf planar memiliki bilangan kromatik paling besar empat?”

Minat terhadap Masalah Empat Warna meredup hingga tahun 1877, ketika matematikawan Inggris Arthur Cayley menulis surat kepada Royal Society untuk menanyakan apakah persoalan itu telah diselesaikan. Surat tersebut menarik perhatian jauh lebih banyak orang. “Bukti” pertama Teorema Empat Warna, karya Alfred Bray Kempe, selesai pada tahun 1878 dan diterbitkan setahun kemudian. Baru \(11\) tahun kemudian Percy John Heawood menemukan kekeliruan dalam bukti tersebut, tetapi ia berhasil mempertahankan cukup banyak bagiannya untuk menunjukkan bahwa setiap graf planar memiliki bilangan kromatik paling besar lima. Pada tahun 1880, Peter Guthrie Tait, fisikawan Inggris yang paling dikenal melalui buku Treatise on Natural Philosophy bersama Sir William Thomson (Lord Kelvin), membuat pengumuman yang menyiratkan bahwa ia memiliki bukti Teorema Empat Warna dengan menggunakan siklus Hamilton pada graf planar tertentu. Namun, sejalan dengan cara Tait menangani beberapa konjektur dalam teori knot matematis, tampaknya sekitar tahun 1883 ia kemudian menyadari bahwa dirinya tidak dapat membuktikan keberadaan siklus Hamilton yang digunakan. Karena itu, mungkin Tait hanya dalam waktu singkat meyakini bahwa ia memiliki bukti Teorema Empat Warna, jika ia pernah benar-benar meyakininya. Meskipun demikian, contoh penyangkal bagi konjektur yang digunakan Tait baru ditemukan pada tahun 1946.

Pada paruh pertama abad kedua puluh, terdapat sejumlah kemajuan bertahap menuju penyelesaian Masalah Empat Warna, tetapi hanya sedikit matematikawan terkemuka yang menaruh minat serius. Dorongan terakhir untuk membuktikan Teorema Empat Warna berlangsung kira-kira bersamaan dengan mulai meluasnya penggunaan komputer elektronik pertama dalam industri dan penelitian. Pada tahun 1976, dua matematikawan di University of Illinois mengumumkan bukti Teorema Empat Warna berbantuan komputer. Bukti Kenneth Appel dan Wolfgang Haken mendorong University of Illinois menambahkan frasa “FOUR COLORS SUFFICE (EMPAT WARNA CUKUP)” pada cap mesin perangkonya.

¹

Foto sebuah amplop dengan cap mesin semacam itu dapat ditemukan dalam buku The Four-Color Theorem: History, Topological Foundations, and Idea of Proof karya Rudolf dan Gerda Fritsch. (Springer, 1998)

Bukti Teorema Empat Warna oleh Appel dan Haken setidaknya tidak memuaskan bagi banyak matematikawan, bahkan bagi sebagian orang sama sekali bukan sebuah bukti. Para matematikawan tersebut menganggap penggunaan komputer untuk memeriksa berbagai kasus terlalu tidak pasti: bagaimana Anda dapat yakin bahwa kode yang memeriksa 1.482 “konfigurasi tak terhindarkan” tidak mengandung kesalahan logika? Memang, beberapa kesalahan ditemukan dalam kasus-kasus yang dianalisis, tetapi tidak satu pun terbukti sebagai kekeliruan fatal. Pada tahun 1989, Appel dan Haken menerbitkan karya setebal 741 halaman berjudul Every Planar Map is Four Colorable, yang memperbaiki semua kelemahan yang diketahui dalam argumen awal mereka. Hal ini masih belum memuaskan banyak orang. Pada awal 1990-an, tim yang terdiri atas Neil Robertson dari The Ohio State University; Daniel P. Sanders, mahasiswa pascasarjana di Georgia Institute of Technology; Paul Seymour dari Bellcore; dan Robin Thomas dari Georgia Tech mengumumkan bukti baru Teorema Empat Warna. Namun, bukti tersebut tetap memerlukan komputer. Bukti baru itu diterima secara lebih luas daripada bukti Appel dan Haken, antara lain karena menggunakan kurang dari separuh jumlah konfigurasi dalam bukti Appel–Haken, yaitu \(633\text{,}\) dan kode komputernya disediakan daring agar dapat diperiksa oleh siapa pun. Walaupun tetap tidak memuaskan bagi sebagian orang, bukti Robertson dan rekan-rekannya diterima secara umum, dan kini persoalan Teorema Empat Warna pada dasarnya dianggap selesai. Namun, banyak orang masih bertanya-tanya apakah kelak akan ditemukan bukti bagi pernyataan sederhana ini yang tidak memerlukan bantuan komputer.