Lewati ke konten utama
Gambar logo

Subbab 2.3 Graf Planar

Subbagian Pratinjau Bagian

Selidiki!
Jika suatu graf terhubung dapat digambar tanpa ada sisi yang berpotongan, graf tersebut disebut planar. Ketika graf planar digambar dengan cara ini, graf tersebut membagi bidang menjadi wilayah-wilayah yang disebut muka.
  1. Jika mungkin, gambarkan dua graf planar berbeda dengan jumlah simpul, sisi, dan muka yang sama.
  2. Jika mungkin, gambarkan dua graf planar berbeda dengan jumlah simpul dan sisi yang sama, tetapi jumlah muka yang berbeda.
Kapan suatu graf dapat digambar sehingga tidak ada sisi yang berpotongan? Jika hal ini memang mungkin, kita mengatakan bahwa graf tersebut planar (karena dapat digambar pada suatu bidang).
Perhatikan bahwa definisi planar memuat frasa “dapat digambar.” Artinya, meskipun suatu graf tidak tampak planar, graf tersebut mungkin tetap planar. Barangkali graf itu dapat digambar ulang tanpa ada sisi yang berpotongan. Sebagai contoh, berikut adalah graf planar:
Gambar K2,3 dengan dua simpul pada baris atas; masing-masing bertetangga dengan ketiga simpul pada baris bawah.
Alasannya, graf tersebut dapat digambar ulang seperti berikut:
Gambar lain dari K2,3. Satu simpul pada baris atas bertetangga dengan tiga simpul yang berjajar di bawahnya. Masing-masing dari ketiga simpul tersebut bertetangga dengan satu simpul yang berada di bawah dan di sebelah kanannya.
Kedua graf tersebut sama, sehingga jika salah satunya planar, yang lain juga harus planar. Namun, gambar awal graf tersebut bukan representasi planar dari graf itu.
Ketika graf planar digambar tanpa sisi yang berpotongan, sisi dan simpul graf membagi bidang menjadi sejumlah wilayah. Setiap wilayah ini kita sebut muka. Graf di atas memiliki 3 muka (ya, kita juga menghitung wilayah “luar” sebagai muka). Jumlah muka tidak berubah, bagaimanapun graf tersebut digambar (selama tidak ada sisinya yang berpotongan), sehingga wajar untuk menganggap jumlah muka sebagai sifat graf planar.
PERINGATAN: muka hanya dapat dihitung ketika graf digambar secara planar. Sebagai contoh, perhatikan dua representasi dari graf yang sama berikut:
Gambar K4 dengan empat simpul yang tersusun membentuk persegi; sisi-sisinya membentuk keliling persegi, ditambah dua sisi yang berpotongan di tengah.
Gambar K4 dengan empat simpul yang tersusun membentuk persegi dan sisi-sisi yang membentuk keliling persegi. Satu sisi lainnya membentang dari sudut kiri bawah ke sudut kanan atas. Sebuah sisi melengkung melewati bagian luar persegi dari simpul kiri atas ke simpul kanan bawah. Tidak ada sisi yang berpotongan.
Jika Anda mencoba menghitung muka menggunakan graf di sebelah kiri, Anda mungkin mengatakan bahwa terdapat 5 muka (termasuk muka luar). Namun, representasi planar graf tersebut menunjukkan bahwa sebenarnya hanya terdapat 4 muka.

Lembar Kerja Kegiatan Pratinjau

1.
(a)
Gambarkan graf planar terhubung dengan 5 simpul dan 5 sisi. Berapa banyak muka (termasuk muka “luar”) yang dimiliki graf Anda?
Jumlah muka:
(b)
Sekarang tambahkan satu sisi pada graf Anda di antara dua simpul yang belum bertetangga. Dengan mengasumsikan graf yang dihasilkan tetap planar, tuliskan jumlah simpul, sisi, dan muka yang sekarang dimilikinya.
Simpul: ; Sisi: ; Muka:
(c)
Sekarang tambahkan satu sisi lagi pada graf, kali ini menuju simpul baru. Dengan mengasumsikan graf yang dihasilkan tetap planar, tuliskan jumlah simpul, sisi, dan muka yang sekarang dimilikinya.
Simpul: ; Sisi: ; Muka:
2.
Sekarang gambarkan sedikitnya tiga graf planar terhubung lainnya, masing-masing dengan sedikitnya enam simpul. Hitung jumlah simpul \(v\text{,}\) sisi \(e\text{,}\) dan muka \(f\) untuk setiap graf, lalu catat data Anda pada tabel di bawah ini.
\(v\) \(e\) \(f\)
3.
Apakah Anda melihat suatu pola? Apa yang terjadi pada bilangan-bilangan tersebut jika Anda menambahkan sisi di antara dua simpul yang tidak bertetangga? Apa yang terjadi jika Anda menambahkan simpul baru dan menghubungkannya ke simpul yang sudah ada?
Buatlah konjektur berupa ekspresi yang melibatkan jumlah simpul \(v\text{,}\) jumlah sisi \(e\text{,}\) dan jumlah muka \(f\) yang tetap konstan untuk semua graf planar terhubung. Berapakah konstanta tersebut?
Ekspresi yang dikonjekturkan: .
Petunjuk.
Anda mungkin mengajukan konjektur berupa ekspresi seperti \(\frac{v+e}{f}\text{.}\) Namun, ekspresi ini tidak tepat karena terdapat graf planar yang menghasilkan \(\frac{5+5}{2} = 5\) dan graf planar lain yang menghasilkan \(\frac{6+7}{3} \ne 5\text{.}\)
Jenis ekspresi apa yang tetap konstan jika \(v\) dan \(e\) sama-sama bertambah 1? Dan juga tetap konstan jika \(e\) dan \(f\) sama-sama bertambah 1?
4.
Kubus tersusun atas enam persegi, yang masing-masing berbagi sisi dengan setiap persegi tetangganya. Setiap simpul kubus mempertemukan tiga persegi.
(a)
Berapa banyak simpul, sisi, dan muka yang dimiliki kubus?
Simpul: ; Sisi: ; Muka:

Subbagian Rumus Euler untuk Graf Planar

Terdapat hubungan antara jumlah simpul (\(v\)), jumlah sisi (\(e\)), dan jumlah muka (\(f\)) pada setiap graf planar terhubung. Hubungan ini disebut rumus Euler.

Rumus Euler untuk Graf Planar.

Untuk setiap graf planar terhubung dengan \(v\) simpul, \(e\) sisi, dan \(f\) muka, berlaku
\begin{equation*} v-e + f = 2\text{.} \end{equation*}
Mengapa rumus Euler benar? Salah satu cara untuk meyakinkan diri akan kesahihannya adalah menggambar graf planar selangkah demi selangkah. Mulailah dengan graf \(P_2\text{:}\)
Dua simpul yang dihubungkan oleh satu sisi.
Setiap graf terhubung (selain satu simpul terisolasi saja) pasti memuat subgraf ini. Sekarang kita membangun graf dengan menambahkan sisi dan simpul. Setiap langkah berupa penambahan simpul baru yang dihubungkan oleh sisi baru ke suatu bagian graf (sehingga membentuk “duri” baru) atau penghubungan dua simpul yang sudah ada pada graf dengan sisi baru (melengkapi suatu siklus).
Graf dengan empat simpul yang tersusun membentuk persegi. Simpul kiri atas bertetangga dengan ketiga simpul lainnya, dan simpul kanan atas juga bertetangga dengan simpul kanan bawah. Sebuah sisi putus-putus mengarah dari simpul kanan atas persegi ke simpul kelima di sebelah kanan bawahnya.
Graf dengan empat simpul yang tersusun membentuk persegi. Simpul kiri atas bertetangga dengan ketiga simpul lainnya, dan simpul kanan atas juga bertetangga dengan simpul kanan bawah. Sebuah sisi putus-putus menghubungkan kedua simpul bawah.
Apa akibat dari “langkah-langkah” ini? Ketika duri ditambahkan, jumlah sisi bertambah 1, jumlah simpul bertambah 1, dan jumlah muka tetap sama. Artinya, \(v - e + f\) tidak berubah. Melengkapi suatu siklus menambahkan satu sisi, menambahkan satu muka, dan mempertahankan jumlah simpul. Jadi, sekali lagi, \(v - e + f\) tidak berubah.
Karena kita dapat membangun graf apa pun dengan menggabungkan kedua langkah ini, dan langkah-langkah tersebut tidak pernah mengubah nilai \(v - e + f\text{,}\) nilai itu akan sama untuk semua graf. Namun, perhatikan bahwa graf awal \(P_2\) memiliki \(v = 2\text{,}\) \(e = 1\text{,}\) dan \(f = 1\text{,}\) sehingga \(v - e + f = 2\text{.}\)
Argumen yang diuraikan di atas belum sepenuhnya tepat karena kita membuat asumsi tanpa pembenaran bahwa semua graf dapat dibangun dari \(P_2\) hanya dengan kedua langkah tersebut. Untuk menghindari masalah ini, kita dapat menggunakan argumen penyangkal minimal. Anda diminta melakukannya dalam latihan, tetapi gagasannya pada dasarnya sama dengan yang dibahas di sini. Kita mulai dengan graf planar terhubung minimal yang tidak memenuhi rumus, lalu menghapus suatu sisi atau suatu simpul (beserta sisinya) untuk memperoleh graf planar terhubung yang lebih kecil dan memenuhi rumus. Sama seperti langkah penambahan yang dijelaskan di atas, penghapusan sisi atau simpul tidak mengubah nilai \(v - e + f\text{.}\)

Subbagian Graf Nonplanar

Selidiki!
Untuk graf lengkap \(K_n\text{,}\) kita ingin mengetahui jumlah simpul, sisi, dan (jika grafnya planar) muka. Pertama, perhatikan \(K_3\text{:}\)
  1. Berapa banyak simpul yang dimiliki \(K_3\text{?}\) Berapa banyak sisinya?
  2. Jika \(K_3\) planar, berapa banyak muka yang seharusnya dimilikinya?
Ulangi bagian (1) dan (2) untuk \(K_4\text{,}\) \(K_5\text{,}\) dan \(K_{23}\text{.}\)
Bagaimana dengan graf bipartit lengkap? Berapa banyak simpul, sisi, dan muka (jika graf tersebut planar) yang dimiliki \(K_{7,4}\text{?}\) Untuk nilai \(m\) dan \(n\) manakah \(K_n\) dan \(K_{m,n}\) planar?
Tidak semua graf bersifat planar. Jika terdapat terlalu banyak sisi dan terlalu sedikit simpul, beberapa sisi harus berpotongan. Graf terkecil yang mengalami hal ini adalah \(K_5\text{.}\)
Gambar K5: lima simpul tersusun membentuk segilima, dengan sisi-sisi yang menghubungkan setiap simpul ke setiap simpul lainnya.
Jika Anda mencoba menggambar ulang graf ini tanpa sisi yang berpotongan, kesulitan segera muncul. Tampaknya terdapat satu sisi terlalu banyak. Bahkan, kita dapat membuktikan bahwa bagaimanapun graf tersebut digambar, \(K_5\) akan selalu memiliki sisi yang berpotongan.

Bukti.

Pembuktian dilakukan dengan kontradiksi. Jadi, asumsikan bahwa \(K_5\) planar. Graf tersebut harus memenuhi rumus Euler untuk graf planar. \(K_5\) memiliki 5 simpul dan 10 sisi, sehingga diperoleh
\begin{equation*} 5 - 10 + f = 2\text{,} \end{equation*}
yang menyatakan bahwa jika graf digambar tanpa sisi yang berpotongan, akan terdapat \(f = 7\) muka.
Sekarang perhatikan banyaknya sisi yang mengelilingi setiap muka. Setiap muka harus dikelilingi oleh sedikitnya 3 sisi. Misalkan \(B\) adalah jumlah seluruh batas di sekeliling semua muka pada graf. Dengan demikian, \(3f \le B\text{.}\) Selain itu, \(B = 2e\) karena setiap sisi digunakan sebagai batas tepat dua kali. Dengan menggabungkan keduanya, diperoleh
\begin{equation*} 3f \le 2e\text{.} \end{equation*}
Namun, hal ini mustahil karena telah ditentukan bahwa \(f = 7\) dan \(e = 10\text{,}\) sedangkan \(21 \not\le 20\text{.}\) Ini merupakan kontradiksi, sehingga \(K_5\) sebenarnya tidak planar.
Graf paling sederhana lainnya yang tidak planar adalah \(K_{3,3}\)
Gambar K3,3 dengan tiga simpul berjajar di atas; masing-masing bertetangga dengan ketiga simpul yang berjajar tepat di bawahnya.
Pembuktian bahwa \(K_{3,3}\) tidak planar menjawab teka-teki klasik rumah dan layanan utilitas: tidak mungkin menghubungkan masing-masing dari tiga rumah ke masing-masing dari tiga layanan utilitas tanpa garis yang berpotongan.

Bukti.

Sekali lagi, kita menggunakan pembuktian dengan kontradiksi. Andaikan \(K_{3,3}\) planar. Berdasarkan rumus Euler, akan terdapat 5 muka karena \(v = 6\text{,}\) \(e = 9\text{,}\) dan \(6 - 9 + f = 2\text{.}\)
Berapa banyak batas yang mengelilingi kelima muka ini? Misalkan \(B\) adalah jumlah tersebut. Karena setiap sisi digunakan sebagai batas dua kali, berlaku \(B = 2e\text{.}\) Selain itu, \(B \ge 4f\) karena setiap muka dikelilingi oleh 4 batas atau lebih. Hal ini benar karena \(K_{3,3}\) bipartit, sehingga tidak memuat siklus dengan 3 sisi. Dengan demikian,
\begin{equation*} 4f \le 2e\text{.} \end{equation*}
Namun, ini akan menyatakan bahwa \(20 \le 18\text{,}\) yang jelas salah. Jadi, \(K_{3,3}\) tidak planar.
Perhatikan persamaan dan perbedaan kedua pembuktian ini. Keduanya merupakan pembuktian dengan kontradiksi, dan keduanya diawali dengan penggunaan rumus Euler untuk memperoleh jumlah muka yang semestinya pada graf. Kemudian kita mencari hubungan antara jumlah muka dan jumlah sisi berdasarkan banyaknya sisi yang mengelilingi setiap muka. Inilah satu-satunya perbedaannya. Dalam pembuktian untuk \(K_5\text{,}\) diperoleh \(3f \le 2e\text{,}\) sedangkan untuk \(K_{3,3}\) diperoleh \(4f \le 2e\text{.}\) Koefisien \(f\) merupakan kuncinya. Koefisien tersebut adalah jumlah sisi terkecil yang dapat mengelilingi suatu muka. Jika sejumlah sisi mengelilingi suatu muka, sisi-sisi tersebut membentuk siklus. Jadi, jumlah itu adalah panjang siklus terpendek pada graf.
Secara umum, misalkan \(g\) adalah panjang siklus terpendek pada suatu graf (\(g\) berasal dari istilah teknis bahasa Inggris girth) sehingga untuk setiap graf planar berlaku \(gf \le 2e\text{.}\) Ketika pertidaksamaan ini tidak sesuai dengan rumus Euler, kita mengetahui dengan pasti bahwa graf tersebut tidak mungkin planar.
 7 
Perhatikan bahwa karena alasan teknis, panjang siklus terpendek pada graf tanpa siklus (hutan) didefinisikan sebagai tak hingga. Dalam kasus ini, \(gf \le 2e\) jelas tidak berlaku, meskipun semua pohon bersifat planar.

Subbagian Polihedron

Selidiki!
Kubus merupakan contoh polihedron konveks. Kubus memiliki 6 persegi identik sebagai mukanya, 8 simpul, dan 12 sisi. Kubus merupakan polihedron beraturan (juga dikenal sebagai bangun ruang Platonik) karena setiap muka berupa poligon beraturan yang identik dan setiap simpul mempertemukan jumlah muka yang sama.
Terdapat tepat empat polihedron beraturan lainnya: tetrahedron, oktahedron, dodekahedron, dan ikosahedron, yang masing-masing memiliki 4, 8, 12, dan 20 muka. Berapa banyak simpul dan sisi yang dimiliki masing-masing polihedron tersebut?
Cabang matematika lain yang menggunakan istilah “simpul,” “sisi,” dan “muka” adalah geometri. Polihedron adalah bangun ruang geometris yang tersusun atas muka-muka poligonal datar yang bertemu pada sisi dan simpul. Kita terutama tertarik pada polihedron konveks, yaitu polihedron yang setiap ruas garis penghubung dua titik di bagian dalamnya seluruhnya terletak di dalam polihedron tersebut.
 8 
Definisi alternatif untuk konveks adalah bahwa sudut dalam yang dibentuk oleh sembarang dua muka harus kurang dari \(180\deg\text{.}\)
Perhatikan bahwa karena \(8 - 12 + 6 = 2\text{,}\) simpul, sisi, dan muka kubus memenuhi rumus Euler untuk graf planar. Hal ini bukan suatu kebetulan. Kubus dapat direpresentasikan sebagai graf planar dengan memproyeksikan simpul dan sisinya ke bidang. Salah satu proyeksi tersebut tampak seperti berikut:
Delapan simpul tersusun sebagai sebuah persegi kecil di dalam persegi yang lebih besar. Sisi-sisi membentuk keliling kedua persegi dan menghubungkan setiap simpul persegi kecil ke simpul terdekat pada persegi besar.
Bahkan, setiap polihedron konveks dapat diproyeksikan ke bidang tanpa sisi yang berpotongan. Bayangkan polihedron ditempatkan di dalam sebuah bola, dengan sumber cahaya di pusat bola. Sisi dan simpul polihedron membentuk bayangan pada permukaan bagian dalam bola. Kemudian, lubangi bola di tengah salah satu muka yang diproyeksikan dan “rentangkan” bola hingga terhampar rata pada bidang. Muka yang dilubangi menjadi muka “luar” pada graf planar.
Intinya, pengetahuan kita tentang graf (khususnya graf planar) dapat diterapkan pada polihedron konveks. Karena setiap polihedron konveks dapat direpresentasikan sebagai graf planar, rumus Euler untuk graf planar juga berlaku bagi semua polihedron konveks. Kita juga dapat menerapkan jenis penalaran yang digunakan untuk graf dalam konteks lain pada polihedron konveks. Sebagai contoh, tidak ada polihedron konveks dengan 11 simpul yang semuanya berderajat 3 karena hal itu akan menghasilkan 33/2 sisi.

Contoh 2.3.3.

Adakah polihedron konveks yang terdiri atas tiga segitiga dan enam segilima? Bagaimana dengan polihedron yang terdiri atas tiga segitiga, enam segilima, dan lima segitujuh (poligon bersisi 7)?
Penyelesaian.
Berapa banyak sisi yang akan dimiliki polihedron semacam itu? Untuk polihedron pertama yang diusulkan, segitiga-segitiganya menyumbangkan total 9 sisi, sedangkan segilima-segilimanya menyumbangkan 30 sisi. Namun, perhitungan ini menghitung setiap sisi dua kali (karena setiap sisi membatasi tepat dua muka), sehingga menghasilkan 39/2 sisi, yang mustahil. Jadi, polihedron semacam itu tidak ada.
Polihedron kedua tidak menghadapi kendala ini. Tambahan 35 sisi yang disumbangkan oleh segitujuh menghasilkan total 74/2 = 37 sisi. Sejauh ini tidak ada masalah. Sekarang, berapa banyak simpul yang dimiliki polihedron yang diandaikan tersebut? Kita dapat menggunakan rumus Euler. Terdapat 14 muka, sehingga diperoleh \(v - 37 + 14 = 2\) atau secara ekuivalen \(v = 25\text{.}\) Namun, sekarang gunakan simpul-simpulnya untuk menghitung sisi sekali lagi. Setiap simpul harus berderajat sedikitnya tiga (artinya, setiap simpul mempertemukan sedikitnya tiga muka karena sudut dalam semua poligon harus kurang dari \(180^\circ\)), sehingga jumlah derajat simpul sedikitnya 75. Karena jumlah derajat harus tepat dua kali jumlah sisi, ini menyatakan bahwa terdapat lebih dari 37 sisi. Sekali lagi, polihedron semacam itu tidak ada.
Untuk mengakhiri penerapan graf planar ini, perhatikan polihedron beraturan. Kita menyatakan bahwa hanya terdapat lima polihedron semacam itu. Bagaimana kita mengetahui bahwa pernyataan ini benar? Kita dapat membuktikannya menggunakan teori graf.

Bukti.

Ingatlah bahwa semua muka polihedron beraturan merupakan poligon beraturan yang identik dan setiap simpul memiliki derajat yang sama. Perhatikan empat kasus berdasarkan jenis poligon beraturannya.
Kasus 1: Setiap muka merupakan segitiga. Misalkan \(f\) adalah jumlah muka. Dengan demikian, terdapat \(3f/2\) sisi. Dengan menggunakan rumus Euler, diperoleh \(v - 3f/2 + f = 2\text{,}\) sehingga \(v = 2 + f/2\text{.}\) Setiap simpul memiliki derajat yang sama, misalkan \(k\text{.}\) Jadi, jumlah sisi juga sama dengan \(kv/2\text{.}\) Dengan menggabungkan hasil-hasil ini, diperoleh
\begin{equation*} e = \frac{3f}{2} = \frac{k(2+f/2)}{2}\text{,} \end{equation*}
yang berarti
\begin{equation*} k = \frac{6f}{4+f}\text{.} \end{equation*}
\(k\) dan \(f\) harus berupa bilangan bulat positif. Perhatikan bahwa \(\frac{6f}{4+f}\) merupakan fungsi naik untuk \(f\) positif, yang dibatasi dari atas oleh asimtot horizontal \(k=6\text{.}\) Jadi, nilai \(k\) yang mungkin hanyalah 3, 4, dan 5. Ketiga nilai tersebut dapat dicapai. Untuk memperoleh \(k = 3\text{,}\) diperlukan \(f = 4\) (polihedron ini adalah tetrahedron). Untuk \(k = 4\text{,}\) ambil \(f = 8\) (oktahedron). Untuk \(k = 5\text{,}\) ambil \(f = 20\) (ikosahedron). Dengan demikian, terdapat tepat tiga polihedron beraturan bermuka segitiga.
Kasus 2: Setiap muka merupakan persegi. Sekarang berlaku \(e = 4f/2 = 2f\text{.}\) Dengan menggunakan rumus Euler, diperoleh \(v = 2 + f\text{,}\) dan penghitungan sisi menggunakan derajat \(k\) setiap simpul menghasilkan
\begin{equation*} e = 2f = \frac{k(2+f)}{2}\text{.} \end{equation*}
Penyelesaian untuk \(k\) memberikan
\begin{equation*} k = \frac{4f}{2+f} = \frac{8f}{4+2f}\text{.} \end{equation*}
Sekali lagi, ini merupakan fungsi naik, tetapi kali ini asimtot horizontalnya adalah \(k = 4\text{,}\) sehingga satu-satunya nilai yang mungkin bagi \(k\) adalah 3. Nilai ini menghasilkan 6 muka, sehingga diperoleh kubus. Hanya terdapat satu polihedron beraturan bermuka persegi.
Kasus 3: Setiap muka merupakan segilima. Lakukan perhitungan yang sama seperti di atas. Kali ini diperoleh \(e = 5f/2\text{,}\) sehingga \(v = 2 + 3f/2\text{.}\) Selanjutnya,
\begin{equation*} e = \frac{5f}{2} = \frac{k(2+3f/2)}{2}\text{,} \end{equation*}
sehingga
\begin{equation*} k = \frac{10f}{4+3f}\text{.} \end{equation*}
Sekarang asimtot horizontalnya adalah \(\frac{10}{3}\text{.}\) Nilai ini kurang dari 4, sehingga satu-satunya kemungkinan adalah \(k = 3\text{.}\) Nilai tersebut dapat dicapai dengan menggunakan 12 segilima, sehingga diperoleh dodekahedron. Inilah satu-satunya polihedron beraturan bermuka segilima.
Kasus 4: Setiap muka merupakan segi-\(n\) dengan \(n \ge 6\text{.}\) Dengan mengikuti prosedur yang sama seperti di atas, diperoleh
\begin{equation*} k = \frac{2nf}{4+(n-2)f}\text{,} \end{equation*}
yang merupakan fungsi naik menuju asimtot horizontal \(\frac{2n}{n-2}\text{.}\) Ketika \(n = 6\text{,}\) asimtot ini berada pada \(k = 3\text{.}\) Setiap nilai \(n\) yang lebih besar menghasilkan asimtot yang lebih kecil lagi. Oleh karena itu, tidak ada polihedron beraturan dengan muka yang memiliki lebih dari lima sisi.
 9 
Perhatikan bahwa bidang dapat diubin dengan segienam. Ini merupakan graf planar tak hingga; setiap simpul berderajat 3. Segienam yang jumlahnya tak hingga ini bersesuaian dengan limit ketika \(f \to \infty\) sehingga \(k = 3\text{.}\)

Pertanyaan Bacaan Pertanyaan Bacaan

1.

Apakah graf yang ditunjukkan di bawah ini planar? Jelaskan jawaban Anda.
Graf dengan 4 simpul dan 4 sisi; dua sisinya berpotongan

2.

Misalkan Anda menggambar graf dengan 10 simpul dan 14 sisi sedemikian sehingga tidak ada sisi yang berpotongan. Berapa banyak muka yang mungkin dimiliki graf tersebut? Jelaskan jawaban Anda.

3.

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

Latihan Soal Latihan

1.

Tentukan apakah setiap pernyataan berikut benar atau salah.
  1. \(K_{3,6}\) adalah graf planar
  2. \(K_{2,5}\) bukan graf planar
  3. \(K_6\) bukan graf planar
  4. \(K_{2,4}\) adalah graf planar
  5. \(K_{3,10}\) bukan graf planar
  6. \(K_{4,5}\) adalah graf planar
  7. \(K_{2,10}\) bukan graf planar
  8. \(K_8\) bukan graf planar

2.

Misalkan \(G\) adalah graf planar terhubung. Graf tersebut memiliki 22 sisi dan 10 muka. Berapa banyak simpul yang dimiliki \(G\text{?}\)
\(v =\) .

3.

Misalkan suatu graf terhubung memiliki 5 simpul dan setiap simpul berderajat 2.
  1. Berapa banyak sisi yang dimiliki graf tersebut?
    \(e =\) .
  2. Jika graf tersebut planar, berapa banyak muka yang dimilikinya?
    \(f =\) .

4.

Mari kita buktikan bahwa \(K_{8}\) tidak planar:
Pertama, berapa banyak simpul dan sisi yang dimiliki \(K_{8}\text{?}\)
\(v =\) dan \(e =\) .
Jika kita mengasumsikan bahwa \(K_{8}\) planar, berapa banyak muka yang akan dimilikinya?
\(f =\) .
Namun, karena setiap muka dibatasi oleh sedikitnya sisi dan setiap sisi membatasi tepat muka, kita dapat memperoleh batas atas bagi banyaknya muka. Berdasarkan penalaran ini, berapa banyak muka maksimum yang mungkin?
\(f \le\) .
Ini merupakan kontradiksi, sehingga \(K_{8}\) tidak planar. Terbukti.

5.

Misalkan graf tersebut planar tetapi tidak terhubung dan memiliki \(4\) komponen. Gambarkan cukup banyak contoh untuk menurunkan suatu bentuk rumus Euler bagi kasus ini.
\(v-e+f=\) .

Latihan Latihan Tambahan

1.

Mungkinkah suatu graf planar memiliki 6 simpul, 10 sisi, dan 5 muka? Jelaskan.

2.

Graf \(G\) memiliki 6 simpul dengan derajat \(2, 2, 3, 4, 4, 5\text{.}\) Berapa banyak sisi yang dimiliki \(G\text{?}\) Mungkinkah \(G\) planar? Jika ya, berapa banyak muka yang dimilikinya? Jika tidak, jelaskan.

3.

Mungkinkah graf terhubung dengan 7 simpul dan 10 sisi digambar tanpa sisi yang berpotongan sehingga menghasilkan 4 muka? Jelaskan.
Petunjuk.
Apa yang dinyatakan oleh rumus Euler?

4.

Mungkinkah graf dengan 10 simpul dan sejumlah sisi menjadi graf planar terhubung? Jelaskan.

5.

Adakah graf planar terhubung dengan jumlah muka ganjil yang setiap simpulnya berderajat 6? Buktikan jawaban Anda.
Petunjuk.
Anda dapat menggunakan lema jabat tangan untuk menyatakan banyaknya sisi dalam \(v\text{,}\) yaitu banyaknya simpul.

6.

Saya memikirkan sebuah polihedron yang memiliki 12 muka. Tujuh muka berbentuk segitiga dan empat muka berbentuk segiempat. Polihedron tersebut memiliki 11 simpul, termasuk simpul-simpul di sekeliling muka yang belum diketahui. Berapa banyak sisi yang dimiliki muka terakhir?

7.

Perhatikan beberapa polihedron klasik.
  1. Sebuah oktahedron adalah polihedron beraturan yang tersusun atas 8 segitiga sama sisi (bentuknya agak menyerupai dua limas yang alasnya direkatkan menjadi satu). Gambarkan representasi graf planar dari sebuah oktahedron. Berapa banyak simpul, sisi, dan muka yang dimiliki oktahedron (dan graf Anda)?
  2. Desain tradisional bola sepak merupakan (proyeksi sferis dari) ikosahedron terpenggal. Bangun ini terdiri atas 12 segilima beraturan dan 20 segienam beraturan. Tidak ada dua segilima yang bertetangga (jadi setiap sisi segilima hanya berbatasan dengan segienam). Berapa banyak simpul, sisi, dan muka yang dimiliki ikosahedron terpenggal? Jelaskan bagaimana Anda memperoleh jawaban tersebut. Bonus: gambarkan representasi graf planar dari ikosahedron terpenggal.
  3. “Teman” Anda mengaku telah membuat polihedron cembung dari 2 segitiga, 2 persegi, 6 segilima, dan 5 segidelapan. Buktikan bahwa teman Anda berbohong. Petunjuk: setiap simpul polihedron cembung harus berbatasan dengan sedikitnya tiga muka.

8.

Buktikan rumus Euler menggunakan argumen penyangkal minimal, dengan minimalitas ditentukan oleh jumlah sisi terkecil.

9.

Buktikan rumus Euler menggunakan argumen penyangkal minimal, dengan minimalitas ditentukan oleh jumlah simpul terkecil.

10.

Rumus Euler (\(v - e + f = 2\)) berlaku bagi semua graf planar terhubung. Bagaimana jika suatu graf tidak terhubung? Misalkan suatu graf planar memiliki dua komponen. Berapakah nilai \(v - e + f\) sekarang? Bagaimana jika graf tersebut memiliki \(k\) komponen?

11.

Buktikan bahwa graf Petersen (di bawah ini) tidak planar.
Gambar graf Petersen: sepuluh simpul tersusun sebagai sebuah segilima besar yang mengelilingi pentagram kecil (bintang bersudut lima). Sisi-sisi membentuk keliling segilima besar dan garis-garis pentagram yang berpotongan. Setiap simpul pada segilima besar bertetangga dengan simpul terdekat pada pentagram di bagian dalam.
Petunjuk.
Berapa panjang siklus terpendeknya? (Besaran ini biasanya disebut panjang siklus terpendek (girth) suatu graf.)

12.

Buktikan bahwa setiap graf planar dengan \(v\) simpul dan \(e\) sisi memenuhi \(e \le 3v - 6\text{.}\)

13.

Buktikan bahwa setiap graf planar harus memiliki simpul berderajat paling tinggi 5.

14.

Berikan bukti yang cermat bahwa graf di bawah ini tidak planar.
Graf dengan 11 simpul. Satu simpul berada di pusat, kemudian lima simpul tersebar merata pada suatu lingkaran di sekelilingnya, dan lima simpul lagi tersebar merata pada lingkaran yang mengelilingi lingkaran pertama. Sisi-sisi membentuk sebuah segilima pada lingkaran luar simpul. Setiap simpul luar juga bertetangga dengan dua simpul dalam, yaitu dua simpul yang berada di kedua sisi simpul terdekat dengannya. Terakhir, setiap simpul dalam juga bertetangga dengan simpul pusat.
Petunjuk.
Panjang siklus terpendek (girth) graf tersebut adalah 4.

15.

Jelaskan mengapa kita tidak dapat menggunakan jenis bukti yang sama seperti dalam Latihan 14 untuk membuktikan bahwa graf di bawah ini tidak planar. Kemudian jelaskan bagaimana Anda tetap mengetahui bahwa graf tersebut tidak planar.
Graf dengan 11 simpul. Satu simpul berada di pusat, kemudian lima simpul tersebar merata pada suatu lingkaran di sekelilingnya, dan lima simpul lagi tersebar merata pada lingkaran yang mengelilingi lingkaran pertama. Sisi-sisi membentuk segilima pada lingkaran luar simpul dan juga pada lingkaran dalam simpul. Setiap simpul luar juga bertetangga dengan dua simpul dalam, yaitu dua simpul yang berada di kedua sisi simpul terdekat dengannya. Terakhir, setiap simpul dalam juga bertetangga dengan simpul pusat.
Petunjuk.
Apa yang terjadi pada panjang siklus terpendek (girth)? Hati-hati: banyaknya sisi juga berbeda. Sebaiknya periksa rumus Euler.