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.

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.

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

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

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.


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

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
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 11
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 12
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 13
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 14
Misallan $G$ graf bipartisi. Tunjukkan bahwa matriks keterhubungan langsung dari $G$ dapat ditulis dalam bentuk
$A(G) = \left[ \begin{array}{c|c} O & P \\ \hline Q & O \end{array} \right]$
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 15
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 16
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 17
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]

CategoriesMatematika 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 *