Soal dan Pembahasan – Ujian Akhir Semester (UAS) Matematika Diskrit (Graf)


Berikut ini adalah 6 soal UAS Matematika Diskrit (TA 2017/2018) yang diujikan pada tanggal 8 Januari 2018 oleh Drs. Ade Mirza, M.Pd. Materi yang diujikan seluruhnya mengenai graf.

Soal Nomor 1
Jika G graf sederhana dengan |V(G)| \geq 2, buktikan bahwa G memiliki paling sedikit 2 titik berbeda dengan derajat yang sama.

Penyelesaian

Misalnya graf sederhana itu memiliki n titik, dengan n \geq 2. Karena ada n titik berbeda, maka derajat maksimum yang mungkin adalah n - 1, tetapi perhatikan bahwa ketika ada 1 buah titik yang memiliki derajat n - 1, maka tidak ada titik yang berderajat 0 dan derajat titik lainnya haruslah n - 2, n - 3, n - 4, ...., 3, 2, 1. Padahal ada n titik berbeda dalam kasus ini, sehingga pastilah setidaknya ada 1 titik yang memiliki derajat yang sama dengan titik lainnya.
Contoh: Misal ada graf sederhana dengan 4 titik. V(G) = \{a, b, c, d\}, dengan d(a) = 3. Ini berakibat tidak ada titik yang berderajat 0. Agar berbeda, ambil d(b) = 2 dan d(c) = 1. Karena d(d) \neq 0, maka derajat titik d yang mungkin adalah 1, 2, atau 3 (derajatnya sama dengan titik lain).

[collapse]

Soal Nomor 2
Buatlah 2 buah graf yang tidak isomorfik, beraturan dengan 8 titik dan 12 sisi.

Penyelesaian


Graf H dan H pada gambar di atas tidak isomorfik, beraturan (berderajat 3) dengan 8 titik dan 12 sisi.

[collapse]

Soal Nomor 3
Tunjukkan bahwa graf pohon dengan n titik memiliki tepat n - 1 sisi.

Penyelesaian

Misalkan H adalah graf pohon, dengan |V(H)| = n. Akan dibuktikan bahwa |E(H)| = n - 1.
Dengan menggunakan induksi matematika pada titik n, maka untuk n=1, maka |E(H)| = 1 - 1 = 0 merupakan pernyataan yang benar karena pohon dengan satu titik jelas tidak memiliki sisi.
Asumsikan benar bahwa untuk n = k, |E(H)| = k - 1. Akan dibuktikan benar untuk n = k + 1 sebagai berikut.
Misalkan e adalah salah satu sisi pada pohon H. Karena H tidak memuat sikel dan terhubung (definisi pohon), maka bila sisi ini dihapus, akan diperoleh graf yang terdiri dari dua komponen, masing-masing komponen memiliki k_1 dan k_2 titik, dengan k_1+k_2=n. Masing-masing komponen pada graf itu merupakan pohon. Berdasarkan asumsi, masing-masing komponen memiliki (k_1-1) dan (k_2-1) sisi. Jika sisi e dimasukkan kembali pada H, maka diperoleh total sisinya, yaitu
\begin{aligned} |E(H)| & = (k_1 - 1)+(k_2-1)+1 \\ & = (k_1 + k_2) - 1 \\ & = n - 1 \end{aligned}
Dengan demikian benar untuk semua n. Jadi, terbukti bahwa pohon dengan n titik mempunyai tepat n - 1 sisi.

[collapse]

Soal Nomor 4
Jika Q_n adalah graf kubus,
a) berapa banyak titik Q_n
b) berapa banyak sisi Q_n
Berikan argumen/alasan!

Penyelesaian

Graf kubus Q_n memiliki 2^n titik dan 2^{n-1}.n sisi.
Penjelasan:
Q_1 (graf berupa segmen garis) memiliki 2 titik dan 1 sisi.
Q_2 (graf berupa bidang persegi panjang) memiliki 4 titik dan 4 sisi.
Q_3 (graf berupa kubus yang direpresentasikan dalam bidang) memiliki 8 titik dan 12 sisi. Selanjutnya, Anda akan memperoleh bahwa graf kubus Q_n memiliki 2^n titik dan 2^{n-1} \times n sisi.

[collapse]

Soal Nomor 5
Buatlah contoh graf yang dual diri.

Penyelesaian


(Sumber: Wolfram MathWorld)

[collapse]

Soal Nomor 6
Perhatikan graf H berikut.

a) Buatlah jalan tertutup dengan panjang 7.
b) Carilah trail yang bukan sirkuit dengan panjang 6.
c) Carilah jalan tertutup yang bukan trail.

Penyelesaian

Contoh jalan tertutup dengan panjang 7 adalah (u~a~v~e~w~f~x~b~u~a~v~e~w~d~u)
Contoh trail yang bukan sirkuit dengan panjang 6 adalah (u~b~x~g~x~f~w~c~u~d~w~e~v)
Contoh jalan tertutup yang bukan trail adalah (u~b~x~b~u)

[collapse]

Ayo Beri Rating Postingan Ini

Soal dan Pembahasan – Pohon/Tree (Graf ~ Matematika Diskrit)

Soal Nomor 1
Jelaskan perbedaan dan kesamaan antara graf pohon (tree) dan hutan (forest).

Penyelesaian

Kesamaan: merupakan graf asiklik (graf yang tidak memuat sikel).
Perbedaan: pohon merupakan graf terhubung, sedangkan hutan merupakan graf yang boleh terhubung ataupun tidak. Dengan kata lain, semua pohon adalah hutan, tetapi tidak semua hutan adalah pohon.

[collapse]

Soal Nomor 2
Gambarkan sebuah contoh graf dengan ketentuan berikut bila ada.
a. pohon
b. hutan
c. hutan yang bukan pohon
d. pohon yang bukan hutan

Penyelesaian


(Jawaban a) Graf berikut merupakan pohon (graf terhubung yang tidak memuat sikel)

(Jawaban b) Graf G dan komplemennya merupakan contoh hutan (sekaligus pohon).

(Jawaban c) Graf berikut merupakan hutan, tetapi bukan pohon, karena grafnya tak terhubung (terdiri dari 2 komponen).

(Jawaban d) Tidak ada graf yang demikian (semua pohon adalah hutan).

[collapse]

Soal Nomor 3
Buktikan bahwa setiap sisi pada graf pohon adalah jembatan.

Penyelesaian

Jika ada 2 lintasan dari titik A ke titik B pada suatu graf, maka ada sikel yang memuat kedua titik itu juga. Oleh karenanya, ketika kita menghilangkan sisi AB pada suatu pohon dan tetap ada lintasan dari A ke B, maka graf itu bukan pohon karena memuat sikel.

[collapse]

Soal Nomor 4
Buktikan bahwa graf pohon dengan paling sedikit dua titik adalah graf bipartisi.

Penyelesaian

Teorema graf bipartisi menyatakan bahwa suatu graf disebut graf bipartisi jika dan hanya jika graf itu tidak memuat sikel ganjil. Karena pohon tidak memiliki sikel (termasuk sikel ganjil), maka dengan menggunakan teorema tersebut, terbukti bahwa pohon dengan paling sedikit 2 titik merupakan graf bipartisi. 

[collapse]

Soal Nomor 5
Suatu sisi e dari graf G adalah jembatan jika dan hanya jika e bukan merupakan bagian dari sikel dalam G. Buktikan pernyataan tersebut.

Penyelesaian

Pembuktian dengan menggunakan kontradiksi.
(\Rightarrow) Misal e jembatan di G dan merupakan bagian dari sikel G. Ketika e dihapus, kita tahu bahwa akan ada lintasan di antara dua titik ujung sisi e, dan jelas ini kontradiksi dengan definisi jembatan.
(\Leftarrow) Misalkan e bukan bagian dari sikel di G. Hapus sisi e dari G, dan kita misalkan ada lintasan pada titik-titik ujung e setelah sisi e dihapus karena e bukan jembatan. Sekarang, tambahkan sisi e kembali. Karena ada lintasan di antara dua titik ujung e yang tidak melalui sisi e, maka ada sikel di G yang melewati sisi e, yang ternyata kontradiksi karena diasumsikan bahwa e bukan jembatan. Pengandaian diingkari. Berarti, e jembatan. (Terbukti)

[collapse]

Soal Nomor 6
Nyatakan pernyataan berikut apakah benar atau salah, serta berikan alasannya.
a. Sebuah titik v dari pohon T adalah titik potong jika dan hanya jika d(v) \geq 1
b. Jika G adalah sebuah graf yang tepat memiliki sebuah spanning tree, maka G adalah pohon.
c. Jika T adalah spanning tree dari graf G yang memuat sisi e, maka T.e adalah spanning tree dari G.e

Penyelesaian Belum Lengkap

(Jawaban a) Pernyataan salah. Titik v pada pohon merupakan titik potong jika dan hanya jika d(v) \geq 2. Ini terjadi karena penghilangannya mengakibatkan sisi yang bersisian dengan titik itu juga hilang, padahal sisi tersebut merupakan jembatan, sehingga membuat graf menjadi tak terhubung. Di lain pihak, titik pada pohon dengan derajat 1 (titik ujung) bukan titik potong karena penghilangan titik ini beserta satu sisinya tidak membuat graf menjadi tak terhubung.
(Jawaban b) Pernyataan benar. Pohon merentang (spanning tree) dari suatu graf adalah pohon yang memuat semua titik pada graf itu. Karena spanning tree pada graf itu tunggal (berarti semua titik dan semua sisi dilewati), maka graf itu sendiri adalah pohon.
(Jawaban c) –

[collapse]

Soal Nomor 7
Misalkan T adalah pohon dengan n titik, n \geq 4, dan v sebuah titik berderajat maksimum dalam T.
Tunjukkan bahwa T adalah lintasan (path) jika dan hanya jika d(v) = 2

Penyelesaian

Pernyataan yang akan dibuktikan berbentuk biimplikasi sehingga harus dibuktikan 2 arah.
Premis 1: Jika T lintasan, maka d(v) = 2.
Premis 2: Jika d(v) = 2, maka T lintasan.
(Pembuktian premis 1) Untuk d(v) < 2 jelas tidak mungkin karena diberikan bahwa n \geq 4. Andaikan d(v) > 2. Lintasan T (yang melewati titik v) akan bercabang (padahal lintasan seharusnya linear), sehingga kontradiksi dengan pengandaian yang ada. Jadi, haruslah d(v) = 2.
(Pembuktian premis 2) Gunakan induksi. Misalkan T_n adalah suatu pohon dengan n titik, n \geq 4, dan maksimum derajat titiknya 2. Untuk n = 4, hanya ada 2 kemungkinan untuk T_4 termasuk isomorfiknya yaitu sebagai berikut.

Pohon pada gambar kiri merupakan suatu lintasan dengan derajat maksimum titiknya 2, sedangkan pohon pada gambar kanan bukan lintasan (derajat maksimum titiknya 3). Sekarang, misalkan n \geq 5 dan asumsi ini berlaku untuk semua n bilangan asli. Untuk mengonstruksi T_{n + 1}, kita harus menambah satu titik lagi pada T_n. Karena hipotesisnya kita memiliki titik dengan derajat maksimum tidak lebih dari 2, maka hanya ada 2 pilihan untuk menambahkan titik tersebut, yaitu di awal dan akhir lintasan T_n (bila tidak, T_{n + 1} akan memiliki derajat maksimum 3). Tapi, di manapun kita meletakkan titik itu baik di awal maupun akhir lintasan, T_{n+1} adalah lintasan dan dengan menggunakan induksi, bukti ini berlaku untuk semua n.

[collapse]

Soal Nomor 8
Jika P = \{v_0, v_1, v_2, \cdots, v_n\} adalah sebuah lintasan terpanjang di pohon G, maka d(v_0) = d(v_n) = 1. Buktikan pernyataan tersebut.

Penyelesaian

Jika lintasan berakhir pada titik yang masih memiliki sisi yang terkait dengannya, maka kita bisa menambahkan sisi tersebut sebagai bagian dari lintasan itu sehingga lintasannya semakin panjang. Misalkan kita memiliki lintasan terpanjang  P = \{v_0, v_1, v_2, \cdots, v_n\}. Andaikan d(v_n) > 1, maka ada titik v_{n+1} dan sisi e = (v_n, v_{n+1}) yang bukan bagian dari lintasan P. Jika tidak, kita akan memperoleh suatu sikel pada pohon. Lintasan v_1, \cdots, v_n, v_{n+1} lebih panjang dari P. Ini kontradiksi dengan pernyataan bahwa P lintasan terpanjang. Jadi, pengandaian diingkari, sehingga haruslah d(v_n) = 1. Dengan prinsip yang sama, dapat dibuktikan d(v_1) = 1.

[collapse]

Soal Nomor 9
Gunakan Algoritma Prim untuk mendapatkan pohon rentang minimal dari graf G berikut.

Penyelesaian

—-INISIASI: ALGORITMA PRIM—–
Step 1: Pilih salah satu titik, misalnya titik a.
Step 2: Misalkan T = \{a\} dan F = \{b, c, d, e, f, g, h, i\}. Dengan meninjau keterhubungan langsung titik pada himpunan F dengan titik pada himpunan T, diperoleh
a(-, -); b(a, 4)~\boxed{c(a, 3)}
d(a, 5)~e(-, -)~f(-, -)~g(-, -)~h(-, -)~i(-. -)
Pilih titik c(a, 3) (bobot c ke a adalah 3).
Tulis T = \{a, c\}
Step 3: Tidak semua titik berada pada himpunan T, berarti kembali ke step 2.
—-ITERASI—-
Step 2: Misalkan T = \{a, c\} dan F = \{b, d, e, f, g, h, i\}. Gunakan prinsip yang sama.
Untuk selanjutnya, titik yang tidak terhubung langsung dengan titik-titik di T tidak ditulis.
c(a, 3); \boxed{b(a, 4)}~b(c,6)~d(a,5)~\boxed{d(c,4)}
Ada 2 pilihan. Pilih salah satu, misalkan dipilih b(a, 4) (bobot b ke a adalah 4).
Tulis T = \{a, c, b\}
Step 3: Tidak semua titik berada pada himpunan T, berarti kembali ke step 2.
—-ITERASI—-
Step 2: Misalkan T = \{a, c, b\} dan F = \{d, e, f, g, h, i\}
b(a, 4); d(a,5)~\boxed{d(c,4)}
Pilih d(c, 4) (bobot d ke c adalah 4).
Tulis T = \{a, c, b, d\}
Step 3: Tidak semua titik berada pada himpunan T, berarti kembali ke step 2.
—-ITERASI—-
Step 2: Misalkan T = \{a, c, b, d\} dan F = \{e, f, g, h, i\}
d(c, 4); ~\boxed{e(d, 2)}
Pilih e(d, 2) (bobot e ke d adalah 2).
Tulis T = \{a, c, b, d, e\}
Step 3: Tidak semua titik berada pada himpunan T, berarti kembali ke step 2.
—-ITERASI—-
Step 2: Misalkan T = \{a, c, b, d, e\} dan F = \{f, g, h, i\}
e(d, 2); h(e,2)~\boxed{g(e, 1)}~f(e, 4)
Pilih g(e, 1) (bobot g ke e adalah 1).
Tulis T = \{a, c, b, d, e, g\}
Step 3: Tidak semua titik berada pada himpunan T, berarti kembali ke step 2.
—-ITERASI—
Step 2: Misalkan T = \{a, c, b, d, e, g\} dan F = \{f, h, i\}
g(e, 1); \boxed{h(e, 2)}~f(e, 4)~h(g, 4)~\boxed{i(g, 2)}
Ambil salah satu. Misal dipilih h(e, 2) (bobot h ke e adalah 2).
Tulis T = \{a, c, b, d, e, g, h\}
Step 3: Tidak semua titik berada pada himpunan T, berarti kembali ke step 2.
—-ITERASI—-
Step 2: Misalkan T = \{a, c, b, d, e, g, h\} dan F = \{f,  i\}
h(e, 2); i(h,3)~\boxed{i(g, 2)}~f(e, 4)
Pilih i(g, 2) (bobot i ke g adalah 2).
Tulis T = \{a, c, b, d, e, g, h, i\}
Step 3: Tidak semua titik berada pada himpunan T, berarti kembali ke step 2.
—-ITERASI—-
Step 2: Misalkan T = \{a, c, b, d, e, g, h, i\} dan F = \{f\}
i(g, 2); \boxed{f(i,3)}~f(e, 4)
Pilih f(i, 3) (bobot f ke i adalah 3).
Tulis T = \{a, c, b, d, e, g, h, i, f\}
Step 3: Semua titik berada pada himpunan T. Beri pesan: T = \{a, c, b, d, e, g, h, i, f\} adalah pohon rentang minimal dengan bobot 3 + 4 + 4 + 2 + 1 + 2 + 2 + 3 + 3 = 24
—ALGORITMA SELESAI—–

[collapse]

Ayo Beri Rating Postingan Ini

Istilah Lengkap Mengenai Materi Graf (Matematika Diksrit)

Berikut ini adalah istilah-istilah yang ditemukan dalam materi graf beserta arti/definisinya yang diharapkan dapat meringankan kesulitan kita dalam mempelajarinya. Untuk menguji ingatan Anda, klik pranala berikut dan selamat belajar!
Tes Istilah Graf

  1. Diagram Sirkulasi
    Diagram yang dibuat arsitek untuk menganalisis arus pengunjung/mengatur tata letak ruangan dalam gedung besar.
  2. Definisi Graf
    Pasangan tak berurutan yang terdiri dari himpunan tak kosong berupa himpunan titik/simpul (vertex) dan himpunan boleh kosong berupa himpunan sisi (edge)
  3. Terhubung Langsung/Bertetangga (Adjacent)
    Dua buah titik pada graf tak berarah dikatakan __________ jika kedua titik itu dihubungkan oleh sebuah sisi.
  4. Terkait/Bersisian (Incident)
    Untuk sembarang sisi yang menghubungkan dua titik pada graf,  sisi itu dikatakan _________ dengan dua titik itu.
  5. Sisi Rangkap/Sisi Ganda (Multiple Edges)
    Dua sisi atau lebih yang menghubungkan sepasang titik.
  6. Gelang/Kalang (Loop)
    Sisi yang titik ujungnya sama.
  7. Simpul Terpencil (Isolated Vertex)
    Simpul yang tidak memiliki sisi yang bersisian dengannya.
  8. Derajat Simpul (Vertex Degree)
    Jumlah sisi yang bersisian/keluar dari simpul.
  9. Graf Trivial (Trivial Graph)
    Graf yang hanya memiliki satu titik/simpul (tanpa sisi)
  10. Graf Kosong (Null/Empty Graph)
    Graf yang tidak memiliki sisi.
  11. Graf Sederhana (Simple Graph)
    Graf yang tidak memuat sisi rangkap maupun gelang (loop).
  12. Graf Tak Sederhana (Unsimple Graph)
    Graf yang memuat sisi rangkap atau gelang (loop).
  13. Graf Ganda/Rangkap (Multiple Graph)
    Graf yang mengandung sisi rangkap (tidak boleh memuat gelang).
  14. Graf Semu/Graf Palsu/Pseudograf (Pseudograph)
    Graf yang mengandung gelang (jika ada sisi rangkap, juga disebut demikian).
  15. Kardinalitas Graf
    Jumlah simpul/titik pada graf.
  16. Anting-anting (Pendant Vertex)
    Simpul graf yang berderajat 1.
  17. Graf Tak Berarah (Undirected Graph)
    Graf yg sisinya tidak mengandung orientasi arah (berupa garis saja). Dalam hal ini, (u, v) = (v, u) di mana u dan v adalah titik pada graf itu.
  18. Graf Berarah (Directed Graph)
    Graf yang sisinya mengandung orientasi arah. Sisinya disebut busur (arc).
  19. Simpul Asal (Initial Vertex) dan Simpul Terminal (Terminal Vertex)
    Istilah khusus untuk simpul awal dan simpul akhir pada graf berarah.
  20. Derajat Masuk (In-Degree) dan Derajat Keluar (Out-Degree)
    Jumlah busur yang masuk ~ keluar suatu simpul pada graf berarah.
  21. Graf Komplit/Graf Lengkap (Complete Graph)
    Graf sederhana dengan setiap pasang titik yang berbeda dihubungkan oleh satu sisi.
  22. Graf Bipartisi (Bipartite Graph)
    Graf yang himpunan titiknya dapat dipartisi  menjadi 2 bagian, misalnya V_1 dan V_2 sedemikian sehingga setiap sisi di dalam G menghubungkan sebuah simpul di V_1 ke simpul di V_2
  23. Graf Bipartisi Komplit (Complete Bipartite Graph)
    Graf bipartisi dengan himpunan partisi V_1 dan V_2 yang masing-masing titik di V_1 dihubungkan dengan masing-masing titik di V_2 oleh TEPAT SATU SISI.
  24. Graf Lingkaran (Circle Graph)
    Graf sederhana yang semua simpulnya berderajat dua.
  25. Graf Beraturan-r (Regular-r Graph)
    Graf yang semua titiknya berderajat r
  26. Lema Jabat Tangan (Handshaking Lemma)
    Jumlah semua derajat simpul pada suatu graf sama dengan 2 kali jumlah sisinya.
  27. Subgraf/Upagraf/Graf Bagian (Subgraph)
    Graf yang himpunan titik dan sisinya merupakan himpunan bagian dari graf yang lain.
  28. Subgraf Merentang (Spanning Subgraph)
    Subgraf yang mengandung semua titik dari graf induknya.
  29. Vertex Induced Subgraph dari V_1
    Subgraf G yang himpunan titiknya V_1 dan himpunan sisinya beranggotakan semua sisi G yang mempunyai titik ujung di V_1.
  30. Edge Induced Subgraph dari F
    Subgraf G yang himpunan titiknya adalah titik-titik ujung sisi pada F. (F adalah himpunan sisi subset dari graf G)
  31. Titik Disjoin
    Dua subgraf dari graf G yang tidak memiliki titik yang sama.
  32. Sisi Disjoin
    Dua subgraf dari graf G yang tidak memiliki sisi yang sama.
  33. Jalan (Walk)
    Barisan simpul dan sisi v_0~e_1~v_1~e_2~\cdots~e_n~v_n yang saling terhubung pada suatu graf.
  34. Jalan Trivial (Trivial Walk)
    Jalan yang tidak memuat sisi.
  35. Jalan Tertutup (Closed Walk)
    Jalan dengan syarat u = v (titik ujungnya sama) dengan u dan v titik pada suatu graf. 
  36. Titik Dalam (Internal Vertex)
    Titik selain titik ujung pada suatu jalan.
  37. Jalur/Jejak (Trail)
    Jalan dengan semua sisinya berbeda.
  38. Lintasan (Path)
    Jalan yang semua titiknya berbeda.
  39. Sirkuit (Circuit) atau Trail Tertutup
    Jalan tertutup dengan semua sisinya berbeda
  40. Sikel (Cycle)
    Sirkuit yang titik dalamnya berbeda.
  41. Lilitan (girth)
    Panjang sikel terpendek pada graf.
  42. Lintasan Euler (Euler Path)
    Lintasan yang memuat semua sisi di graf
  43. Sirkuit Euler (Euler Circuit)
    Sirkuit yang memuat semua sisi di graf.
  44. Sikel Hamilton (Hamiltonian Cycle)
    Sikel yang memuat semua titik dari suatu graf.
  45. Graf Hamilton (Hamiltonian Graph)
    Graf yang memuat sikel Hamilton.
  46. Graf Lintasan
    Graf yang hanya memuat satu lintasan.
  47. Titik Potong (Cut Vertex)
    Titik graf terhubung yang bila dihilangkan menyebabkan graf menjadi tidak terhubung.
  48. Jembatan/Sisi Potong(Cut Set/Bridge)
    Sisi graf terhubung yang bila dihilangkan menyebabkan graf menjadi tidak terhubung.
  49. Graf Terhubung (Connected Graph)
    Graf dengan setiap pasang simpulnya mengandung lintasan.
  50. Graf Berbobot (Weighted Graph)
    Graf yang setiap sisinya diberi bobot/nilai.
  51. Matriks Ketertanggaan (Adjacency Matrix)
    Matriks yang merepresentasikan banyaknya sisi yang menghubungkan setiap dua simpul dari suatu graf.
  52. Matriks Keterkaitan/Bersisian (Incidency Matrix)
    Matriks yang merepresentasikan sisi yang bersisian dengan setiap pasang simpul dari suatu graf.
  53. Daftar/Senarai Ketetanggaan (Adjacency List)
    Daftar yang menunjukkan hasil enumerasi simpul yang bertetangga dengan simpul lainnya pada suatu graf.
  54. Pohon (Tree)
    Graf terhubung yang tidak memuat sikel.
  55. Graf Planar (Planar Graph)
    Graf yang dapat digambar pada bidang datar dengan sisi-sisi yang tidak saling berpotongan.
  56. Graf Bidang (Plane Graph)
    Representasi graf planar yang digambarkan dengan sisi-sisinya tidak saling berpotongan.

Jika ada kosa kata atau istilah lain mengenai graf yang tidak tercantum di atas, silakan tambahkan di kolom komentar di bawah. 

Ayo Beri Rating Postingan Ini

Soal dan Pembahasan – Keterhubungan Graf

 
             Setelah kita mempelajari mengenai soal dan pembahasan Teori Dasar Graf dan Graf Isomorfik dan Subgraf, sekarang kita siap untuk mempelajari soal-soal berikut mengenai graf.
            Berikut ini merupakan contoh soal beserta penyelesaiannya mengenai definisi dan terminologi graf lanjutan, yang meliputi jalan (walk), lintasan (path), sikel (cycle). sirkuit (circuit), jalur (trail), jembatan (bridge/cut set), termasuk juga mengenai graf Euler, graf Hamilton, konektivitas graf, matriks keterhubungan langsung (adjacency matrix), matriks keterkaitan (incidency matrix), Algoritma Fleury, beserta teorema-teorema yang terkait dengannya.  Jangan lupa juga untuk belajar istilah/kosa kata mengenai graf di sini.

Soal Nomor 1
Perhatikan graf G berikut.

Carilah:
a) Sebuah jalan tertutup dengan panjang 9
b) Sebuah trail terbuka dengan panjang 9
c) Sebuah trail tertutup dengan panjang 7
d) Sebuah lintasan (path) dari simpul a ke n
e) Panjang sikel terpanjang dalam G
f) Panjang lintasan (path) terpanjang dalam G
g) Lilitan (girth) dalam G
h) Sebuah graf bagian bukan rentang

Penyelesaian

(Jawaban a) Contoh jalan tertutup dengan panjang 9 adalah jalan dengan barisan titik i~c~d~e~m~l~d~k~c~i
(Jawaban b) Contoh trail terbuka dengan panjang 9 adalah jalan dengan barisan titik a~g~b~h~j~i~c~k~d~e
(Jawaban c) Contoh trail tertutup dengan panjang 7 adalah jalan dengan barisan titik c~d~e~m~l~d~k~c
(Jawaban d) Contoh lintasan (path) dari a ke n adalah jalan dengan barisan titik a~g~b~i~c~d~e~n
(Jawaban e) Panjang sikel terpanjang dalam G adalah 4. Salah satu sikel yang panjangnya demikian adalah jalan dengan barisan titik g~b~i~j~g.
(Jawaban f) Panjang lintasan (path) terpanjang dalam G adalah 12.Salah satu lintasan yang panjangnya demikian adalah jalan dengan barisan titik a~g~b~h~j~i~c~k~d~l~m~e~n
(Jawaban g) Lilitan (girth) adalah panjang sikel terpendek dalam suatu graf. Lilitan pada graf G di atas adalah 3 (contoh: jalan i~c~k)
(Jawaban h) Graf bagian bukan rentang adalah graf bagian yang tidak memuat seluruh titik pada graf induknya. Contohnya sebagai berikut di mana titik selain e, f, m, n dihapus.


[collapse]

Soal Nomor 2
Gambarkan sebuah graf yang terdiri dari
a) 5 titik, tanpa sikel, dan terhubung
b) 6 titik, reguler-2, dan terdiri dari 2 komponen

Penyelesaian

(Jawaban a) Lihat video berikut.

(Jawaban b) Graf berikut memuat 6 titik (s, t, u, x, y, z), reguler-2 (setiap titik berderajat 2), dan terdiri dari 2 komponen.

[collapse]

Soal Nomor 3
Buktikan teorema berikut.
“Setiap jalan (u, v) dalam suatu graf memuat sebuah path (u, v)

Penyelesaian

Misalkan W sebuah jalan dalam graf G, dengan W = (u, v). Jika W tertutup, maka jelas W memuat path (trivial = hanya terdiri dari satu titik), karena u = v, sehingga path (P) = u. Jika u \neq v, maka kita misalkan jalan W di G adalah sebagai berikut.
u = v_0, v_1, v_2, v_3, \cdots, v_{n-1}, v_n = v
Apabila tidak ada titik di G pada jalan W yang dilalui lebih dari satu kali (tidak ada titik yang sama pada jalan itu), maka W sendiri adalah path (u, v).
Sebaliknya, bila tidak demikian, dengan kata lain terdapat titik di G pada jalan W yang dilalui lebih dari satu kali, maka ada i, j anggota bilangan bulat positif berbeda dengan i < j sedemikian sehingga berlaku u_i = u_j.
Jika jalan u_i, u_{i+1}, \cdots, u_{j-1} dihapus dari W, maka diperoleh suatu jalan baru, sebut saja W_1 dari titik u ke v (ini hanya pemisalan) yang mempunyai beberapa titik (minimal 1) pada W. Jika tidak ada pengulangan titik pada jalan W_1, maka W_1 adalah path (u, v).
Jika tidak demikian, ulangi prosedur penghapusan seperti di atas sampai diperoleh hasil akhir berupa jalan (u, v) yang juga adalah path (u, v) (terbukti)

[collapse]

Soal Nomor 4
Dengan menggunakan teorema pada soal nomor 3 di atas, tentukan sebuah path dari v_1 ke v_5 jika jalan W dari graf G berikut.
v_1, e_1, v_2, e_5, v_3, e_{10}, v_3, e_5, v_2, e_3, v_5

Penyelesaian Belum Tersedia
[collapse]

Soal Nomor 5
Misalkan G suatu graf yang dipresentasikan seperti gambar berikut.

Nyatakanlah matriks keterhubungan langsung dan matriks keterkaitan dari graf di atas.

Penyelesaian

Misalkan A(G) menyatakan matriks keterhubungan langsung (adjacency matrix) dari graf G, maka A(G) dapat dinyatakan sebagai berikut.
A(G) = \begin{bmatrix} a_{11} & a_{12} & a_{13} & a_{14} \\ a_{21} & a_{22} & a_{23} & a_{24} \\ a_{31} & a_{32} & a_{33} & a_{34} \\ a_{41} & a_{42} & a_{43} & a_{44} \end{bmatrix} = \begin{bmatrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 2 \\ 0 & 1 & 0 & 1 \\ 1 & 2 & 1 & 0 \end{bmatrix}
(a_{ij} menyatakan banyaknya sisi yang menghubungkan titik i dan titik j, misalnya a_{24} berarti banyak sisi yang menghubungkan titik 2 dan 4, yaitu ada 2 sisi)
Selanjutnya, misalkan I(G) menyatakan matriks keterkaitan (incidency matrix) dari graf G, maka I(G) dapat dinyatakan sebagai berikut.
A(G) dapat dinyatakan sebagai berikut.
I(G) = \begin{bmatrix} a_{11} & a_{12} & a_{13} & a_{14} & a_{15} & a_{16} \\ a_{21} & a_{22} & a_{23} & a_{24} & a_{25} & a_{26} \\ a_{31} & a_{32} & a_{33} & a_{34} & a_{35} & a_{36} \\ a_{41} & a_{42} & a_{43} & a_{44} & a_{45} & a_{46} \end{bmatrix}
I(G) = \begin{bmatrix} 1 & 0 & 0 & 1 & 0 & 0\\ 1 & 1 & 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 1 & 1 \end{bmatrix}

(a_{ij} menyatakan keterkaitan titik i pada sisi j. Misalkan a_{43} bernilai 1 menyatakan karena sisi 3 terkait dengan titik 4).

[collapse]

Soal Nomor 6
Gambarkan graf dengan matriks keterhubungan langsung sebagai berikut.
a. \begin{bmatrix} 0 & 1 & 0 & 2 & 1 \\ 1 & 0 & 0 & 1 & 1 \\ 0 &0&0&0&2\\2&1&0&0&1\\1&1&2&1&0 \end{bmatrix}

b. \begin{bmatrix} 0 & 1 & 0 & 1 &1 \\ 1 & 0 &0&1&1 \\ 0 &0&0&0&0\\ 1&1&0&0&1\\ 1&1&0&1&0 \end{bmatrix}

Penyelesaian

(Jawaban a) Bentuk graf yang sesuai dengan matriks keterhubungan langsung itu adalah sebagai berikut.

Penjelasan:
Entri baris 1 kolom 1 = 0, berarti tidak ada sisi loop pada titik 1.
Entri baris 1 kolom 2 = 1, artinya ada 1 sisi yang menghubungkan titik 1 dan 2. 
Entri baris 1 kolom 3 = 0, artinya tidak ada sisi yang menghubungkan titik 1 dan 3.
Entri baris 1 kolom 4 = 2, artinya ada 2 sisi yang menghubungkan titik 1 dan 4, dan seterusnya.
(Jawaban b) Bentuk graf yang sesuai dengan matriks keterhubungan langsung itu adalah sebagai berikut.


Tips! Entri pada baris pertama menyatakan keterhubungan titik 1 pada titik lain sesuai dengan kolom matriksnya. Begitu juga entri pada baris kedua, yang menyatakan keterhubungan titik 2 pada titik lain sesuai dengan kolom matriksnya, dan seterusnya. Karena matriksnya simetris (transposnya sama), maka jika Anda tinjau dari entri kolomnya juga bisa menggunakan prinsip yang sama.

[collapse]

Soal Nomor 7
Gambarkan graf dengan matriks keterkaitan berikut.
\begin{bmatrix} 1&1&1&1&0&0&0&0 \\ 1&1&0&0&1&1&0&0 \\ 0&0&0&0&0&0&0&0\\ 0&0&0&1&0&1&1&1\\ 0&0&1&0&1&0&1&1 \end{bmatrix}

Penyelesaian

Pada matriks keterkaitan, banyak kolom menyatakan banyaknya sisi pada graf (ada 8 kolom berarti ada 8 sisi), sedangkan banyak baris menyatakan banyak titiknya (ada 5 baris berarti ada 5 titik). Untuk menggambar graf yang dimaksud, tinjau kolom per kolom.
Misalnya pada kolom pertama, baris 1 dan baris 2 bernilai 1, artinya titik 1 dan titik 2 terhubung oleh satu sisi. Pada kolom kedua, baris 1 dan 2 juga bernilai 1, artinya titik 1 dan titik 2 terhubung oleh satu sisi lagi (berarti sisi rangkap), dan seterusnya. Perhatikan bahwa pada entri pada baris ke-3 semuanya bernilai 0, yang berarti tidak ada sisi yang terkait dengan titik 3 (titik 3 di sini disebut sebagai titik terpencil (isolated vertex))

[collapse]

Soal Nomor 8
Berilah contoh setiap graf berikut dengan paling banyak 6 titik.
a) Graf Hamilton yang bukan Euler.
b) Graf Euler yang bukan Hamilton.

Penyelesaian

Graf Hamilton adalah graf yang memuat sikel Hamilton. Sikel Hamilton sendiri adalah jalan tertutup yang semua sisi dan titik internalnya berbeda serta melalui seluruh titik pada graf tersebut. Sedangkan graf Euler adalah graf yang memuat sirkuit Euler, yaitu jalan tertutup yang semua sisinya berbeda dan setiap sisi dilalui tepat 1 kali. Contoh yang diberikan berikut merupakan salah satunya. Silakan Anda coba buat graf yang lain.

Graf G_1 di atas mengandung sikel Hamilton dengan barisan titik
a~b~c~d~e~f~h~g~a
Jelas bahwa jalan tersebut tertutup (kembali pada titik semula), melalui semua titik pada graf, dan titik internalnya berbeda (hanya dilalui 1 kali). Oleh karena itu, graf G_1 disebut graf Hamilton. Tetapi, bukan graf Euler karena ada sisi yang tidak dilaluinya, yaitu sisi be, cf, dan fg.

(Jawaban b) Graf di atas tergolong graf Euler (karena mengandung sirkuit Euler a~b~c~d~e, tetapi bukan graf Hamilton sebab titik f tidak dilaluinya (tidak mengandung sikel Hamilton).

[collapse]

Soal Nomor 9
Tunjukkan bahwa setiap sikel pada graf bipartisi mempunyai panjang genap.

Penyelesaian

Perhatian! Sikel adalah jalan tertutup yang memuat sisi yang berbeda.
Misalkan diberikan graf bipartisi G. Andaikan graf ini memiliki setidaknya 1 sikel ganjil sehingga partisi himpunan titiknya dapat ditulis sebagai V_1 = \{v_1, v_3, v_5, \cdots\} dan V_2 = \{v_2, v_4, v_6, \cdots\}. Karena sikelnya memiliki panjang ganjil, maka jalan yang dapat terjadi adalah v_1~v_2~v_3~\cdots~v_{2n+1} untuk suatu n bilangan bulat positif. Jelas bahwa v_1 dan v_{2n+1} (ganjil) berada dalam himpunan partisi yang sama, yaitu V_1. Akibatnya graf tersebut bukan graf bipartisi (karena “terpaksa” harus dibuat sisi yang menghubungkan kedua titik itu agar menjadi jalan yang tertutup). Jadi, pengandaian diingkari. Terbukti bahwa graf bipartisi memiliki sikel dengan panjang genap.

[collapse]

Soal Nomor 10
Berapa banyak path (s, x) pada graf berikut?

Penyelesaian

Lintasan (path) adalah jalan yang memuat titik yang berbeda. Hanya ada 4 path yang dapat ditemukan dalam jalan (s, x), yaitu
s~v~w~x
s~t~u~v~w~x
s~v~w~z~y~x
s~t~u~v~w~z~y~x

[collapse]

Soal Nomor 11
Berilah 3 contoh graf yang komplemen diri (self complementary).

Penyelesaian


Graf yang komplemen diri adalah graf yang komplemennya sama dengan isomorfiknya. G^c sendiri merupakan notasi untuk menyatakan komplemen dari graf G. Berikut ini adalah 3 contoh graf yang komplemen diri. Contoh terakhir diambil dari Math Stack Exchange.




[collapse]

Soal Nomor 12
Buktikan bahwa graf yang komplemen diri mempunyai banyak titik sama dengan 4k atau 4k + 1 untuk suatu bilangan bulat positif k

Penyelesaian

Ingat bahwa graf lengkap/komplit dengan n titik memiliki \dfrac{1}{2}n(n-1) sisi. Untuk graf yang komplemen diri, banyak sisinya adalah setengah dari banyaknya sisi pada graf lengkap, yaitu \dfrac{1}{4}n(n-1). Agar diperoleh n bulat, maka dapat dituliskan 4|n(n-1), yang mengimplikasikan bahwa n = 4k atau n = 4k + 1 untuk suatu bilangan bulat positif k.

[collapse]

Soal Nomor 13
Tuliskan matriks keterhubungan langsung dan matriks keterkaitan dari graf berikut.

Penyelesaian

Matriks keterhubungan dari graf G di atas adalah sebagai berikut.
\begin{pmatrix} 0 & 1 & 1 & 0 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 & 1 & 0 & 0 \\  0 & 0 & 1 & 0 & 0& 1 & 0 & 0 \\  0 & 0 & 0 & 1 & 1 & 0 &0 & 0 \\  1 & 0 & 0 & 0 &0 & 0&0&1 \\\ 0 & 1 &0&0&0&0&1&0 \end{pmatrix}
Matriks keterkaitan dari graf G di atas adalah

Ordo matriks di atas adalah 8 \times 12 yang menunjukkan bahwa graf itu memuat 8 titik dan 12 sisi.
Matriks keterhubungan langsung dari graf H di atas adalah sebagai berikut.
\begin{pmatrix} 2 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 2 \\ 1 & 1 & 2 & 0 \end{pmatrix}
Sedangkan matriks keterkaitannya adalah sebagai berikut.
\begin{pmatrix} 1 & 1 & 1 & 2 & 2 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 1 \end{pmatrix}
Ordo matriks di atas adalah 4 \times 9. Banyak barisnya 4 menunjukkan bahwa jumlah titik di graf itu adalah 4, sedangkan 9 kolomnya menyatakan bahwa graf itu memuat 9 sisi. Perhatikan bahwa angka 2 pada entri di baris pertama (titik 1) matriks itu menunjukkan bahwa sisi loop mengait pada titik 1.

[collapse]

Soal Nomor 14
Tunjukkan bahwa salah satu di antara graf atau komplemennya pasti terhubung.

Penyelesaian

Misalkan G graf tak terhubung. Akan ditunjukkan G^c terhubung. Misalkan v dan w titik pada graf G. Jika vw bukan sisi di G, maka vw pasti sisi di G^c, dan berarti kita punya lintasan dari v ke w di G^c. Di lain sisi, bila vw adalah sisi di G, maka ini berarti titik v dan w berada dalam satu komponen di G. Karena G tak terhubung, maka kita bisa menemukan titik lain, sebut saja u, yang terletak di komponen lainnya sedemikian sehingga uv maupun uw bukan sisi di G. Dengan kata lain, uv dan uw adalah sisi di G^c dan vuw membentuk lintasan (path). Ini menunjukkan bahwa sembarang dua titik di G^c memiliki lintasan yang menghubungkan mereka. Dapat disimpulkan bahwa G^c pasti terhubung.

[collapse]

Soal Nomor 15
Misallan G graf bipartisi. Tunjukkan bahwa matriks keterhubungan langsung dari G dapat ditulis dalam bentuk

di mana O, P, dan Q adalah submatriks; O submatriks yang setiap unsurnya 0 (nol), sedangkan P adalah transpose dari Q.

Penyelesaian Belum Tersedia

[collapse]

Soal Nomor 16
Misalkan G graf sederhana dengan n titik dan untuk setiap titik v di G, berlaku
d(v) \ge \dfrac{1}{2}(n-1)
Buktikan bahwa G terhubung.

Penyelesaian

Misalkan G adalah graf sederhana dengan n titik. Andaikan bahwa G tak terhubung, misalnya terdiri dari setidaknya 2 komponen. Masing-masing komponen graf setidaknya memiliki 1 titik dan berdasarkan hipotesis (minimal\dfrac{1}{2}(n-1) titik), banyak titik pada masing-masing komponen adalah
1 + \dfrac{1}{2}(n-1) = \dfrac{1}{2}(n+1)
Jadi, jumlah titik pada graf G adalah
\dfrac{1}{2}(n+1) +  \dfrac{1}{2}(n+1) = n + 1
Ini kontradiksi dengan asumsi awal bahwa graf G memiliki n titik. Jadi, pengandaian diingkari. Terbukti bahwa graf G haruslah terhubung.

[collapse]

Soal Nomor 17
Tentukan \chi(G_1) (baca: chi G_1) dan \lambda(G_1) (baca: lambda G_1) dari graf G_1.

Penyelesaian

\chi(G_1) menyatakan banyak minimum titik-titik di G_1 yang jika dihilangkan akan menghasilkan graf tak terhubung atau graf trivial. Hilangkan satu titik, misalnya titik a, sehingga grafnya hanya memuat titik b dan c serta sisi bc (masih graf terhubung). Hilangkan satu titik lagi, misalnya titik b, sehingga hanya tersisa titik c. Graf tersebut menjadi graf trivial. Sesuai definisi, maka \chi(G_1) = 2 (karena titik yang dihilangkan sebanyak 2).
\lambda(G_1) menyatakan banyak minimum sisi-sisi di G_1 yang jika dihilangkan akan menghasilkan graf tak terhubung atau graf trivial. Hilangkan salah satu sisi, misalnya sisi ab, berarti G_1 masih memuat titik a, b, dan c serta sisi ac dan bc (graf terhubung). Hilangkan salah satu sisi lagi, misalnya sisi ac, sehingga graf tersebut hanya memuat titik a, b, dan c serta sisi bc. Jelas bahwa graf menjadi tak terhubung lagi. Berarti, penghilangan sisinya paling sedikit adalah 2 atau ditulis \lambda(G_1) = 2.

[collapse]

Soal Nomor 18
Tentukan \chi(G_1) (baca: chi G_1) dan \lambda(G_1) (baca: lambda G_1) dari graf-graf berikut.
 

Penyelesaian

Sebut graf pada bagian atas dan bawah berturut-turut adalah G_1 dan G_2. Sama seperti soal sebelumnya,
\lambda(G_1) = 1
\lambda(G_2) = 2 (hilangkan 2 sisi yang mengait titik di bagian ujung)
\chi(G_1) = 1
\chi(G_2) = 2 (hilangkan 2 titik dengan sisi yang mengait titik ujung)

[collapse]

Soal Nomor 19 (Soal ON-MIPA PT Seleksi Wilayah)
Suatu sisi e di graf G dikatakan suatu cut edge jika jumlah komponen dari G\e lebih dari jumlah komponen dari G. Buktikan bahwa, suatu sisi e adalah cut edge di G jika dan hanya jika e tidak termuat di setiap lingkaran di G.

Penyelesaian Belum Tersedia
[collapse]
Ayo Beri Rating Postingan Ini

Soal Latihan dan Pembahasan – Graf Isomorfik dan Subgraf (Upagraf)


Berikut ini adalah soal-soal beserta penyelesaiannya mengenai graf isomorfik dan subgraf. Tentunya, Anda diharapkan sudah menguasai materi graf dasar terlebih dahulu. Selain itu, Anda juga diharapkan mengenal istilah dalam graf. Bagi Anda yang ingin mempelajari kosa kata atau istilah graf, silakan klik sini

Soal Nomor 1
Jika G adalah graf yang diberikan seperti gambar di bawah ini, tentukan
a) Graf G – U, bila U = \{x_1, x_3, x_5, x_7\}
b) Graf G – F, bila F = \{e_2, e_4, e_6, e_8, e_{10}, e_{12}\}
c) G[U], dengan U = \{x_2, x_3, x_4, x_7\}
d) G[F], dengan F = \{e_1, e_2, e_8, e_{11}\}

Penyelesaian

(Jawaban a) Hapus titik U = \{x_1, x_3, x_5, x_7\} pada graf G beserta sisi yang bersisian dengannya sehingga diperoleh graf berikut.

(Jawaban b) Hapus sisi F = \{e_2, e_4, e_6, e_8, e_{10}, e_{12}\} pada graf G sehingga diperoleh graf berikut.

 

(Jawaban c) Hapus semua titik pada graf G terkecuali U = \{x_2, x_3, x_4, x_7\}. Tambahkan dengan sisi pada graf G yang titik ujungnya adalah anggota himpunan titik U, sehingga diperoleh graf berikut.

(Jawaban d) Hapus semua sisi pada graf G terkecuali F = \{e_1, e_2, e_8, e_{11}\}. Tambahkan titik ujung sisi tersebut sehingga terbentuk graf berikut.

[collapse]

Soal Nomor 2
Benar atau salahkan pernyataan berikut? Jelaskan.
a) Jika graf G dan H isomorfik, maka keduanya mempunyai banyak titik yang sama dan banyak sisi yang sama pula.
b) Jika graf G dan H isomorfik, maka keduanya mempunyai barisan derajat yang sama.
c) Jika G dan H graf sederhana dan mempunyai barisan derajat yang sama, maka keduanya isomorfik.

Penyelesaian
[collapse]

(Jawaban a) Benar. Jika tidak demikian, maka fungsi yang terbentuk bukan bijektif/korespondensi satu-satu, padahal itu adalah syarat keisomorfikan graf. (ingat kembali bahwa syarat suatu fungsi dikatakan bijektif adalah banyaknya anggota domain sama dengan banyaknya anggota kodomain).
(Jawaban b) Benar. Ini merupakan syarat “melestarikan keterhubungan langsung” pada definisi graf isomorfik. Perlu ditekankan juga bahwa jika dua buah graf memiliki titik yang berderajat sama (graf beraturan), belum tentu kedua graf itu isomorfik, terkecuali graf itu adalah graf sederhana (simple graph).
(Jawaban c) Salah.

Kedua graf ini sederhana dan memiliki barisan derajat yang sama, tetapi tidak isomorfik. Mengapa? Silakan baca penyelesaian soal nomor 4b. Lanjutkan membaca “Soal Latihan dan Pembahasan – Graf Isomorfik dan Subgraf (Upagraf)”

Ayo Beri Rating Postingan Ini