Soal Latihan dan Penyelesaian – Teori Dasar Graf (Graph Basic Theory)

        Berikut ini adalah beberapa soal mengenai teori dasar graf, yang sangat cocok bagi Anda yang baru saja mengenal materi graf. Beberapa soal diambil dari bahan ajar dosen dan sisanya diambil dari referensi lain terkait. Soal juga disertai penyelesaian, tetapi ada beberapa yang belum disertai (mungkin Anda bisa menyelesaikannya di kolom komentar). Bagi Anda yang ingin mempelajari kosa kata atau istilah graf, silakan klik sini

Soal Nomor 1
Gambarkan graf dengan 5 titik dan 8 sisi serta
a) sederhana
b) memuat loop dan sisi rangkap
c) tidak sederhana dan memuat sisi rangkap

Penyelesaian

a) Contoh graf sesuai dengan syarat yang diberikan bisa dilihat di gambar berikut.

b) Contoh graf sesuai dengan syarat yang diberikan bisa dilihat di gambar berikut. Perhatikan bahwa sisi penghubung AB ada sebanyak 3 sisi (yang disebut sisi rangkap/multiple edges) dan CC merupakan gelang (loop).

c) Contoh graf sesuai dengan syarat yang diberikan bisa dilihat di gambar berikut. Perhatikan bahwa sisi penghubung CD ada sebanyak 3 sisi (yang disebut sisi rangkap/multiple edges), begitu juga AE terhubung oleh sisi rangkap.

[collapse]

Soal Nomor 2
Misalkan G adalah graf dengan barisan derajat: (4, 3, 2, 1). Tentukan banyaknya sisi di G dan gambarkan graf G.

Penyelesaian

Menurut Lema Jabat Tangan (Handshaking Lemma), jumlah derajat titik pada suatu graf sama dengan 2 kali banyak sisi. Diketahui bahwa jumlah derajat titik-titik graf itu adalah 4 + 3 + 2 + 1 = 10. Dengan demikian, banyak sisi di G adalah \dfrac{1}{2} \times 10 = 5. Gambar graf G sebagai berikut.

Tampak pada gambar di atas bahwa derajat titik A, B, C, dan D berturut-turut adalah 1, 4, 3, dan 2. Tampak pula ada 5 sisi pada graf tersebut.

[collapse]

Soal Nomor 3
Untuk setiap graf berikut, tentukan
a) himpunan titiknya
b) himpunan sisinya

Penyelesaian

(Jawaban a)
V(G_1) = \{a, b, c, d \}
V(G_2) = \{u, v, w, x, y\}
V(G_3) = \{1, 2, 3, 4, 5, 6\}
(Jawaban b)
E(G_1) = \{ab, ac, bc, ad, bd, cd\}
E(G_2) = \{xy, xw, xu, vy, uw, uy, vu, vu\}
E(G_3) = \{12, 22, 23, 24, 25, 26, 45, 46\}

[collapse]

Soal Nomor 4
Perhatikan kembali graf yang diberikan pada soal nomor 3. Tentukan graf mana yang
a) sederhana
b) memuat loop
c) memuat sisi rangkap

Penyelesaian

Graf yang memuat sisi rangkap adalah graf G_2, yaitu pada sisi penghubung titik u dan v. Graf yang memuat loop adalah G_3 yaitu pada titik 2. Sedangkan graf sederhana adalah G_1 karena tidak memuat sisi rangkap maupun loop.

[collapse]

Soal Nomor 5
Apakah ada graf sederhana yang mempunyai barisan derajat (1, 2, 3, 4)? Jika tidak, berikan alasannya.

Penyelesaian

Tidak ada. Misalkan titik graf itu adalah a, b, c, dan d. Katakanlah d merupakan titik berderajat 4. Graf yang terbentuk bukan graf sederhana karena hanya ada 3 sisi yang ditarik dari d ke titik lain (a, b, c), sehingga 1 sisi lainnya pastilah akan menjadi bagian dari sisi rangkap atau loop di titik itu.

[collapse]

Soal Nomor 6
Gambarkan graf G dengan ketentuan berikut.
a) V(G) = \{t, u, v, w\} dan E(G) = \emptyset
b) V(G) = \{1, 2, 3, 4, 5, 6, 7\} dan E(G) =\left{\{1, 1\}, \{1, 2\}, \{3, 7\}, \{3, 5\}, \{6, 7\}, \{7, 7\}\right}

Penyelesaian

Contoh graf untuk soal 6a adalah sebagai berikut. Perhatikan bahwa tidak ada sisi dalam graf tersebut.

Contoh graf untuk soal 6b adalah sebagai berikut.

[collapse]

Soal Nomor 7
Buktikan semua akibat dari lema jabat tangan (handshaking lemma) berikut.
a) Jumlah semua derajat titik pada suatu graf adalah genap.
b) Pada suatu graf, banyak titik berderajat ganjil adalah genap.
c) Jika G graf beraturan-r, maka |E(G)| = \dfrac{1}{2}r|V(G)|

Penyelesaian

Jawaban a
Berdasarkan lema jabat tangan, jumlah semua derajat titik suatu graf sama dengan 2 kali banyak sisinya. Dengan demikian, jelas bahwa derajat suatu graf adalah genap. (Terbukti)

Jawaban b
Misalkan V_A dan V_B berturut-turut adalah himpunan titik-titik berderajat genap dan ganjil pada graf G(V, E), sehingga haruslah berlaku
\displaystyle \sum_{i = 1}^{n} d(v_i) = \sum_{v_j \in V_A} d(v_j) + \sum_{v_k \in V_B} d(v_k)
Dengan meninjau lema jabat tangan, kita tahu bahwa \displaystyle \sum_{i = 1}^{n} d(v_i) bernilai genap (jumlah derajat titiknya genap). Karena \displaystyle \sum_{v_j \in V_A} d(v_j) juga genap, maka agar hasil penjumlahan (ruas kanan) genap, haruslah \displaystyle \sum_{v_k \in V_B} d(v_k) genap (bil. genap = bil. genap + bil. genap). Jadi, banyak titik berderajat ganjil pada suatu graf adalah genap. (Terbukti)
Ilustrasi: Misalkan diberikan 4 titik berderajat ganjil pada suatu graf dengan derajat (1, 3, 5, 7) sehingga bila dijumlahkan, diperoleh 1 + 3 + 5 + 7 = 16 (genap). Dengan kata lain, bilangan ganjil itu harus sebanyak genap agar bila dijumlahkan menghasilkan bilangan genap.

Jawaban c
Graf beraturan-r adalah graf yang semua titiknya berderajat r. Jadi, jika ada titik dalam graf sebanyak |V(G)|, maka jumlah derajatnya adalah r \times |V(G)|. Menurut lema jabat tangan, berlaku \displaystyle \sum_{v \in V(G)} d(v) = 2|E(G)|. Dalam kasus ini, \displaystyle \sum_{v \in V(G)} d(v) = r \times |V(G)|. Jadi, diperoleh
r \times |V(G)| = 2|E(G)| atau
|E(G)| = \dfrac{1}{2}r \times |V(G)| (Terbukti)

[collapse]

Soal Nomor 8
Untuk masing-masing graf berikut, tentukan
a) derajat titiknya
b) barisan derajatnya
c) derajat maksimum
d) derajat minimum

Penyelesaian

Jawaban a
Pada G_1, d(a) = d(c) = 2, d(b) = d(d) = 4. Pada G_2, d(p) = d(r) = 1, d(s) = d(q) = 3. Pada G_3, d(x) = d(w) = 2, d(u) = d(v) = 4

Jawaban b
Barisan derajat pada G_1 adalah (2, 2, 4, 4)
Barisan derajat pada G_2 adalah (1, 1, 3, 3)
Barisan derajat pada G_3 adalah (2, 2, 4, 4)

Jawaban c
Derajat maksimum adalah nilai terbesar dari derajat titik-titik di graf itu.
Derajat maksimum G_1 adalah 4.
Derajat maksimum G_2 adalah 3.
Derajat maksimum G_3 adalah 4.

Jawaban d
Derajat minimum adalah nilai terkecil dari derajat titik-titik di graf itu.
Derajat minimum G_1 adalah 2.
Derajat minimum G_2 adalah 1.
Derajat minimum G_3 adalah 2.

[collapse]

Soal Nomor 9
Gambarlah graf sederhana dengan barisan derajat
a) (5, 5, 4, 3, 3, 3, 3, 3, 3)
b) (6, 4, 4, 3, 3, 2, 1, 1)

Penyelesaian

Contoh graf dengan syarat yang diminta pada soal nomor 9a adalah sebagai berikut.

Contoh graf dengan syarat yang diminta pada soal nomor 9b adalah sebagai berikut.

[collapse]

Soal Nomor 10 (pilihan ganda)
Graf K_{m,n} beraturan jika dan hanya jika …
a. semua titik memiliki derajat yang berbeda
b. semua titiknya berderajat sama
c. jumlah titiknya sama dengan jumlah sisinya
d. tidak ada loop dan sisi rangkap

Soal Nomor 11 (pilihan ganda)
Graf sederhana dengan n titik mempunyai derajat maksimum …
a. n
b. n - 1
c. -n
d. 2n

Penyelesaian

Graf sederhana dengan n titik mempunyai derajat maksimum n - 1 (kunci: b)

[collapse]

Soal Nomor 12
Buktikan bahwa tidak ada graf dengan tujuh titik yang beraturan dengan derajat 3.

Penyelesaian

Menurut akibat lema jabat tangan, jumlah semua derajat suatu graf adalah genap, tetapi graf 3-beraturan dengan 7 titik memiliki jumlah derajat 3 \times 7 = 21, padahal 21 adalah bilangan ganjil. Jadi, tidak mungkin ada graf 3-beraturan dengan 7 titik. (Terbukti)

[collapse]

Soal Nomor 13a
Periksalah apakah barisan (4~4~3~3~2) merupakan grafik atau bukan.

Penyelesaian

Perhatikan bahwa banyaknya bilangan pada S = 4~4~3~3~2 adalah 5. Jelas bahwa n = 5 \geq 1. Tampak pula bahwa S tidak memuat bilangan yang lebih dari 4 dan tidak semua bilangannya 0, serta tidak ada bilangan negatif. S sudah terurut berupa bilangan monoton turun, sehingga langkah selanjutnya adalah sebagai berikut.
S =  4~4~3~3~2
(Eksekusi 4 dan kurangi 4 bilangan disampingnya dengan 1)
S_1 = 3~2~2~1
(Eksekusi 3 dan kurangi 3 bilangan disampingnya dengan 1)
S_2 = 1~1~0
(Eksekusi 1 dan kurangi 1 bilangan disampingnya dengan 1)
S_3 = 0~0
Tampak bahwa S_3 hanya memuat bilangan 0, sehingga S_3 grafik. Jadi, S juga grafik.

[collapse]

Soal Nomor 13b
Periksalah apakah barisan (6~4~4~3~3~2~1~1) merupakan grafik atau bukan.

Penyelesaian

Perhatikan bahwa banyaknya bilangan pada S = 6~4~4~3~3~2~1~1 adalah 8. Jelas bahwa n = 8 \geq 1. Tampak pula bahwa S tidak memuat bilangan yang lebih dari 7 dan tidak semua bilangannya 0, serta tidak ada bilangan negatif. S sudah terurut berupa bilangan monoton turun, sehingga langkah selanjutnya adalah sebagai berikut.
S = 6~4~4~3~3~2~1~1
(Eksekusi 6 dan kurangi 6 bilangan disampingnya dengan 1)
S_1' = 3~3~2~2~1~0~1 \Rightarrow S_1 = 3~3~2~2~1~1~0
(Eksekusi 3 dan kurangi 3 bilangan disampingnya dengan 1)
S_2 = 2~1~1~1~1~0
(Eksekusi 2 dan kurangi 2 bilangan disampingnya dengan 1)
S_3' = 0~0~1~1~0 \Rightarrow S_3 = 1~1~0~0~0
(Eksekusi 1 dan kurangi 1 bilangan disampingnya dengan 1)
S_4 = 0~0~0~0
Tampak bahwa S_4 hanya memuat bilangan 0, sehingga S_4 grafik. Jadi, S juga grafik.

[collapse]

Soal Nomor 13c
Periksalah apakah barisan (5~4~3~2~1~0) merupakan grafik atau bukan.

Penyelesaian

Perhatikan bahwa banyaknya bilangan pada S = 5~4~3~2~1~0 adalah 6. Jelas bahwa n = 6 \geq 1. Tampak pula bahwa S tidak memuat bilangan yang lebih dari 5 dan tidak semua bilangannya 0, serta tidak ada bilangan negatif. S sudah terurut berupa bilangan monoton turun, sehingga langkah selanjutnya adalah sebagai berikut.
S = 5~4~3~2~1~0
(Eksekusi 5 dan kurangi 5 bilangan disampingnya dengan 1)
S_1 = 3~2~1~0~-1
Tampak bahwa S_1 memuat bilangan negatif, sehingga S_1 bukan grafik. Jadi, S juga bukan grafik.

[collapse]

Soal Nomor 14
Dalam sebuah pesta, sepuluh orang saling berjabat tangan. Tiap orang hanya berjabat tangan satu kali dengan orang lainnya. Hitung jumlah jabat tangan yang terjadi dan modelkan dalam graf.

Penyelesaian


Graf di atas merepresentasikan jabat tangan yang terjadi. Titik mewakili orang, sedangkan sisi mewakili jabat tangan. Jumlah jabat tangan = jumlah sisi pada graf = 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1  = 45.

[collapse]

Soal Nomor 15
Ada n buah komputer yang akan dihubungkan dengan sejumlah kabel, baik secara langsung atau terhubung melalui komputer lainnya. Berapa jumlah minimum potongan kabel yang dibutuhkan?

Penyelesaian

Misalkan komputer itu direpresentasikan sebagai titik pada suatu graf. Himpunan titiknya adalah (a, b, c, d, …..), yaitu sebanyak titik. Agar semua titik ini terhubung baik secara langsung maupun melalui komputer lainnya dengan sisi minimum, titik-titik tersebut harus diposisikan sedemikian sehingga tidak ada sisi yang bercabang seperti berikut.
(Catatan: sisi yang terkait dengan titik d selain sisi cd menunjukkan representasi sisi yang berlaku umum sampai titik-titik selanjutnya, bukan sisi yang hanya memiliki satu titik ujung)

Jadi, dalam hal ini, titik a adjacent dengan titik b, titik b adjacent dengan titik c, dan seterusnya, sehingga banyak sisi = banyak titik – 1 = n – 1. Jadi, jumlah minimum potongan kabel yang dibutuhkan adalah \boxed{n - 1}

[collapse]

Soal Nomor 16
Jika G graf sederhana dengan paling sedikit 2 titik, buktikanlah bahwa G mempunyai 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 17
Jika G graf beraturan r, r \geq 1, dan G bipartisi dengan himpunan partisinya, yaitu A dan B, buktikan bahwa |A| = |B|

Penyelesaian Belum Tersedia
[collapse]

Soal Nomor 18
Tunjukkan bahwa graf bipartisi, sederhana, dan dengan n titik, tidak mempunyai lebih dari \dfrac{n^2}{4} sisi.

Penyelesaian

Pada graf bipartisi, sederhana, dan dengan n titik, kita bisa mempartisi n titik tersebut dalam himpunan bagian (beranggotakan titik pada graf) dengan ukuran i dan n - i, 0 \leq i \leq n. Sisi yang dimiliki juga harus menghubungkan titik pada himpunan yang satu ke titik pada himpunan yang lain. Jadi, maksimum sisi yang mungkin adalah i(n-i) sisi (terjadi ketika setiap titik pada himpunan yang satu terhubung ke setiap titik pada himpunan yang lain, atau disebut graf bipartisi lengkap). Jadi, kita dapat tuliskan sebagai suatu fungsi
f(i) = i(n - i), 0 \leq i \leq n
f(i) akan maksimum saat i = \dfrac{n}{2}, sehingga jumlah maksimum sisinya adalah
i(n-i) = \dfrac{n}{2}\left(n - \dfrac{n}{2}\right) = \dfrac{n^2}{4}
Jadi, terbukti bahwa graf bipartisi, sederhana, dan dengan n titik, tidak mempunyai lebih dari \dfrac{n^2}{4} sisi.

[collapse]
Ayo Beri Rating Postingan Ini