Lewati ke konten utama
Gambar logo

Matematika Diskret Sebuah Pengantar Terbuka, Edisi Keempat

Oscar Levin

Subbab 2.5 Pewarnaan

Subbagian Pratinjau Bagian

Selidiki!
Para pembuat peta di negeri fiktif Euleria telah menggambar batas berbagai kadipaten di negeri tersebut. Agar petanya menarik, mereka ingin mewarnai setiap wilayah. Wilayah yang bertetangga harus diberi warna berbeda, tetapi dua wilayah yang berjauhan boleh diberi warna yang sama. Berapa jumlah warna minimum yang dapat digunakan para pembuat peta untuk menyelesaikan tugas ini?
🔗
Gambar abstrak sebuah "peta" yang wilayah-wilayahnya dipisahkan oleh batas yang sedikit melengkung. Peta tersebut memuat lingkaran luar yang terdiri atas tujuh wilayah (semuanya berukuran berbeda), lingkaran dalam yang terdiri atas lima wilayah lagi, dan satu wilayah tengah terakhir yang bentuknya tidak beraturan.
🔗
Barangkali masalah teori graf yang paling terkenal adalah cara mewarnai peta.
🔗
Untuk sembarang peta negara, negara bagian, kabupaten, dan sebagainya, berapa banyak warna yang diperlukan untuk mewarnai setiap wilayah pada peta agar wilayah yang bertetangga diberi warna berbeda?
🔗
🔗
Para pembuat peta sebenarnya biasanya menggunakan sekitar tujuh warna. Salah satu alasannya, mereka mengharuskan wilayah perairan diberi warna tertentu, dan dengan banyak warna, pewarnaan yang diperbolehkan lebih mudah ditemukan. Kita ingin mengetahui apakah ada palet yang lebih kecil dan dapat digunakan untuk sembarang peta.
🔗
Apa kaitannya dengan teori graf? Jika kita menempatkan sebuah simpul di tengah setiap wilayah (misalnya di ibu kota setiap negara bagian) lalu menghubungkan dua simpul apabila negara bagiannya berbagi batas, kita memperoleh sebuah graf. Mewarnai wilayah pada peta bersesuaian dengan mewarnai simpul-simpul graf. Karena wilayah yang bertetangga tidak boleh diberi warna yang sama, simpul-simpul yang bertetangga pada graf kita tidak boleh diberi warna yang sama.
🔗
Secara umum, untuk sembarang graf \(G\text{,}\) pemberian warna pada simpul-simpulnya disebut (tidak mengherankan) pewarnaan simpul. Jika dalam pewarnaan simpul tersebut simpul-simpul yang bertetangga diberi warna berbeda, pewarnaan itu disebut tepat. Setiap graf memiliki pewarnaan simpul yang tepat. Sebagai contoh, Anda dapat memberi setiap simpul warna yang berbeda. Namun, sering kali kita dapat menggunakan lebih sedikit warna. Jumlah warna minimum yang diperlukan untuk memperoleh pewarnaan simpul yang tepat disebut bilangan kromatik graf tersebut, yang ditulis \(\chi(G)\text{.}\)
🔗
Tujuan kita dalam bagian ini adalah melihat bagaimana pewarnaan graf dapat digunakan untuk menyelesaikan berbagai masalah dan memahami beberapa sifat dasar pewarnaan graf.
🔗

Lembar Kerja Kegiatan Pratinjau

Untuk setiap graf di bawah ini:
  • Temukan pewarnaan simpul yang tepat dengan menggunakan sejumlah warna. Artinya, warnai simpul-simpul dengan jumlah warna sembarang sedemikian sehingga tidak ada dua simpul bertetangga yang memiliki warna sama.
    🔗
    🔗
  • Tentukan jumlah warna paling sedikit yang diperlukan untuk mewarnai simpul-simpul graf dengan tepat. Bilangan ini disebut bilangan kromatik graf. Pikirkan bagaimana Anda mengetahui bahwa jawaban tersebut benar.
    🔗
    🔗
  • Dapatkah Anda membuat generalisasi? Dapatkah Anda menyimpulkan sesuatu mengenai bilangan kromatik untuk jenis graf tertentu?
    🔗
    🔗
🔗
🔗
🔗

Subbagian Pewarnaan Simpul

Selidiki!
Departemen matematika berencana menawarkan 10 mata kuliah pada semester depan. Beberapa mata kuliah tidak dapat diselenggarakan pada waktu yang sama (mungkin karena diajarkan oleh dosen yang sama, atau diwajibkan bagi mahasiswa tingkat akhir).
🔗
Mata kuliah: Berbenturan dengan:
A D I
B D I J
C E F I
D A B F
E C H I
F C D I
G J
H E I J
I A B C E F H
J B G H
Berapa banyak slot waktu berbeda yang diperlukan untuk menyelenggarakan mata kuliah tersebut (dan mata kuliah mana yang sebaiknya diselenggarakan pada waktu yang sama)? Lebih penting lagi, bagaimana kita dapat menggunakan pewarnaan graf untuk menjawab pertanyaan ini?
🔗
🔗
Cara terbaik untuk memahami bilangan kromatik secara intuitif adalah mencoba mewarnai beberapa graf.
🔗

Contoh 2.5.1.

Tentukan bilangan kromatik graf-graf di bawah ini.
🔗
Salinan K6: enam simpul tersusun membentuk segienam, dengan setiap simpul bertetangga dengan setiap simpul lainnya.
Enam simpul tersusun membentuk segitiga (dengan tiga simpul pada setiap sisinya). Enam sisi membentuk keliling segitiga, dan tiga sisi menghubungkan simpul tengah pada setiap sisinya (membentuk segitiga terbalik).
Salinan K2,3, dengan dua simpul pada baris atas yang masing-masing bertetangga dengan ketiga simpul pada baris bawah.
Penyelesaian.
Graf di sebelah kiri adalah \(K_6\text{.}\) Satu-satunya cara untuk mewarnai graf tersebut secara tepat adalah memberi setiap simpul warna yang berbeda (karena setiap simpul bertetangga dengan setiap simpul lainnya). Jadi, bilangan kromatiknya adalah 6.
🔗
Graf di tengah dapat diwarnai secara tepat hanya dengan 3 warna (merah, biru, dan hijau). Sebagai contoh:
🔗
Enam simpul tersusun membentuk segitiga (dengan tiga simpul pada setiap sisinya). Enam sisi membentuk keliling segitiga, dan tiga sisi menghubungkan simpul tengah pada setiap sisinya (membentuk segitiga terbalik). Label R, B, dan G masing-masing menyatakan merah, biru, dan hijau. Simpul-simpul pada baris bawah berlabel R, B, G (dari kiri ke kanan), simpul-simpul pada baris tengah berlabel G, R, dan simpul paling atas berlabel B.
Graf tersebut tidak mungkin diwarnai hanya dengan dua warna karena terdapat tiga simpul yang saling bertetangga (yaitu, sebuah segitiga). Jadi, bilangan kromatiknya adalah 3.
🔗
Graf di sebelah kanan adalah \(K_{2,3}\text{.}\) Seperti semua graf bipartit, graf ini memiliki bilangan kromatik 2: warnai simpul-simpul pada baris atas dengan merah dan simpul-simpul pada baris bawah dengan biru.
🔗
🔗
🔗
Tampaknya tidak ada batas bagi besarnya bilangan kromatik. Tidak mengherankan bahwa \(K_n\) memiliki bilangan kromatik \(n\text{.}\) Lalu, bagaimana mungkin pertanyaan awal tentang pewarnaan peta memiliki jawaban? Jika bilangan kromatik suatu graf dapat menjadi sebesar apa pun, tampaknya tidak akan ada batas atas bagi jumlah warna yang diperlukan untuk sembarang peta. Namun, batas tersebut ada.
🔗
Pengamatan kuncinya adalah bahwa meskipun untuk setiap bilangan \(n\) terdapat graf dengan bilangan kromatik \(n\text{,}\) hanya graf tertentu yang dapat muncul sebagai representasi peta. Jika Anda mengubah suatu peta menjadi graf, sisi-sisi di antara simpul bersesuaian dengan batas antarnegara. Jadi, simpul-simpul tersebut harus dapat dihubungkan sedemikian rupa sehingga sisi-sisinya tidak berpotongan. Dengan kata lain, semua graf yang merepresentasikan peta bersifat planar!
🔗
Jadi, pertanyaannya adalah: berapakah bilangan kromatik terbesar dari sembarang graf planar? Jawabannya diberikan oleh teorema teori graf yang paling terkenal:
🔗
Kita tidak akan membuktikan teorema ini. Sungguh. Meskipun teorema tersebut mudah dinyatakan dan dipahami, pembuktiannya tidak mudah. Bahkan, saat ini belum diketahui adanya bukti yang “mudah” untuk teorema tersebut. Bukti terbaik saat ini masih memerlukan komputer berdaya tinggi untuk memeriksa himpunan tak terhindarkan yang terdiri atas 633 konfigurasi yang dapat direduksi. Gagasannya adalah bahwa setiap graf harus memuat salah satu konfigurasi yang dapat direduksi tersebut (fakta ini juga perlu diperiksa oleh komputer) dan bahwa konfigurasi yang dapat direduksi memang dapat diwarnai dengan 4 warna atau kurang.
🔗
Kartografi tentu bukan satu-satunya penerapan pewarnaan graf. Ada banyak situasi ketika Anda ingin mempartisi objek-objek yang ditinjau agar objek yang saling berkaitan tidak berada dalam himpunan yang sama. Sebagai contoh, Anda mungkin ingin menyimpan bahan kimia dengan aman. Untuk menghindari ledakan, pasangan bahan kimia tertentu tidak boleh disimpan dalam ruangan yang sama. Dengan mewarnai suatu graf (dengan simpul yang merepresentasikan bahan kimia dan sisi yang merepresentasikan potensi interaksi berbahaya), Anda dapat menentukan jumlah minimum ruangan yang diperlukan untuk menyimpan bahan kimia tersebut.
🔗
Berikut adalah contoh lainnya:
🔗

Contoh 2.5.3.

Stasiun radio memancarkan sinyal pada frekuensi tertentu. Namun, jumlah frekuensi yang dapat dipilih terbatas, sehingga banyak stasiun di seluruh negeri menggunakan frekuensi yang sama. Hal ini dapat dilakukan karena stasiun-stasiun tersebut cukup berjauhan sehingga sinyalnya tidak saling mengganggu; tidak ada satu radio pun yang dapat menangkap sinyal-sinyal tersebut secara bersamaan.
🔗
Misalkan 10 stasiun radio baru akan didirikan di suatu wilayah yang saat ini belum memiliki stasiun radio. Pasangan stasiun radio yang cukup berdekatan sehingga menimbulkan gangguan dicatat dalam tabel di bawah ini. Berapa jumlah minimum frekuensi yang dapat digunakan stasiun-stasiun tersebut?
🔗
KQEA KQEB KQEC KQED KQEE KQEF KQEG KQEH KQEI KQEJ
KQEA x x x x
KQEB x x
KQEC x x x x x
KQED x x x x
KQEE x x
KQEF x x x x x
KQEG x x x x
KQEH x x
KQEI x x x
KQEJ x x x x x
Penyelesaian.
Representasikan masalah tersebut sebagai graf dengan stasiun sebagai simpul dan sisi yang menghubungkan dua stasiun apabila keduanya cukup berdekatan sehingga menimbulkan gangguan. Kita mencari bilangan kromatik graf tersebut. Simpul-simpul yang diberi warna sama merepresentasikan stasiun yang dapat menggunakan frekuensi yang sama.
🔗
Graf ini memiliki bilangan kromatik 5. Pewarnaan tepat dengan 5 warna ditunjukkan di sebelah kanan. Perhatikan bahwa graf tersebut memuat salinan graf lengkap \(K_5\text{,}\) sehingga tidak mungkin digunakan kurang dari 5 warna.
🔗
Gambar graf yang merepresentasikan stasiun radio, dengan sisi di antara dua simpul apabila kedua stasiun tersebut saling mengganggu. Simpul-simpul tersusun melingkar dengan KQEA di bagian atas, kemudian KQEB searah jarum jam, dan seterusnya hingga KQEJ.
Gambar graf yang merepresentasikan stasiun radio, dengan sisi di antara dua simpul apabila kedua stasiun tersebut saling mengganggu. Di sini, setiap simpul diberi label huruf yang merepresentasikan warna: R untuk merah, G untuk hijau, B untuk biru, Y untuk kuning, dan P untuk ungu. Dari simpul paling atas, kemudian bergerak searah jarum jam: R, G, B, B, G, G, Y, R, B, P. Salinan graf K5 digambar tebal di antara sisi-sisi graf semula.
🔗
🔗
Dalam contoh di atas, bilangan kromatiknya adalah 5, tetapi hal ini bukan contoh penyangkal bagi Teorema Empat Warna 2.5.2 karena graf yang merepresentasikan stasiun radio tidak planar. Akan menyenangkan jika ada cara cepat untuk menentukan bilangan kromatik suatu graf (yang mungkin nonplanar). Ternyata belum diketahui apakah terdapat algoritma efisien untuk menghitung bilangan kromatik.
🔗
Meskipun kita mungkin tidak dapat menentukan bilangan kromatik suatu graf secara tepat dengan mudah, kita sering kali dapat memberikan rentang yang wajar bagi bilangan kromatik tersebut. Dengan kata lain, kita dapat memberikan batas atas dan batas bawah bagi bilangan kromatik.
🔗
Hal ini tidak terlalu sulit: untuk setiap graf \(G\text{,}\) bilangan kromatik \(G\) sedikitnya 1 dan paling banyak sama dengan jumlah simpul \(G\text{.}\)
🔗
Apa? Anda menginginkan batas yang lebih baik bagi bilangan kromatik? Kalau begitu, Anda beruntung.
🔗
Sebuah klik dalam graf adalah himpunan simpul yang setiap pasang simpulnya bertetangga. Dengan kata lain, klik berukuran \(n\) tidak lain adalah salinan graf lengkap \(K_n\text{.}\) Kita mendefinisikan bilangan klik suatu graf sebagai nilai \(n\) terbesar sedemikian sehingga graf tersebut memuat klik berukuran \(n\text{.}\) Setiap klik berukuran \(n\) tidak dapat diwarnai dengan kurang dari \(n\) warna, sehingga kita memperoleh batas bawah yang baik:
🔗
Ada kalanya bilangan kromatik \(G\) sama dengan bilangan kliknya. Graf-graf ini memiliki nama khusus; graf tersebut disebut sempurna. Jika Anda mengetahui bahwa suatu graf sempurna, menentukan bilangan kromatiknya cukup dilakukan dengan mencari klik terbesar.
 10 
Terdapat kelas-kelas graf khusus yang dapat dibuktikan sempurna. Salah satunya adalah kelas graf kordal, yang memiliki sifat bahwa setiap siklus dalam graf memuat tali busur—sisi di antara dua simpul pada siklus yang tidak bertetangga di sepanjang siklus tersebut.
Namun, tidak semua graf sempurna.
🔗
Untuk batas atas, kita dapat memperbaiki batas “jumlah simpul” dengan memperhatikan derajat simpul. Misalkan \(\Delta(G)\) menyatakan derajat terbesar dari semua simpul dalam graf \(G\text{.}\) Dugaan yang wajar untuk batas atas bilangan kromatik adalah \(\chi(G) \le \Delta(G) + 1\text{.}\) Mengapa dugaan ini wajar? Mulai dari sembarang simpul, simpul tersebut beserta semua tetangganya selalu dapat diberi \(\Delta(G) + 1\) warna, karena himpunan ini memuat paling banyak \(\Delta(G) + 1\) simpul. Sekarang, perluas pewarnaannya! Pada setiap tahap, jika Anda meninjau simpul yang telah diwarnai, sebagian tetangganya mungkin telah diwarnai dan sebagian lainnya belum. Namun, dalam keadaan apa pun, simpul tersebut dan semua tetangganya dapat diberi warna berbeda, karena terdapat paling banyak \(\Delta(G)\) tetangga, ditambah satu simpul yang sedang ditinjau.
🔗
Bahkan, terdapat contoh graf yang memenuhi \(\chi(G) = \Delta(G) + 1\text{.}\) Untuk sembarang \(n\text{,}\) graf lengkap \(K_n\) memiliki bilangan kromatik \(n\text{,}\) tetapi \(\Delta(K_n) = n-1\) (karena setiap simpul bertetangga dengan setiap simpul lainnya). Selain itu, setiap siklus ganjil memiliki bilangan kromatik 3, sedangkan derajat setiap simpul dalam siklus adalah 2. Ternyata hanya dua jenis contoh inilah yang menghasilkan kesamaan, suatu hasil yang dikenal sebagai Teorema Brooks.
🔗
Bukti teorema ini cukup rumit sehingga tidak akan kita sajikan di sini (meskipun Anda diminta membuktikan suatu kasus khusus dalam latihan). Pembaca yang menyukai tantangan dianjurkan mencari buku teori graf untuk memperoleh petunjuk tentang cara membuktikan teorema tersebut.
🔗
🔗

Subbagian Pewarnaan Sisi

Bilangan kromatik suatu graf berkaitan dengan pewarnaan simpul, tetapi kita juga dapat menanyakan pewarnaan sisi. Seperti pada pewarnaan simpul, kita dapat mensyaratkan bahwa sisi-sisi yang bertetangga harus diberi warna berbeda. Di sini, dua sisi dianggap bertetangga apabila keduanya berinsiden dengan simpul yang sama. Jumlah warna minimum yang diperlukan untuk mewarnai sisi-sisi graf \(G\) secara tepat disebut indeks kromatik \(G\text{,}\) yang ditulis \(\chi'(G)\text{.}\)
🔗

Contoh 2.5.6.

Enam orang teman memutuskan untuk menghabiskan sore dengan bermain catur. Setiap orang akan bermain satu kali melawan setiap orang lainnya. Mereka memiliki cukup banyak perangkat catur, tetapi tidak seorang pun ingin memainkan lebih dari satu pertandingan pada saat yang sama. Setiap pertandingan berlangsung selama satu jam (berkat jam catur mereka yang praktis). Berapa jam turnamen tersebut akan berlangsung?
🔗
Penyelesaian.
Representasikan setiap pemain dengan sebuah simpul dan tempatkan sebuah sisi di antara dua pemain apabila mereka saling bertanding. Dalam kasus ini, kita memperoleh graf \(K_6\text{:}\)
🔗
Graf K6: enam simpul (tersusun melingkar), yang masing-masing bertetangga dengan lima simpul lainnya.
Kita harus mewarnai sisi-sisinya; setiap warna merepresentasikan jam yang berbeda. Karena sisi-sisi berbeda yang berinsiden dengan simpul yang sama akan diberi warna berbeda, tidak ada pemain yang memainkan dua pertandingan (sisi) berbeda pada saat yang sama. Jadi, kita perlu mengetahui indeks kromatik \(K_6\text{.}\)
🔗
Perhatikan bahwa pasti berlaku \(\chi'(K_6) \ge 5\) karena terdapat simpul berderajat 5. Ternyata 5 warna sudah cukup (cobalah temukan pewarnaan semacam itu). Oleh karena itu, keenam teman tersebut akan bermain selama 5 jam.
🔗
🔗
🔗
Menariknya, jika salah satu teman dalam contoh di atas pergi, kelima pecatur yang tersisa tetap memerlukan 5 jam: indeks kromatik \(K_5\) juga 5.
🔗
Secara umum, apa yang dapat kita katakan tentang indeks kromatik? Tentu saja \(\chi'(G) \ge \Delta(G)\text{.}\) Namun, seberapa jauh lebih besar nilainya? Ternyata hanya sedikit lebih besar.
🔗
Sekilas, teorema ini membuat indeks kromatik tampak kurang menarik. Namun, menentukan suatu graf termasuk dalam kasus yang mana tidak selalu mudah. Graf yang memenuhi \(\chi'(G) = \Delta(G)\) disebut kelas 1, sedangkan graf lainnya disebut kelas 2. Graf bipartit selalu memenuhi \(\chi'(G) = \Delta(G)\text{,}\) sehingga termasuk kelas 1 (hal ini dibuktikan oleh König pada tahun 1916, beberapa dasawarsa sebelum Vizing membuktikan teoremanya pada tahun 1964). Pada tahun 1965, Vizing membuktikan bahwa semua graf planar dengan \(\Delta(G) \ge 8\) termasuk kelas 1, tetapi hal ini tidak berlaku bagi semua graf planar dengan \(2 \le \Delta(G) \le 5\text{.}\) Vizing mengajukan konjektur bahwa semua graf planar dengan \(\Delta(G) = 6\) atau \(\Delta(G) = 7\) termasuk kelas 1; kasus \(\Delta(G) = 7\) dibuktikan pada tahun 2001 oleh Sanders dan Zhao; kasus \(\Delta(G) = 6\) masih terbuka.
🔗

Teori Ramsey.

Ada cara menarik lain untuk meninjau pewarnaan sisi, yang sangat berbeda dari pembahasan kita sejauh ini. Bagaimana jika setiap sisi graf kita warnai merah atau biru? Dapatkah kita melakukannya tanpa, misalnya, membentuk segitiga monokromatik (yaitu, segitiga yang seluruh sisinya merah atau seluruh sisinya biru)? Untuk graf tertentu, jawabannya tentu saja ya. Cobalah melakukannya untuk \(K_4\text{.}\) Bagaimana dengan \(K_5\text{?}\) \(K_6\text{?}\) Sampai sejauh mana kita dapat melakukannya?
🔗
Masalah di atas tidak terlalu sulit dan merupakan latihan yang menyenangkan. Kita dapat memperluas pertanyaan tersebut dengan berbagai cara. Bagaimana jika kita memiliki tiga warna? Bagaimana jika kita berusaha menghindari graf lain? Mengejutkan bahwa masih sangat sedikit yang diketahui tentang pertanyaan-pertanyaan ini. Sebagai contoh, kita mengetahui bahwa diperlukan hingga \(K_{17}\) untuk memaksa terbentuknya segitiga monokromatik dengan tiga warna, tetapi belum diketahui seberapa besar graf yang diperlukan jika digunakan lebih banyak warna. Demikian pula, kita mengetahui bahwa dengan dua warna, \(K_{18}\) adalah graf terkecil yang memaksa terbentuknya salinan monokromatik \(K_4\text{,}\) tetapi untuk memaksa terbentuknya \(K_{5}\) monokromatik, hasil terbaik yang kita miliki masih berupa rentang, yaitu dari \(K_{43}\) hingga \(K_{49}\text{.}\) Jika Anda tertarik pada pertanyaan semacam ini, bidang teori graf ini disebut teori Ramsey. Silakan pelajari lebih lanjut.
🔗
🔗
🔗

Pertanyaan Bacaan Pertanyaan Bacaan

1.

Benar atau salah: jika suatu graf memuat simpul berderajat 5, bilangan kromatik graf tersebut sedikitnya 5. Jelaskan.
🔗
🔗

2.

Dengan kata-kata Anda sendiri, jelaskan perbedaan antara bilangan kromatik dan indeks kromatik.
🔗
🔗

3.

Pertanyaan apa yang Anda miliki setelah membaca bagian ini? Tuliskan sedikitnya satu pertanyaan tentang isi bagian ini yang membuat Anda ingin tahu lebih jauh.
🔗
🔗
🔗

Latihan Latihan Soal

1.

Setiap masalah berikut dapat diselesaikan dengan mencari bilangan kromatik atau indeks kromatik suatu graf.
🔗
Untuk setiap masalah, tentukan apakah penyelesaiannya memerlukan pewarnaan sejati pada simpul atau pada sisi graf. Catatan: informasi yang diberikan mungkin belum cukup untuk benar-benar menyelesaikan masalah, dan itu tidak menjadi persoalan. Anda hanya perlu menentukan apakah pada prinsipnya masalah tersebut merupakan penerapan pewarnaan sisi atau pewarnaan simpul.
🔗
  1. Profesor Snape menyimpan bahan-bahan ramuan dalam sesedikit mungkin lemari, tetapi beberapa bahan tidak boleh disimpan dalam lemari yang sama karena dapat berinteraksi secara berbahaya. Berapa banyak lemari yang diperlukan?
    🔗
    🔗
  2. Dalam kejuaraan tic-tac-toe dunia, setiap pemain harus bertanding melawan tujuh pemain lain. Pertandingan baru dimulai setiap jam. Berapa jam turnamen tersebut akan berlangsung?
    🔗
    🔗
  3. Guru Anda ingin membuat beberapa versi ujian akhir agar tidak ada dua siswa yang duduk dalam jarak empat kaki satu sama lain dan menerima versi ujian yang sama. Berapa banyak versi yang diperlukan?
    🔗
    🔗
  4. Departemen matematika ingin menjadwalkan ujian tengah semester bersama yang masing-masing berlangsung sehari selama libur semester. Seorang mahasiswa yang mengambil dua mata kuliah harus mengikuti kedua ujian itu pada hari yang berbeda, dan inilah satu-satunya kendala penjadwalannya. Berapa hari ujian yang diperlukan?
    🔗
    🔗
🔗
🔗

2.

Berapakah bilangan kromatik setiap graf berikut?
🔗
\(P_{15}\)
🔗
\(C_{6}\)
🔗
\(C_{5}\)
🔗
\(K_{5, 15}\)
🔗
\(K_{5}\)
🔗
🔗

3.

Berapakah indeks kromatik setiap graf berikut?
🔗
\(P_{5}\)
🔗
\(C_{14}\)
🔗
\(C_{9}\)
🔗
\(K_{5, 15}\)
🔗
\(K_{14}\)
🔗
🔗

4.

Pernyataan-pernyataan berikut membahas bilangan kromatik \(\chi(G)\) dan indeks kromatik \(\chi'(G)\) suatu graf. Kita menggunakan \(\Delta(G)\) untuk derajat maksimum \(G\text{.}\)
🔗
Apakah pernyataan-pernyataan berikut benar atau salah?
🔗
  1. Jika setiap simpul pada suatu graf berderajat paling besar 7, maka indeks kromatik graf tersebut sekurang-kurangnya 7.
    🔗
    🔗
  2. \(\chi'(G) \ge \Delta(G)\text{.}\)
    🔗
    🔗
  3. Untuk setiap siklus, indeks kromatik sama dengan bilangan kromatik.
    🔗
    🔗
  4. Untuk setiap \(n \ge 3\text{,}\) \(\chi'(K_n) = \Delta(K_n)\text{.}\)
    🔗
    🔗
🔗
🔗

5.

Berapakah bilangan kromatik setiap graf?
🔗
graf yang bilangan kromatiknya harus ditentukan
graf yang bilangan kromatiknya harus ditentukan
graf yang bilangan kromatiknya harus ditentukan
graf yang bilangan kromatiknya harus ditentukan
🔗
🔗

Latihan Latihan Tambahan

1.

Berapakah jumlah warna paling sedikit yang diperlukan untuk mewarnai simpul-simpul \(K_{4,5}\) secara tepat? Dengan kata lain, tentukan bilangan kromatik graf tersebut.
🔗
🔗

2.

Gambarlah sebuah graf dengan bilangan kromatik 6 (yaitu graf yang memerlukan 6 warna untuk mewarnai simpul-simpulnya secara tepat). Dapatkah graf Anda berupa graf planar? Jelaskan.
🔗
🔗

3.

Tentukan bilangan kromatik setiap graf berikut.
🔗
Sebuah graf dengan lima simpul yang tersusun membentuk belah ketupat dan satu simpul berada di tengah. Simpul teratas terhubung ke dua simpul luar di bawahnya, yang masing-masing terhubung ke simpul terbawah. Simpul tengah terhubung ke simpul di sebelah kiri dan kanannya.
Graf C7: tujuh simpul tersusun melingkar, dengan sisi-sisi yang menghubungkan simpul-simpul bertetangga sehingga membentuk poligon bersisi tujuh.
Lima simpul membentuk segilima dengan simpul keenam di tengah. Sisi-sisi membentuk keliling segilima, dan simpul tengah bertetangga dengan setiap simpul luar.
Graf K5: lima simpul yang tersusun membentuk segilima, dengan setiap simpul bertetangga dengan semua simpul lainnya.
Graf Petersen: sepuluh simpul tersusun dalam dua lingkaran yang masing-masing terdiri atas lima simpul. Setiap simpul luar bertetangga dengan dua simpul luar terdekat sehingga membentuk segilima, serta dengan simpul dalam terdekat. Setiap simpul dalam bertetangga dengan dua simpul dalam yang tidak berada tepat di sebelahnya sehingga membentuk bintang bersudut lima.
🔗

4.

Sekelompok 10 teman memutuskan pergi ke sebuah pondok di hutan (tempat yang tentunya mustahil menjadi lokasi terjadinya masalah). Sayangnya, beberapa di antara mereka pernah berpacaran satu sama lain dan hubungan mereka masih agak canggung. Untuk mencapai pondok tersebut, mereka perlu membagi diri ke dalam sejumlah mobil, dan dua orang yang pernah berpacaran tidak boleh berada di mobil yang sama.
🔗
(a)
Berapakah jumlah mobil paling sedikit yang diperlukan jika semua hubungan tersebut hanya bersifat heteroseksual? Representasikan sebuah contoh situasi semacam itu dengan graf. Jenis graf apakah yang Anda peroleh?
🔗
🔗
(b)
Karena beberapa teman tersebut pernah berpacaran, terdapat pula konflik di antara teman-teman dengan gender yang sama, seperti tercantum di bawah ini. Sekarang, berapakah jumlah mobil bebas konflik paling sedikit yang dapat mereka gunakan untuk pergi ke pondok?
🔗
Teman A B C D E F G H I J
Konflik CFJ J AEF H CFG ACEGI EFI D AFG B
🔗
🔗

5.

Berapakah jumlah warna paling sedikit yang dapat digunakan untuk mewarnai simpul-simpul kubus sehingga tidak ada dua simpul bertetangga yang diberi warna sama?
🔗
🔗

6.

Buktikan bahwa bilangan kromatik setiap pohon adalah dua. Ingat bahwa pohon adalah graf terhubung yang tidak memiliki siklus.
🔗
(a)
Perhatikan pohon berikut. Jika Anda mewarnai simpul paling kiri dengan warna merah, warna apakah yang harus diberikan kepada tetangganya? Warna apakah yang harus diberikan kepada tetangga-tetangga dari simpul tersebut? Jelaskan suatu prosedur untuk mewarnai pohon berikut dengan dua warna.
🔗
Sebuah pohon dengan 28 simpul.
🔗
(b)
Jika Anda menggunakan prosedur yang sama untuk mewarnai suatu siklus, apakah Anda selalu dapat mewarnainya dengan dua warna?
🔗
🔗
(c)
Buktikan bahwa prosedur Anda dari bagian (a) selalu berhasil untuk setiap pohon.
🔗
Petunjuk.
Apakah pada akhirnya Anda akan mewarnai setiap simpul dengan mengikuti prosedur tersebut? Mungkinkah ada simpul yang tidak dapat Anda warnai sesuai prosedur itu?
🔗
🔗
🔗
(d)
Sekarang, berikan bukti lain dengan menggunakan induksi bahwa setiap pohon memiliki bilangan kromatik 2.
🔗
🔗
🔗

7.

Kedua masalah berikut dapat diselesaikan dengan menggunakan pewarnaan graf. Untuk setiap masalah, representasikan situasinya dengan graf, nyatakan apakah Anda perlu mewarnai simpul atau sisi beserta alasannya, lalu gunakan pewarnaan tersebut untuk menyelesaikan masalah.
🔗
(a)
Liga Quidditch Anda memiliki 5 tim. Minggu depan akan diadakan turnamen yang mempertemukan setiap tim dengan setiap tim lainnya tepat satu kali. Setiap tim hanya dapat memainkan paling banyak satu pertandingan per hari, tetapi tersedia cukup waktu dalam sehari untuk mengadakan beberapa pertandingan. Berapa harikah waktu paling singkat yang diperlukan untuk menyelenggarakan turnamen tersebut?
🔗
Petunjuk.
Representasikan tim sebagai simpul dan pertandingan sebagai sisi. Manakah yang lebih tepat untuk diwarnai?
🔗
🔗
🔗
(b)
Sepuluh anggota Klub Matematika akan berkendara ke sebuah konferensi matematika di negara bagian tetangga. Namun, beberapa siswa tersebut pernah berpacaran dan hubungan mereka masih agak canggung. Setiap siswa mencantumkan siswa lain yang tidak bersedia berbagi mobil dengannya; konflik-konflik tersebut dicatat dalam tabel berikut. Berapakah jumlah mobil paling sedikit yang diperlukan klub untuk melakukan perjalanan itu? Abaikan keterbatasan jumlah tempat duduk; cukup hindari konflik yang ada.
🔗
Siswa: A B C D E F G H I J
Konflik: BEJ ADG HJ BF AI DJ B CI EHJ ACFI
🔗
🔗

8.

Buktikan teorema enam warna: setiap graf planar memiliki bilangan kromatik paling banyak 6. Jangan mengasumsikan teorema empat warna (yang pembuktiannya JAUH lebih sulit), tetapi Anda boleh mengasumsikan fakta bahwa setiap graf planar memuat sebuah simpul berderajat paling banyak 5.
🔗
🔗

9.

Tidak semua graf merupakan graf sempurna. Berikan contoh graf dengan bilangan kromatik 4 yang tidak memuat salinan \(K_4\text{.}\) Dengan kata lain, tidak boleh terdapat 4 simpul yang seluruh pasangannya saling bertetangga.
🔗
🔗

10.

Tentukan bilangan kromatik graf berikut dan buktikan bahwa jawaban Anda benar.
🔗
Sebuah graf dengan 11 simpul. Terdapat satu simpul di pusat, lima simpul yang berjarak sama pada lingkaran di sekelilingnya, dan lima simpul lain yang berjarak sama pada lingkaran luar. Sisi-sisi pada lingkaran luar membentuk sebuah segilima. Setiap simpul luar juga bertetangga dengan dua simpul dalam, yaitu dua simpul yang mengapit simpul dalam terdekat. Terakhir, setiap simpul dalam juga bertetangga dengan simpul pusat.
Petunjuk.
Bilangan kromatiknya adalah 4. Sekarang, buktikanlah!
🔗
Perhatikan bahwa di sini Anda tidak dapat menggunakan teorema empat warna, teorema Brooks, ataupun bilangan klik. Faktanya, graf ini, yang disebut graf Grötzsch, merupakan graf terkecil dengan bilangan kromatik 4 yang tidak memuat segitiga.
🔗
🔗
🔗

11.

Buktikan bahwa setiap graf terhubung \(G\) yang memuat setidaknya satu simpul dengan derajat kurang dari \(\Delta(G)\) (derajat maksimum di antara semua simpul dalam \(G\)) memiliki bilangan kromatik paling banyak \(\Delta(G)\text{.}\)
🔗
🔗

12.

Anda memiliki satu set huruf alfabet magnetis (masing-masing satu dari 26 huruf dalam alfabet) yang perlu dimasukkan ke dalam kotak-kotak. Untuk alasan yang jelas, Anda tidak ingin menempatkan dua huruf berurutan dalam kotak yang sama. Berapakah jumlah kotak paling sedikit yang diperlukan (dengan asumsi setiap kotak mampu menampung huruf sebanyak yang diperlukan)?
🔗
🔗

13.

Misalkan Anda mewarnai setiap sisi suatu graf dengan warna merah atau biru (tanpa mensyaratkan bahwa sisi-sisi bertetangga harus diberi warna berbeda). Sifat apakah yang harus dimiliki graf tersebut agar dijamin terdapat suatu simpul yang bersisian dengan tiga sisi berwarna sama? Buktikan jawaban Anda.
🔗
Petunjuk.
Anda dapat mewarnai \(K_5\) sedemikian rupa sehingga setiap simpul bersisian dengan tepat dua sisi biru dan dua sisi merah. Namun, terdapat sebuah graf dengan hanya 5 sisi yang pasti menghasilkan suatu simpul yang bersisian dengan tiga sisi berwarna sama, apa pun pewarnaan sisi-sisinya. Graf apakah itu, dan bagaimana Anda dapat menggeneralisasikannya?
🔗
🔗
🔗

14.

Buktikan bahwa jika Anda mewarnai setiap sisi \(K_6\) dengan warna merah atau biru, pasti terdapat sebuah segitiga monokromatik (yaitu segitiga yang seluruh sisinya merah atau seluruh sisinya biru).
🔗
Petunjuk.
Latihan sebelumnya berguna sebagai titik awal.
🔗
🔗
🔗
🔗
🔗
SblmTopLnjt
Umpan Balik