Lewati ke konten utama
Gambar logo

Matematika Diskret Sebuah Pengantar Terbuka, Edisi Keempat

Oscar Levin

Subbab 2.8 Ringkasan Bab

Semoga bab ini telah memberi Anda gambaran tentang luasnya ragam topik dalam teori graf sekaligus alasan bidang ini menarik untuk dipelajari. Masih banyak bidang menarik lain yang dapat ditinjau, dan jumlahnya terus bertambah; teori graf merupakan bidang penelitian matematika yang aktif.
🔗
Salah satu alasan teori graf merupakan bidang kajian yang begitu kaya adalah karena bidang ini membahas konsep yang sangat mendasar: setiap pasangan objek dapat saling berhubungan atau tidak berhubungan. Jenis objek dan arti “berhubungan” bergantung pada konteks, dan hal ini menghasilkan banyak penerapan teori graf dalam sains dan bidang matematika lainnya. Objek tersebut dapat berupa negara, dan dua negara berhubungan apabila keduanya berbagi batas. Objek tersebut dapat berupa daratan yang berhubungan apabila terdapat jembatan di antaranya. Objek tersebut dapat berupa situs web yang berhubungan apabila terdapat tautan dari satu situs ke situs lainnya. Atau, kita dapat bersikap sepenuhnya abstrak: objeknya berupa simpul yang berhubungan apabila terdapat sisi di antaranya.
🔗
Pertanyaan yang kita ajukan tentang graf bergantung pada penerapannya, tetapi sering kali mengarah pada pertanyaan yang lebih mendalam, umum, dan abstrak yang layak dipelajari secara tersendiri. Berikut adalah ringkasan singkat jenis pertanyaan yang telah kita tinjau:
  • Dapatkah graf digambar pada bidang tanpa sisi yang berpotongan? Jika dapat, berapa banyak muka yang dibentuk gambar tersebut pada bidang?
    🔗
    🔗
  • Dapatkah simpul-simpul graf diwarnai dengan sedikit warna sedemikian sehingga simpul-simpul yang bertetangga memiliki warna berbeda? Berapa banyak warna yang diperlukan?
    🔗
    🔗
  • Dapatkah setiap sisi graf ditelusuri tepat satu kali tanpa mengangkat pensil? Jenis “lintasan” lain apa yang mungkin dimiliki suatu graf?
    🔗
    🔗
  • Dapatkah Anda menemukan subgraf dengan sifat tertentu? Sebagai contoh, kapan suatu graf (bipartit) memuat subgraf yang setiap simpulnya hanya bertetangga dengan satu simpul lain?
    🔗
    🔗
🔗
Tidak mengherankan bahwa pertanyaan-pertanyaan ini sering kali saling berkaitan. Sebagai contoh, bilangan kromatik suatu graf tidak dapat lebih besar dari 4 apabila graf tersebut planar. Ada atau tidaknya jejak Euler pada suatu graf bergantung pada banyaknya simpul yang bertetangga dengan setiap simpul (dan apakah bilangan-bilangan tersebut selalu genap atau tidak). Bahkan keberadaan pencocokan dalam graf bipartit dapat dibuktikan menggunakan lintasan.
🔗

Latihan Tinjauan Bab

1.

Graf mana saja di bawah ini yang sama, jika ada? Graf mana yang berbeda? Jelaskan.
🔗
Graf dengan lima simpul; dua simpul berada pada baris atas dan tiga simpul pada baris bawah. Simpul kiri atas bertetangga dengan simpul kanan atas, simpul kanan bawah, dan simpul tengah bawah. Simpul kanan atas juga bertetangga dengan simpul tengah bawah dan simpul kiri bawah. Simpul tengah bawah bertetangga dengan kedua simpul bawah lainnya.
Graf dengan lima simpul: tiga simpul dalam satu baris, dan di atas simpul tengah pada baris tersebut terdapat dua simpul lagi yang tersusun vertikal. Simpul-simpul terluar pada baris itu bertetangga dengan setiap simpul pada kolom tengah. Simpul paling atas dan simpul tengah pada kolom tersebut juga bertetangga.
Graf dengan lima simpul: tiga simpul tersusun pada baris atas, dan dua simpul lainnya berada tepat di bawah simpul kiri dan kanan pada baris atas. Simpul di tengah baris bertetangga dengan setiap simpul lainnya. Kedua simpul di sebelah kiri bertetangga, demikian pula kedua simpul di sebelah kanan. Terakhir, simpul kiri atas dan kanan atas bertetangga melalui sisi melengkung.
🔗

2.

Graf mana dalam soal sebelumnya yang memiliki jejak atau sirkuit Euler? Graf mana yang planar?
🔗
🔗

3.

Gambarkan graf yang memiliki sirkuit Euler tetapi tidak planar.
🔗
🔗

4.

Gambarkan graf yang tidak memiliki jejak Euler dan juga tidak planar.
🔗
🔗

5.

Perhatikan graf \(G = (V, E)\) dengan \(V = \{a,b,c,d,e,f,g\}\) dan \(E = \{ab, ac, af, bg, cd, ce\}\) (di sini kita menggunakan notasi singkat untuk sisi: sebagai contoh, \(ab\) sebenarnya berarti \(\{a,b\}\)).
  1. Apakah graf \(G\) isomorfik dengan \(G' = (V', E')\) dengan \(V' = \{t, u, v, w, x, y, z\}\) dan \(E' = \{tz, uv, uy, uz, vw, vx\}\text{?}\) Jika ya, berikan isomorfismenya. Jika tidak, jelaskan bagaimana Anda mengetahuinya.
    🔗
    🔗
  2. Temukan graf \(G''\) dengan 7 simpul dan 6 sisi yang TIDAK isomorfik dengan \(G\text{,}\) atau jelaskan mengapa hal tersebut tidak mungkin.
    🔗
    🔗
  3. Tuliskan barisan derajat untuk \(G\text{.}\) Artinya, tuliskan derajat semua simpul dalam urutan menurun.
    🔗
    🔗
  4. Temukan graf terhubung \(G'''\) yang memiliki barisan derajat sama dengan \(G\) tetapi TIDAK isomorfik dengan \(G\text{,}\) atau jelaskan mengapa hal tersebut tidak mungkin.
    🔗
    🔗
  5. Graf jenis apakah \(G\text{?}\) Apakah \(G\) lengkap? Bipartit? Pohon? Siklus? Lintasan? Roda?
    🔗
    🔗
  6. Apakah \(G\) planar?
    🔗
    🔗
  7. Berapakah bilangan kromatik \(G\text{?}\) Jelaskan.
    🔗
    🔗
  8. Apakah \(G\) memiliki jejak atau sirkuit Euler? Jelaskan.
    🔗
    🔗
🔗
🔗

6.

Jika suatu graf memiliki 10 simpul, 10 sisi, dan sebuah sirkuit Euler, apakah graf tersebut harus planar? Berapa banyak muka yang dimilikinya?
🔗
🔗

7.

Misalkan \(G\) adalah graf dengan \(n\) simpul yang masing-masing berderajat 5.
  1. Untuk nilai \(n\) manakah kondisi ini mungkin?
    🔗
    🔗
  2. Untuk nilai \(n\) manakah graf tersebut memiliki jejak Euler?
    🔗
    🔗
  3. Berapakah nilai \(n\) terkecil yang memungkinkan graf tersebut planar? (rumit)
    🔗
    🔗
🔗
🔗

8.

Pada acara dansa sekolah, 6 siswi dan 4 siswa bergiliran berdansa (secara berpasangan) satu sama lain.
  1. Berapa banyak pasangan yang berdansa jika setiap siswi berdansa dengan setiap siswa?
    🔗
    🔗
  2. Berapa banyak pasangan yang berdansa jika setiap orang berdansa dengan setiap orang lainnya (tanpa memandang gender)?
    🔗
    🔗
  3. Jelaskan graf apa yang dapat digunakan untuk merepresentasikan kedua situasi tersebut.
    🔗
    🔗
🔗
🔗

9.

Dalam suatu kelompok yang terdiri atas \(n\) orang, mungkinkah setiap orang berteman dengan sejumlah ganjil orang dalam kelompok tersebut? Jika ya, apa yang dapat Anda simpulkan tentang \(n\text{?}\)
🔗
🔗

10.

Teman Anda menantang Anda untuk membuat polihedron cembung yang terdiri atas 9 segitiga dan 6 segilima.
  1. Mungkinkah polihedron semacam itu dibuat dengan hanya menggunakan bentuk-bentuk tersebut? Jelaskan.
    🔗
    🔗
  2. Anda memutuskan untuk menambahkan satu segitujuh (poligon bersisi tujuh). Berapa banyak simpul yang dimiliki polihedron cembung baru Anda?
    🔗
    🔗
  3. Dengan mengasumsikan bahwa Anda berhasil membuat polihedron baru bermuka 16, mungkinkah setiap simpul menjadi pertemuan bagi jumlah muka yang sama? Mungkinkah setiap simpul menjadi pertemuan bagi 3 atau 4 muka? Jika ya, berapa banyak simpul dari masing-masing jenis tersebut?
    🔗
    🔗
🔗
🔗

11.

Adakah polihedron cembung yang memerlukan 5 warna untuk mewarnai simpul-simpulnya secara tepat? Jelaskan.
🔗
🔗

12.

Berapa banyak sisi yang dimiliki graf \(K_{n,n}\text{?}\) Untuk nilai \(n\) manakah graf tersebut memiliki sirkuit Euler? Untuk nilai \(n\) manakah graf tersebut planar?
🔗
🔗

13.

Graf \(G\) memiliki 6 simpul dengan derajat \(1, 2, 2, 3, 3, 5\text{.}\) Berapa banyak sisi yang dimiliki \(G\text{?}\) Jika \(G\) planar, berapa banyak muka yang dimilikinya? Apakah \(G\) memiliki jejak Euler?
🔗
🔗

14.

Berapa jumlah warna minimum yang Anda perlukan untuk mewarnai simpul-simpul \(K_{7}\) secara tepat? Berdasarkan jawaban Anda, dapatkah Anda menentukan apakah \(K_7\) planar?
🔗
🔗

15.

Berapa jumlah warna minimum yang Anda perlukan untuk mewarnai simpul-simpul \(K_{3,4}\) secara tepat? Berdasarkan jawaban Anda, dapatkah Anda menentukan apakah \(K_{3,4}\) planar?
🔗
🔗

16.

Buktikan bahwa \(K_{3,4}\) tidak planar. Gunakan rumus Euler, bukan sekadar mengacu pada fakta bahwa \(K_{3,3}\) tidak planar.
🔗
🔗

17.

Dodekahedron adalah polihedron cembung beraturan yang tersusun atas 12 segilima beraturan.
  1. Misalkan Anda mewarnai setiap segilima dengan salah satu dari tiga warna. Buktikan bahwa pasti terdapat dua segilima bertetangga yang diberi warna sama.
    🔗
    🔗
  2. Bagaimana jika Anda menggunakan empat warna?
    🔗
    🔗
  3. Bagaimana jika Anda mewarnai muka sebuah kubus alih-alih dodekahedron?
    🔗
    🔗
🔗
🔗

18.

Tentukan apakah pernyataan-pernyataan berikut benar atau salah. Buktikan jawaban Anda.
  1. Jika dua graf \(G_1\) dan \(G_2\) memiliki bilangan kromatik yang sama, kedua graf tersebut isomorfik.
    🔗
    🔗
  2. Jika dua graf \(G_1\) dan \(G_2\) memiliki jumlah simpul dan sisi yang sama serta bilangan kromatik yang sama, kedua graf tersebut isomorfik.
    🔗
    🔗
  3. Jika dua graf isomorfik, kedua graf tersebut memiliki bilangan kromatik yang sama.
    🔗
    🔗
🔗
🔗

19.

Jika graf planar \(G\) dengan \(7\) simpul membagi bidang menjadi 8 muka, berapa banyak sisi yang harus dimiliki \(G\text{?}\)
🔗
🔗

20.

Perhatikan graf di bawah ini:
🔗
Graf dengan enam simpul. Dua simpul tersusun pada kolom tengah dan saling bertetangga. Masing-masing juga bertetangga dengan keempat simpul lainnya.
  1. Apakah graf tersebut memiliki jejak atau sirkuit Euler? Jelaskan.
    🔗
    🔗
  2. Apakah graf tersebut planar? Jelaskan.
    🔗
    🔗
  3. Apakah graf tersebut bipartit? Lengkap? Bipartit lengkap?
    🔗
    🔗
  4. Berapakah bilangan kromatik graf tersebut?
    🔗
    🔗
🔗
🔗

21.

Untuk setiap bagian di bawah ini, tentukan apakah pernyataannya benar atau salah. Jelaskan mengapa pernyataan yang benar memang benar, dan berikan contoh penyangkal bagi pernyataan yang salah.
  1. Setiap graf bipartit bersifat planar.
    🔗
    🔗
  2. Setiap graf bipartit yang memiliki sedikitnya satu sisi mempunyai bilangan kromatik 2.
    🔗
    🔗
  3. Setiap graf bipartit memiliki jejak Euler.
    🔗
    🔗
  4. Setiap simpul pada graf bipartit berderajat genap.
    🔗
    🔗
  5. Suatu graf bipartit jika dan hanya jika jumlah derajat semua simpulnya genap.
    🔗
    🔗
🔗
🔗

22.

Perhatikan pernyataan, “Jika suatu graf planar, graf tersebut memiliki jejak Euler.”
  1. Tuliskan konvers pernyataan tersebut.
    🔗
    🔗
  2. Tuliskan kontraposisi pernyataan tersebut.
    🔗
    🔗
  3. Tuliskan negasi pernyataan tersebut.
    🔗
    🔗
  4. Mungkinkah kontraposisi tersebut salah? Jika ya, apa yang dapat Anda simpulkan?
    🔗
    🔗
  5. Apakah pernyataan semula benar atau salah? Buktikan jawaban Anda.
    🔗
    🔗
  6. Apakah konvers pernyataan tersebut benar atau salah? Buktikan jawaban Anda.
    🔗
    🔗
🔗
🔗

23.

Misalkan \(G\) adalah graf terhubung dengan \(v\) simpul dan \(e\) sisi. Gunakan induksi matematika untuk membuktikan bahwa jika \(G\) memuat tepat satu siklus (di antara sisi dan simpul lainnya), maka \(v = e\text{.}\)
🔗
Catatan: Anda diminta membuktikan kasus khusus rumus Euler untuk graf planar, jadi jangan gunakan rumus tersebut dalam bukti Anda.
🔗
Petunjuk.
Anda dapat membagi bukti menjadi dua bagian. Pertama, buktikan dengan induksi bahwa siklus \(C_n\) memenuhi \(v=e\text{.}\) Kemudian, tinjau apa yang terjadi jika graf tersebut tidak hanya terdiri atas siklus itu.
🔗
🔗
🔗
🔗
🔗
SblmTopLnjt
Umpan Balik