Soal dan Pembahasan – 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. Bagi Anda yang ingin mempelajari kosa kata atau istilah graf, silakan kunjungi tautan di bawah.

Baca: Istilah Lengkap dalam Teori Graf

Quote by Francis of Assisi

Start by doing what’s necessary; then do what’s possible; and suddenly you are doing the impossible.

Soal Nomor 1
Gambarkan graf dengan $5$ titik dan $8$ sisi serta:

  1. sederhana.
  2. memuat loop dan sisi rangkap. 
  3. tidak sederhana dan memuat sisi rangkap.

Pembahasan

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

Graf di atas memiliki $5$ titik, yaitu $A, B, C, D$, dan $E$. Graf itu memiliki $8$ sisi (dapat dihitung dari jumlah garis yang ada), yaitu sisi $AB$, $AC$, $AE$, $BC$, $BE$, $CD$, $CE$, dan $DE$. Graf itu sederhana karena tidak memiliki sisi rangkap maupun loop.
Jawaban b)
Contoh graf sesuai dengan syarat yang diberikan bisa dilihat di gambar berikut. 



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

Perhatikan bahwa $AB$ terhubung oleh sisi rangkap, begitu juga dengan $BC$. Oleh karena graf ini mengandung sisi rangkap, maka graf ini dikatakan tidak sederhana. 

[collapse]

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

Pembahasan

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$ dapat dilihat 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.

Pembahasan

(Jawaban a)
Himpunan titik graf $G$ kita notasikan dengan $V(G)$, huruf $V$ diambil dari kata “Vertex”. Dari gambar, masing-masing graf telah diberi nama $G_1$, $G_2$, dan $G_3$. Untuk itu, dapat kita tuliskan:
$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)
Himpunan sisi graf $G$ kita notasikan dengan $E(G)$, huruf $E$ diambil dari kata “Edge”. Dari gambar, masing-masing graf telah diberi nama $G_1$, $G_2$, dan $G_3$. Untuk itu, kita dapat tuliskan:

$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.

Pembahasan

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$.
Graf sederhana adalah $G_1$ karena tidak memuat sisi rangkap maupun loop.

[collapse]

Baca: Soal dan Pembahasan – Keterhubungan Graf

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

Pembahasan

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.

  1. $V(G) = \{A, B, C, D\}$ dan $E(G) = \emptyset$.
  2. $V(G) = \{1, 2, 3, 4, 5, 6, 7\}$ dan $E(G) =\{11, 12, 37, 35, 67, 77\}$.

Pembahasan

Jawaban a)
Berdasarkan ketentuan tersebut, graf $G$ memiliki $4$ titik, yaitu $A, B, C$, dan $D$. Perhatikan bahwa $E(G)$ merupakan himpunan kosong, artinya graf $G$ tidak memiliki sisi. Dengan kata lain, graf tersebut hanya terdiri dari titik.

Jawaban b)
Berdasarkan ketentuan tersebut, graf $G$ memiliki $7$ titik yang ditandai dengan angka $1$ sampai $7$, serta $6$ sisi. Notasi $11$ pada $E(G)$ artinya ada sisi loop pada titik $1$, notasi $12$ artinya ada satu sisi yang menghubungkan titik $1$ dan $2$, dst. Perhatikan juga bahwa tidak ada angka $4$ yang muncul pada $E(G)$. Ini artinya $4$ adalah titik yang tidak terhubung oleh sisi manapun. Kita sebut titik $4$ sebagai titik terpencil (isolated vertex) dalam teori graf.
 

[collapse]

Baca: Soal dan Pembahasan – Graf Isomorfik dan Subgraf

Soal Nomor 7
Buktikan semua akibat dari lema jabat tangan berikut.

  1. Jumlah semua derajat titik pada suatu graf adalah genap.
  2. Pada suatu graf, banyak titik berderajat ganjil adalah genap.
  3. Jika $G$ graf beraturan-$r$, maka $|E(G)| = \dfrac{1}{2}r|V(G)|$.

Pembahasan

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)$. Pemisalan ini ada karena dalam setiap graf, titik dapat dikelompokkan menjadi dua, yakni titik yang memiliki derajat genap dan titik yang berderajat ganjil. Hal ini analog (serupa) pada himpunan bilangan asli, di mana ada bilangan genap dan bilangan ganjil.
Dengan demikian, 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.

 

Pembahasan

Jawaban a)
Derajat titik pada $G_1$ dapat dilihat pada tabel berikut.
$\begin{array}{|c|c|} \hline \text{Nama Titik} & \text{Derajat} \\ \hline a & 2 \\ \hline b & 4 \\ \hline c & 2 \\ \hline d & 4 \\ \hline \end{array}$
Derajat titik pada $G_2$ dapat dilihat pada tabel berikut.
$\begin{array}{|c|c|} \hline \text{Nama Titik} & \text{Derajat} \\ \hline p & 1 \\ \hline q & 3 \\ \hline r & 1 \\ \hline s & 3 \\ \hline \end{array}$
Derajat titik pada $G_3$ dapat dilihat pada tabel berikut.
$\begin{array}{|c|c|} \hline \text{Nama Titik} & \text{Derajat} \\ \hline u & 3 \\ \hline x & 1 \\ \hline v & 3 \\ \hline w & 1 \\ \hline \end{array}$
Catatan: Titik yang memiliki sisi loop memiliki $2$ derajat. Ini dapat dilihat dari jumlah sisi yang ditarik keluar dari titik yang bersangkutan.
Jawaban b)
Berdasarkan jawaban sebelumnya, kita peroleh:
barisan derajat pada $G_1$ adalah $(2, 4, 2, 4)$;

barisan derajat pada $G_2$ adalah $(1, 3, 1, 3)$;
barisan derajat pada $G_3$ adalah $(3, 1, 3, 1)$.
Catatan: Kita tidak mempermasalahkan urutan penulisan derajat titik yang ada pada graf. Sebagai contoh, $(2, 4, 2, 4)$ dianggap sama saja dengan $(4, 2, 4, 2)$.
Jawaban c)
Derajat maksimum adalah nilai terbesar dari derajat titik-titik di graf itu.
Derajat maksimum $G_1$ ada pada titik $b$ atau $d$, yaitu $d_{\text{maks}}(G_1) = 4$.
Derajat maksimum $G_2$ ada pada titik $q$ atau $s$, yaitu $d_{\text{maks}}(G_2) = 3$.
Derajat maksimum $G_3$ ada pada titik $u$ atau $v$, yaitu $d_{\text{maks}}(G_3) = 3$.
Jawaban d)
Derajat minimum adalah nilai terkecil dari derajat titik-titik di graf itu.
Derajat minimum $G_1$ ada pada titik $a$ atau $c$, yaitu $d_{\text{min}}(G_1) = 2$.
Derajat minimum $G_2$ ada pada titik $p$ atau $r$, yaitu $d_{\text{min}}(G_2) = 1$.
Derajat minimum $G_3$ ada pada titik $x$ atau $w$, yaitu $d_{\text{min}}(G_3) = 1$.

[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)$.

Pembahasan

Graf sederhana adalah graf yang tidak memuat sisi rangkap atau loop.
Jawaban a)
Perhatikan contoh graf berikut yang memenuhi barisan derajat yang diberikan.

Tabel berikut menjelaskan titik dan sisi dari gambar graf di atas.
$$\begin{array}{|c|c|c|} \hline \text{Nama Titik} & \text{Derajat/Jumlah Sisi} & \text{Nama Sisi} \\ \hline 1 & 5 & 12, 16, 17, 18, 19 \\ \hline 2 & 5 & 12, 23, 24, 25, 26 \\ \hline 3 & 4 & 23, 34, 35, 36 \\ \hline 4 & 3 & 24, 34, 45 \\ \hline 5 & 3 & 25, 35, 45 \\ \hline 6 & 3 & 16, 26, 36 \\ \hline 7 & 3 & 17, 78, 79 \\ \hline 8 & 3 & 18, 78, 89 \\ \hline 9 & 3 & 19, 79, 89 \\ \hline \end{array}$$Jawaban b)
Perhatikan contoh graf berikut yang memenuhi barisan derajat yang diberikan.

Tabel berikut menjelaskan titik dan sisi dari gambar graf di atas.
$$\begin{array}{|c|c|c|} \hline \text{Nama Titik} & \text{Derajat/Jumlah Sisi} & \text{Nama Sisi} \\ \hline 1 & 6 & 13, 14, 15, 16, 17, 18 \\ \hline 2 & 4 & 23, 24, 25, 26  \\ \hline 3 & 4 & 23, 34, 35, 36 \\ \hline 4 & 3 & 14, 24, 34 \\ \hline 5 & 3 & 15, 25, 35 \\ \hline 6 & 2 & 16, 26 \\ \hline 7 & 1 & 17 \\ \hline 8 & 1 &  18 \\ \hline \end{array}$$
 

[collapse]

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

Pembahasan

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 11a
Periksalah apakah barisan $(4~4~3~3~2)$ merupakan grafik atau bukan.

Pembahasan

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 11b
Periksalah apakah barisan $(6~4~4~3~3~2~1~1)$ merupakan grafik atau bukan.

Pembahasan

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 11c
Periksalah apakah barisan $(5~4~3~2~1~0)$ merupakan grafik atau bukan.

Pembahasan

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~\color{red}{- 1}$
Tampak bahwa $S_1$ memuat bilangan negatif, sehingga $S_1$ bukan grafik. Jadi, $S$ juga bukan grafik.

[collapse]

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

Pembahasan

Graf berikut merepresentasikan jabat tangan yang terjadi. Titik mewakili orang, sedangkan sisi mewakili jabat tangan. Jumlah jabat tangan diwakili oleh jumlah sisi pada graf tersebut, yaitu $4 + 3 + 2 + 1  = 10$.

[collapse]

Soal Nomor 13
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?

Pembahasan

Misalkan komputer itu direpresentasikan sebagai titik pada suatu graf. Himpunan titiknya adalah $(a, b, c, d, \cdots)$, yaitu sebanyak $n$ 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 graf sama dengan $1$ kurangnya dari banyak titik graf, yaitu $n-1$. Jadi, jumlah minimum potongan kabel yang dibutuhkan adalah $\boxed{n-1}$

[collapse]

Soal Nomor 14
Jika $G$ graf sederhana dengan paling sedikit $2$ titik, buktikanlah bahwa $G$ mempunyai paling sedikit $2$ titik berbeda dengan derajat yang sama.

Pembahasan

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$, $\cdots, 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 15
Tunjukkan bahwa graf bipartisi, sederhana, dan dengan $n$ titik, tidak mempunyai lebih dari $\dfrac{n^2}{4}$ sisi.

Pembahasan

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]

Baca: Soal dan Pembahasan – Struktur Pohon dalam Teori Graf

CategoriesTeori Graf, Matematika DiskritTags, , , , , ,

Leave a Reply

Silakan beri tanggapan dan saran, tidak perlu sungkan. Mohon juga diinformasikan melalui kolom komentar ini bila ada kesalahan pengetikan sekecil apapun (typo atau bahasa latex yang error) atau kesalahan konsep dan pembahasan soal. Terima kasih. Ganbatte!

Your email address will not be published. Required fields are marked *