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.


(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

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
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]

Soal Nomor 18 (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
KategoriMatematika DiskritTag, , ,

2 Balasan untuk “Soal dan Pembahasan – Keterhubungan Graf”

Tinggalkan Balasan

Alamat email Anda tidak akan dipublikasikan. Ruas yang wajib ditandai *