Gambarlah graf dengan \(8\) simpul yang semuanya berderajat ganjil dan tidak mengandung lintasan dengan panjang \(3\text{,}\) atau jelaskan mengapa graf semacam itu tidak ada.
Gambarlah graf dengan \(6\) simpul yang derajatnya berturut-turut \(5\text{,}\)\(4\text{,}\)\(4\text{,}\)\(2\text{,}\)\(1\text{,}\) dan \(1\text{,}\) atau jelaskan mengapa graf semacam itu tidak ada.
Untuk Olimpiade Musim Dingin berikutnya, panitia ingin menambah jumlah tim yang bertanding dalam cabang curling. Mereka ingin mengikutsertakan \(14\) tim yang dibagi menjadi dua grup, masing-masing berisi tujuh tim. Dalam rancangan saat ini, pada babak penyisihan setiap tim harus memainkan tujuh pertandingan melawan lawan yang berbeda: lima lawan berasal dari grup yang sama dan dua lawan dari grup lain. Panitia kesulitan menyusun jadwal tersebut dan meminta bantuan Anda. Dengan menggunakan model teori graf yang sesuai, buktikan bahwa rancangan itu tidak dapat diterapkan atau susunlah cara untuk menerapkannya.
Gambar 5.49 memuat empat graf dengan enam simpul. Tentukan pasangan graf mana saja, jika ada, yang isomorfik. Untuk pasangan yang isomorfik, berikan suatu isomorfisme di antara keduanya. Untuk pasangan yang tidak isomorfik, jelaskan alasannya.
Empat graf dengan enam simpul, berlabel G satu hingga G empat; tata letaknya berbeda-beda sehingga struktur derajat dan ketetanggaannya perlu dibandingkan untuk menentukan isomorfisme.
Perhatikan graf \(\bfG\) pada Gambar 5.51. Tentukan apakah graf tersebut Euler. Jika ya, temukan sebuah sirkuit Euler; jika tidak, jelaskan alasannya. Tentukan pula apakah graf tersebut Hamilton. Jika ya, temukan sebuah siklus Hamilton; jika tidak, jelaskan alasannya.
Jelaskan mengapa graf \(\bfG\) pada Gambar 5.52 tidak memiliki sirkuit Euler, lalu tunjukkan bahwa penambahan satu sisi dapat menjadikannya graf Euler.
Jejak Euler didefinisikan dengan cara yang sama seperti sirkuit Euler (lihat Subbab 5.3), kecuali bahwa syarat \(x_0=x_t\) dihapus. Buktikan bahwa suatu graf memiliki jejak Euler jika dan hanya jika graf itu terhubung dan memiliki paling banyak dua simpul berderajat ganjil.
Alice dan Bob sedang membahas graf dengan \(17\) simpul dan \(129\) sisi. Bob menyatakan bahwa graf itu Hamilton, sedangkan Alice menyatakan bahwa Bob keliru. Tanpa mengetahui informasi lain tentang graf tersebut, apakah salah satu dari mereka pasti benar? Jika ya, siapa dan mengapa? Jika tidak, jelaskan alasannya.
Sebuah produsen farmasi sedang membangun gudang baru untuk menyimpan persediaan \(10\) bahan kimia yang digunakan dalam produksi. Sebagian bahan kimia tidak boleh disimpan dalam ruangan yang sama karena dapat menimbulkan reaksi yang tidak diinginkan. Matriks berikut berisi \(1\) pada posisi \((i,j)\) jika dan hanya jika bahan kimia \(i\) dan bahan kimia \(j\) tidak boleh disimpan dalam ruangan yang sama. Susunlah model teori graf yang sesuai dan tentukan jumlah minimum ruangan yang harus dibuat di dalam gudang agar seluruh \(10\) bahan kimia dapat disimpan dengan aman.
Sebuah sekolah sedang menyusun jadwal pelajaran untuk tahun ajaran berikutnya. Sekolah itu akan menawarkan masing-masing satu kelas Kalkulus, Fisika, Bahasa Inggris, Statistika, Ekonomi, Kimia, dan Bahasa Jerman. Berikut adalah daftar mata pelajaran yang harus diambil oleh masing-masing dari enam siswa agar dapat lulus. Tentukan jumlah minimum jam pelajaran yang dapat digunakan untuk menjadwalkan semua mata pelajaran jika setiap siswa hanya dapat mengikuti paling banyak satu mata pelajaran pada setiap jam. Jelaskan mengapa jumlah jam yang lebih sedikit tidak mungkin digunakan.
Temukan pewarnaan tepat dengan \((t+1)\) warna untuk graf \(\bfG_{t+1}\) dalam bukti Mycielski bagi Proposisi 5.26. Hasil ini menunjukkan bahwa \(\chi(\bfG_{t+1})\leq t+1\text{.}\)
Misalkan \(b_t\) menyatakan banyaknya simpul dalam graf \(\bfG_t\) dari bukti Mycielski bagi Proposisi 5.26. Temukan rumus rekursif untuk \(b_t\text{.}\)
Girth suatu graf \(\bfG\) adalah banyaknya simpul dalam siklus terpendek dari \(\bfG\text{.}\) Tentukan girth graf \(\bfG_t\) dalam bukti Kelly dan Kelly bagi Proposisi 5.26, lalu buktikan bahwa jawaban Anda benar. Sebagai tantangan, cobalah mengubah konstruksi \(\bfG_t\) untuk memperbesar girth. Jika berhasil, seberapa besar Anda dapat memperbesarnya?
Gunakan algoritma pewarnaan First Fit untuk menentukan bilangan kromatik graf interval yang representasi intervalnya ditampilkan pada Gambar 5.55, serta berikan pewarnaan tepat dengan sesedikit mungkin warna.
Dari Latihan 5.9.24, Anda mengetahui bahwa urutan simpul yang buruk dapat membuat algoritma pewarnaan First Fit menghasilkan pewarnaan yang jauh dari optimal. Namun, algoritma ini dapat digunakan untuk membuktikan batas bilangan kromatik. Tunjukkan bahwa jika setiap simpul \(\bfG\) berderajat paling besar \(D\text{,}\) maka \(\chi(\bfG)\leq D+1\text{.}\)
Temukan penggambaran planar graf \(\bfK_5-e\text{,}\) yaitu graf yang dibentuk dari graf lengkap dengan \(5\) simpul dengan menghapus sembarang satu sisi.
Misalkan \(\GVE\) merupakan graf dengan \(V=\{v_1,v_2,\dots,v_n\}\text{.}\)Barisan derajat graf tersebut adalah daftar derajat simpul-simpulnya yang disusun dalam urutan tak naik. Jadi, barisan derajat \(\mathbf{G}\) adalah \((\deg_\mathbf{G}(v_1),\deg_\mathbf{G}(v_2),\dots,\deg_\mathbf{G}(v_n))\text{,}\) dengan simpul-simpul disusun sedemikian sehingga \(\deg_\mathbf{G}(v_1) \geq \deg_\mathbf{G}(v_2)\geq \cdots\geq \deg_\mathbf{G}(v_n)\text{.}\) Berikut diberikan lima barisan bilangan bulat beserta \(n\text{,}\) yaitu banyaknya bilangan dalam barisan. Tentukan
satu barisan yang tidak mungkin menjadi barisan derajat graf mana pun;
Berikut diberikan tiga barisan dengan panjang \(10\text{.}\) Salah satunya tidak mungkin menjadi barisan derajat (lihat Latihan 5.9.33) graf mana pun. Tentukan barisan tersebut dan jelaskan alasannya. Untuk masing-masing dari dua barisan lainnya, jelaskan mengapa, jika informasinya cukup, graf terhubung dengan barisan derajat itu
(Jika Anda tidak memiliki cukup informasi untuk menentukan suatu sifat tanpa melihat graf tertentu dengan barisan derajat tersebut, tulislah “informasi tidak cukup” untuk sifat itu.)
Untuk kedua barisan derajat pada Latihan 5.9.34 yang bersesuaian dengan graf, terdapat beberapa sifat yang tidak dapat ditentukan hanya dari barisan derajat. Untuk setiap keadaan tersebut, cobalah menggambar satu graf yang memiliki sifat itu dan satu graf yang tidak memilikinya.
Bangunlah pohon berlabel \(\bfT\) dengan kode Prüfer berikut; tanda koma digunakan untuk memisahkan simbol dalam string karena terdapat label yang lebih besar dari \(9\text{:}\)\(10,1,7,4,3,4,10,2,2,8\text{.}\)
(Soal tantangan) Jika \(\GVE\) adalah graf, misalkan \(\Delta(\bfG)\) menyatakan derajat maksimum dalam \(\bfG\text{.}\) Buktikan Teorema Brooks: Jika \(\bfG\) terhubung dan \(\Delta(\bfG)=k\text{,}\) maka \(\chi(\bfG)\le k+1\text{.}\) Selanjutnya, kesamaan berlaku jika dan hanya jika (a) \(k=2\) dan \(\bfG\) merupakan siklus ganjil, atau (b) \(k\neq2\) dan \(\bfG=\bfK_{k+1}\text{.}\)
Petunjuk: Jelas bahwa \(\chi(\bfG)\le k+1\text{;}\) bahkan, hasil ini sudah diberikan sebagai latihan. Andaikan \(\chi(\bfG)=k+1\text{,}\) tetapi kesimpulan (a) maupun (b) tidak berlaku. Ambil pohon rentang dari \(\bfG\) dan urutan simpul yang sesuai, dengan dua daun pohon ditempatkan paling awal. Kemudian tunjukkan bahwa pewarnaan First Fit pada graf hanya menggunakan \(k\) warna.
