Soal dan Pembahasan – Keterhubungan 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. 

Baca: Soal dan Pembahasan – Teori Dasar Graf

Baca: Istilah Lengkap dalam Teori Graf

Today Quote

Saat kamu sedang di bawah, ada orang yang tidak menghormatimu. Saat kamu di tengah, ada orang yang tidak peduli denganmu. Saat kamu di atas, ada orang yang benci dan nyinyir padamu. Kamu tak akan bisa menyenangkan semua orang, sehingga tidak perlu memusingkan pendapat mereka dan tetaplah fokus pada tujuanmu.

Soal Nomor 1
Perhatikan graf $G$ berikut.

Berdasarkan graf di atas, carilah:

  1. Sebuah jalan tertutup dengan panjang $9$;
  2. Sebuah trail terbuka dengan panjang $9$;
  3. Sebuah trail tertutup dengan panjang $7$;
  4. Sebuah lintasan (path) dari simpul $a$ ke $n$;
  5. Panjang sikel terpanjang dalam $G$;
  6. Panjang lintasan (path) terpanjang dalam $G$;
  7. Lilitan (girth) dalam $G$;
  8. Sebuah graf bagian bukan rentang.

Pembahasan

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:

  1. $5$ titik, tanpa sikel, dan terhubung;
  2. $6$ titik, reguler-$2$, dan terdiri dari $2$ komponen.

Pembahasan

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

Pembahasan

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]

Baca: Soal dan Pembahasan – Graf Isomorfik dan Subgraf

Soal Nomor 4
Misalkan $G$ adalah suatu graf yang dipresentasikan seperti gambar berikut.

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

Pembahasan

Misalkan $A(G)$ menyatakan matriks keterhubungan langsung (adjacency matrix) dari graf $G$, maka $A(G)$ dapat dinyatakan sebagai berikut.
$\begin{aligned} 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} \end{aligned}$
($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.
$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}$

Catatan: $a_{ij}$ menyatakan banyaknya keterkaitan titik $i$ pada sisi $j$. Misalkan $a_{43}$ bernilai $1$ menyatakan ada $1$ sisi, yaitu sisi $3$, yang terkait dengan titik $4$.

[collapse]

Soal Nomor 5
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}$

Pembahasan

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

Penjelasan:

  1. Entri baris $1$ kolom $1= 0$, berarti tidak ada sisi loop pada titik $1$.
  2. Entri baris $1$ kolom $2 = 1$, artinya ada $1$ sisi yang menghubungkan titik $1$ dan $2$. 
  3. Entri baris $1$ kolom $3 = 0$, artinya tidak ada sisi yang menghubungkan titik $1$ dan $3$.
  4. 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]

Baca Juga: Soal dan Pembahasan – Matriks, Determinan, dan Invers Matriks

Soal Nomor 6
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}$

Pembahasan

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 7
Berilah contoh setiap graf berikut dengan paling banyak $6$ titik.
a. Graf Hamilton yang bukan Euler.
b. Graf Euler yang bukan Hamilton.

Pembahasan

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.
Jawaban a)

Graf $G$ di atas mengandung sikel Hamilton dengan barisan titik 
$a~b~d~c~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 di atas disebut graf Hamilton dan bukan graf Euler karena ada sisi yang tidak dilaluinya, yaitu sisi $bc$.
Jawaban b)

Graf $H$ 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 8
Tunjukkan bahwa setiap sikel pada graf bipartisi mempunyai panjang genap.

Pembahasan

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 9
Berilah $2$ contoh graf yang komplemen diri (self complementary).

Pembahasan

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 $2$ contoh graf yang komplemen diri.

[collapse]

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

Pembahasan

Ingat bahwa graf lengkap/komplit dengan $n$ titik memiliki $\dfrac{1}{2}n(n-1)$ sisi. Untuk graf yang komplemen diri, banyak sisinya adalah setengai banyaknya sisi pada graf lengkap, yaitu $\dfrac{1}{4}n(n-1)$. Agar diperoleh $n$ bh darulat, 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 11
Tuliskan matriks keterhubungan langsung dan matriks keterkaitan dari graf berikut.

Pembahasan

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
$$\begin{pmatrix} 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0  & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \end{pmatrix}$$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}$
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]

Baca: Soal dan Pembahasan – Struktur Pohon dalam Teori Graf

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

Pembahasan

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

Pembahasan

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

[collapse]

Soal Nomor 14
Tentukan $\chi(G)$ (baca: chi $G$) dan $\lambda(G)$ (baca: lambda $G$) dari graf $G$.
Catatan:
$\chi(G)$ menyatakan banyak minimum titik-titik di $G$ yang jika dihilangkan akan menghasilkan graf tak terhubung.
$\lambda(G)$ menyatakan banyak minimum sisi-sisi di $G$ yang jika dihilangkan akan menghasilkan graf tak terhubung.

Pembahasan

Untuk menentukan nilai $\chi(G)$, pertama, 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 tak terhubung. Sesuai definisi, maka $\chi(G) = 2$ (karena titik yang dihilangkan sebanyak $2$).
Untuk menentukan nilai $\lambda(G)$, pertama, hilangkan salah satu sisi, misalnya sisi $ab$, berarti $G$ 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) = 2$.

[collapse]

Soal Nomor 15
Tentukan $\chi(G_1)$, $\chi(G_2)$, $\lambda(G_1)$, dan $\lambda(G_2)$ dari graf-graf yang direpresentasikan sebagai berikut.


Pembahasan

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]

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 *