Materi, Soal, dan Pembahasan – Keterhubungan Graf

Banyak masalah nyata yang dapat dimodelkan dalam bentuk lintasan dari suatu graf. Sebagai contoh, masalah penentuan pengiriman pesan dari satu komputer ke komputer yang lain dan masalah rute terpendek. Berkaitan dengan hal itu, kita mempelajari tentang keterhubungan graf yang diawali dengan istilah lintasan.

Secara informal, lintasan merupakan barisan sisi-sisi yang dimulai dari suatu simpul graf, kemudian berkeliling dari simpul yang satu ke simpul yang lain melalui sisi-sisi tersebut. Berikut diberikan definisi formal dari lintasan.

Artikel tentang Graf

Definisi: Lintasan

Misalkan $n$ merupakan bilangan bulat nonnegatif dan $G$ merupakan graf tak-berarah. Lintasan (path) dengan panjang (length) $n$ dari simpul $u$ ke $v$ di $G$ merupakan barisan dari $n$ sisi $e_1, e_2, \cdots, e_n$ di $G$ sehingga terdapat suatu barisan simpul $x_0 = u, x_1, x_2, \cdots, x_{n-1}, x_n = v$ yang sisi $e_i$-nya memiliki simpul ujung $x_i-1$ dan $x_i$ untuk $i \in \{1, 2, \cdots, n\}.$ 

Jika grafnya sederhana, kita menotasikan lintasan dengan menggunakan barisan simpul $(x_0, x_1, \cdots, x_n)$ (karena mendaftarkan simpul-simpul tersebut menghasilkan lintasan yang tunggal). Suatu lintasan disebut sirkuit jika dimulai dan diakhiri oleh simpul yang sama, yaitu $u = v$ dan panjangnya bukan nol. Lintasan dikatakan melalui (melewati) (pass through) simpul $x_1, x_2, \cdots, x_{n-1}$ atau melintasi (traverse) sisi $e_1, e_2, \cdots, e_n.$ Lintasan dikatakan sederhana (simple) jika tidak memuat sisi yang sama lebih dari satu kali.

Sebagai contoh, perhatikan model graf berikut.
Contoh lintasan dengan panjang $4$ dan simpul awal $a$ di $G$ adalah $(a, b, c, d)$ dan $(a, b, c, g).$ Keduanya juga tergolong lintasan sederhana karena tidak memuat sisi yang sama lebih dari satu kali. Perhatikan bahwa $(b, c, d, e, g, c)$ juga merupakan lintasan di $G$ yang panjangnya $4$ meskipun melalui simpul yang sama lebih dari sekali. Sebaliknya, $(a, b, d, e)$ bukan lintasan karena tidak ada sisi yang menghubungkan simpul $b$ dan $d.$ Lebih lanjut, $(a, a, b, b)$ bukan lintasan karena terdapat simpul yang sama secara berurutan.

Definisi: Graf Terhubung pada Graf Tak-Berarah

Suatu graf tak-berarah $G$ dikatakan terhubung (connected) jika terdapat lintasan di antara setiap pasang simpul berbeda dari graf tersebut. Graf tak-berarah yang tidak terhubung disebut takterhubung (disconnected). Kita memutus (disconnect) graf ketika menghilangkan simpul atau sisi (atau keduanya) sehingga menghasilkan subgraf takterhubung.

Sebagai contoh, perhatikan model graf berikut.
Graf $H_1$ merupakan graf terhubung karena terdapat lintasan di antara setiap pasang simpul berbeda dari graf tersebut. Sebaliknya, graf $H_2$ bukan graf terhubung karena tidak terdapat lintasan yang menghubungkan simpul $e$ dengan simpul lainnya. 

Selanjutnya, perlu diketahui bahwa graf trivial (graf dengan satu simpul tanpa ada satu sisi pun) juga merupakan graf terhubung. Hal ini dapat dipahami dengan mengasumsikan bahwa simpul tunggalnya terhubung dengan dirinya sendiri. Lebih lanjut, graf kosong dengan $n \ge 2$ simpul jelas bukan graf terhubung.

Pada graf berarah, graf terhubung didefinisikan seperti berikut.

Definisi: Graf Terhubung pada Graf Berarah

Graf berarah $G$ dikatakan terhubung jika graf tak-berarahnya terhubung. Graf tak-berarah dari $G$ diperoleh dengan menghilangkan arahnya.

Keterhubungan dua simpul pada graf berarah dibedakan menjadi dua macam, yaitu terhubung kuat dan terhubung lemah. Dua simpul $u$ dan $v$ pada graf berarah $G$ dikatakan terhubung kuat (strongly connected) jika terdapat lintasan berarah dari $u$ ke $v,$ dan sebaliknya, dari $v$ ke $u.$ Sementara itu, dua simpul $u$ dan $v$ pada graf berarah $G$ dikatakan terhubung lemah (weakly connected) jika $u$ dan $v$ tidak terhubung kuat, tetapi tetap terhubung pada graf tak-berarahnya. Sebagai contoh, perhatikan model graf berarah berikut.
Graf $L$ memiliki $6$ simpul. Simpul $v_2$ dan $v_3$ terhubung kuat karena ada lintasan berarah $(v_2, v_3)$ dan $(v_3, v_4, v_1, v_2)$ yang menghubungkan dua simpul tersebut. Simpul $v_1$ dan $v_5$ terhubung lemah karena tidak terdapat lintasan berarah yang berawal dari $v_5$ dan berakhir di $v_1.$ Lebih lanjut, $v_i (1 \le i \le 5)$ dan $v_6$ merupakan simpul yang tidak terhubung.

Terminologi terhubung kuat dan terhubung lemah dari dua simpul pada graf berarah memunculkan definisi graf terhubung kuat dan graf terhubung lemah.

Definisi: Graf Terhubung pada Graf Berarah

Graf berarah $G$ disebut graf terhubung kuat (strongly connected graph) jika setiap pasang simpul sembarang $v_i$ dan $v_j$ di $G$ terhubung kuat. Jika tidak, $G$ dikatakan graf terhubung lemah (weakly connected graph).

Berikutnya, kita akan mendefinisikan terminologi lain dari graf terhubung.

Definisi: Komponen

Komponen (component) dari suatu graf merupakan subgraf terhubung maksimal, artinya tidak ada simpul lain yang dapat ditambahkan lagi untuk mempertahankan keterhubungan subgraf tersebut.

Sebagai contoh, perhatikan model graf berikut.
Graf $M$ di atas memiliki $4$ komponen, masing-masing memuat simpul yang diberi warna yang sama. Diketahui bahwa salah satu komponen merupakan graf trivial, yaitu subgraf dari $M$ yang memuat simpul dengan warna merah.

Masalah Tujuh Jembatan Königsberg diselesaikan oleh Leonhard Euler (1707–1783). Setelah itu, teori graf menjadi salah satu topik matematika diskrit yang terus dikembangkan hingga saat ini. Sebagai bentuk penghormatan, masalah yang diselesaikan oleh Euler tersebut menggunakan terminologi yang didefinisikan dengan menggunakan namanya sendiri.

Definisi: Lintasan Euler

Lintasan Euler (Eulerian path), kadang juga disebut jejak Euler (Eulerian trail), adalah lintasan yang melalui semua sisi dari suatu graf tepat satu kali.

Definisi di atas mengizinkan lintasan yang dibuat melalui sejumlah simpul lebih dari sekali. Sebagai contoh, perhatikan model graf berikut.
Graf $K_1$ tidak memuat lintasan Euler. Berbeda darinya, graf $K_2$ dan $K_3$ keduanya memuat lintasan Euler. Simpul merah dan biru pada masing-masing graf berturut-turut merepresentasikan simpul awal dan akhirnya, sedangkan angka pada setiap sisi menyatakan urutan sisi yang akan dilintasi oleh lintasan Euler. 

Definisi: Siklus Euler

Siklus Euler (Eulerian cycle), kadang juga disebut sirkuit Euler (Eulerian circuit), adalah siklus yang melalui semua sisi dari suatu graf tepat satu kali.

Berdasarkan definisi tersebut, dapat juga dikatakan bahwa siklus Euler merupakan lintasan Euler yang diberikan syarat tambahan, yaitu simpul awal dan simpul akhirnya harus sama. Selanjutnya, graf yang mempunyai lintasan Euler disebut sebagai graf semi-Euler (semi-Eulerian graph), sedangkan graf yang mempunyai siklus Euler disebut sebagai graf Euler (Eulerian graph).

Lintasan dan siklus Euler melalui semua sisi pada graf tepat sekali. Jika kita ingin membuat lintasan atau siklus yang memuat semua simpul pada graf tepat sekali, kita akan mengenal terminologi baru yang disebut sebagai lintasan Hamilton dan siklus Hamilton, diambil dari nama penemunya, William Rowan Hamilton (1805–1865), di masa sepeninggalan Euler.

Definisi: Lintasan Hamilton

Lintasan Hamilton (Hamiltonian path), kadang juga disebut jejak Hamilton (Hamiltonian trail), adalah lintasan yang melalui semua simpul dari suatu graf tepat satu kali.

Sebagai contoh, perhatikan model graf berikut.
Graf $G$ tidak memiliki lintasan Hamilton, sedangkan graf $H$ memilikinya. Lintasan Hamilton yang dimaksud adalah $\{1, 2, 3, 4, 5, 6, 7\}.$

Definisi: Siklus Hamilton

Siklus Hamilton (Hamiltonian cycle), kadang juga disebut sirkuit Hamilton (Hamiltonian circuit), adalah siklus yang melalui semua simpul dari suatu graf tepat satu kali, kecuali simpul awal dan simpul akhirnya (karena memang harus sama berdasarkan definisi siklus).

Berdasarkan definisi tersebut, dapat juga dikatakan bahwa siklus Hamilton merupakan lintasan Hamilton yang diberikan syarat tambahan, yaitu simpul awal dan simpul akhirnya harus sama. Selanjutnya, graf yang mempunyai lintasan Hamilton disebut sebagai graf semi-Hamilton (semi-Hamiltonian graph), sedangkan graf yang mempunyai siklus Hamilton disebut sebagai graf Hamilton (Hamiltonian graph).


Di bawah ini telah disediakan sejumlah soal dan pembahasan tentang keterhubungan graf. Sebagian soal dibuat oleh penulis sendiri dan sebagian lainnya diadaptasi dari literatur.

Baca: Istilah Lengkap dalam Teori Graf


Artikel ini ditulis berdasarkan beberapa sumber. Salah satu sumber berbahasa Indonesia yang digunakan adalah buku “Matematika Diskrit” karya Rinaldi Munir. Untuk sumber berbahasa Inggris, salah satu yang digunakan adalah buku “Discrete Mathematics and Its Applications” yang ditulis oleh Kenneth H. Rosen. Oleh karena itu, untuk meminimalisasi kesalahan penafsiran, padanan untuk beberapa kata/istilah diberikan dalam tabel berikut.

$$\begin{array}{ccc} \hline \text{No.} & \text{Bahasa Indonesia} & \text{Bahasa Inggris} \\ \hline 1. & \text{Keterhubungan} & \text{Connectivity} \\ 2. & \text{Lintasan} & \text{Path} \\ 3. & \text{Sirkuit} & \text{Circuit} \\ 4. & \text{Siklus} & \text{Cycle} \\ 5. & \text{Panjang} & \text{Length} \\ 6. & \text{Melalui (Melewati)} & \text{Pass Through} \\ 7.  & \text{Melintasi} & \text{Traverse} \\ 8. & \text{Graf Terhubung} & \text{Connected Graph} \\ 9. & \text{Graf Takterhubung} & \text{Disconnected Graph} \\ 10. & \text{Graf Terhubung Lemah} & \text{Weakly Connected Graph} \\ 11. & \text{Graf Terhubung Kuat} & \text{Strongly Connected Graph} \\ 12. & \text{Komponen} & \text{Component} \\ 13. & \text{Lintasan Euler} & \text{Eulerian Path} \\ 14. & \text{Jejak Euler} & \text{Eulerian Trail} \\ 15. & \text{Siklus Euler} & \text{Eulerian Cycle} \\ 16. & \text{Sirkuit Euler} & \text{Eulerian Circuit} \\ 17. & \text{Graf Semi-Euler} & \text{Semi-Eulerian Graph} \\ 18. & \text{Graf Euler} & \text{Eulerian Graph} \\ 19. & \text{Lintasan Hamilton} & \text{Hamiltonian Path} \\ 20. & \text{Jejak Hamilton} & \text{Hamiltonian Trail} \\ 21. & \text{Siklus Hamilton} & \text{Hamiltonian Cycle} \\ 22. & \text{Sirkuit Hamilton} & \text{Hamiltonian Circuit} \\ 23 & \text{Graf Semi-Hamilton} & \text{Semi-Hamiltonian Graph} \\ 24. & \text{Graf Hamilton} & \text{Hamiltonian Graph} \\ 25. & \text{Diameter} & \text{Diameter} \\ \hline \end{array}$$


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.

Bagian Pilihan Ganda

Soal Nomor 1

Perhatikan model graf berikut.
Salah satu lintasan dengan panjang $5,$ simpul awal $a,$ dan simpul akhir $f$ adalah $\cdots \cdot$
A. $(a, b, e, f, g, h)$
B. $(a, f, f, f, f, f)$
C. $(a, f, e, d, c, f)$
D. $(a, b, c, h, g, f)$
E. $(a, h, g, f)$

Pembahasan

Dari graf tersebut, akan ditinjau lintasan dengan panjang $5,$ simpul awal $a,$ dan simpul akhir $f.$
Cek opsi A:
Barisan simpul $(a, b, e, f, g, h)$ merupakan lintasan dengan panjang $5,$ simpul awal $a,$ dan simpul akhir $h$ sehingga tidak memenuhi kriteria.
Cek opsi B:
Barisan simpul $(a, f, f, f, f, f)$ bukan lintasan karena memuat simpul yang sama secara berurutan.
Cek opsi C:
Barisan simpul $(a, f, e, d, c, f)$ bukan lintasan karena tidak ada sisi yang menghubungkan simpul $c$ dan $f.$
Cek opsi D:
Barisan simpul $(a, b, c, h, g, f)$ merupakan lintasan dengan panjang $5,$ simpul awal $a,$ dan simpul akhir $f$ sehingga memenuhi kriteria.
Cek opsi E:
Barisan simpul $(a, h, g, f)$ merupakan lintasan dengan panjang $3,$ simpul awal $a,$ dan simpul akhir $f$ sehingga tidak memenuhi kriteria.
(Jawaban D)

[collapse]

Bagian Uraian

Soal Nomor 1

Dengan menggunakan lintasan, tunjukkan bahwa dua graf berikut tidak isomorfis.

Pembahasan

Graf $G$ memuat lintasan $(v_1, v_2, v_3, v_1)$ dengan panjang $3.$ Namun, tidak ada lintasan dengan panjang $3$ di $H.$ Dari sini, disimpulkan bahwa $G$ dan $H$ tidak isomorfis.

[collapse]

Soal Nomor 2

Jika $G$ merupakan graf dengan derajat simpul minimum $\delta,$ maka $G$ memuat lintasan dengan panjang $\delta.$

Pembahasan

Misalkan $G$ merupakan graf dengan derajat simpul minimum $\delta.$ Misalkan juga $P = (v_0, v_1, \cdots, v_{k-1}, v_k)$ merupakan lintasan terpanjang di $G.$ Dari sini, kita tahu bahwa panjang $P$ adalah $k.$
Klaim bahwa $v_k$ harus bertetangga dengan simpul-simpul pembentuk lintasan $P.$ Dengan menggunakan metode kontradiksi, andaikan $v_k$ bertetangga dengan simpul selain yang termuat di $P,$ katakanlah $v_j.$ Akibatnya, kita dapat memperpanjang lintasan $P$ menjadi $(v_0, v_1, \cdots, v_{k-1}, v_k, v_j).$ Namun, hal ini kontradiksi dengan pernyataan bahwa $P$ merupakan lintasan terpanjang. Jadi, klaim terbukti.
Selanjutnya, karena $\text{deg}(v_k) \ge \delta,$ haruslah $k \ge \delta.$ Jika $k = \delta,$ pembuktian selesai. Jika $k > \delta,$ kita dapat membuat sublintasan dari $P$ dengan panjang $\delta,$ yaitu $P_\delta =(v_0, v_1, \cdots, v_{\delta}).$ Dengan demikian, $G$ memuat lintasan dengan panjang $\delta.$
Jadi, proposisi terbukti benar. $\blacksquare$

[collapse]

Soal Nomor 3

Misalkan $G$ merupakan graf sederhana. Buktikan bahwa setidaknya salah satu di antara $G$ atau $\overline{G}$ merupakan graf terhubung.

Pembahasan

Misalkan $G = (V(G), E(G))$ merupakan graf sederhana. Tanpa mengurangi keumuman, misalkan juga $G$ merupakan graf takterhubung. Akan ditunjukkan bahwa $\overline{G} = (V(\overline{G}), E(\overline{G}))$ terhubung. 
Ambil sembarang simpul $v, w \in V(G).$ Tinjau dua kasus berikut.

  1. Jika $\{v, w\} \notin E(G),$ maka menurut definisi graf komplemen, $\{v, w\} \in E(\overline{G})$ sehingga ada lintasan dari $v$ ke $w$ di $\overline{G}.$
  2. Jika $\{v, w\} \in E(G),$ maka $v$ dan $w$ keduanya berada di dalam satu komponen di $G.$ Karena $G$ takterhubung, terdapat simpul lain $u$ sehingga $\{u, v\} \notin E(G)$ dan $\{u, w\} \notin E(G).$ Akibatnya, $\{u, v\} \in E(\overline{G})$ dan $\{u, w\} \in E(\overline{G})$ sehingga $(u, v, w)$ membentuk lintasan di $\overline{G}.$

Dari dua kasus tersebut, didapat bahwa selalu ada lintasan yang menghubungkan setiap dua simpul di $\overline{G}.$ Berdasarkan definisi, disimpulkan bahwa $\overline{G}$ merupakan graf terhubung. $\blacksquare$

[collapse]

Soal Nomor 4

Misalkan $G = (V, E)$ merupakan graf sederhana dengan $n$ simpul. Buktikan bahwa jika $\text{deg}(v) \ge \dfrac12(n-1)$ untuk setiap $v \in V,$ maka $G$ terhubung.

Pembahasan

Misalkan $G = (V, E)$ merupakan graf sederhana dengan $n$ simpul. Misalkan juga $\text{deg}(v) \ge \dfrac12(n-1)$ untuk setiap $v \in V.$ Akan ditunjukkan bahwa $G$ terhubung.
Dengan menggunakan metode kontradiksi, andaikan $G$ takterhubung. Ini berarti $G$ memuat minimal dua komponen, $C_1$ dan $C_2,$ masing-masing setidaknya memuat satu simpul. Tinjau suatu simpul $x \in C_1.$ Diketahui bahwa $\text{deg}(x) \ge \dfrac12(n-1).$ Dengan kata lain, banyaknya tetangga dari $x$ di $C_1$ paling sedikit adalah $\dfrac12(n-1).$ Ditambah dengan dirinya sendiri, banyak simpul minimum di $C_1$ adalah $1 + \dfrac12(n-1) = \dfrac12(n+1).$ Hal demikian juga berlaku untuk komponen $C_2.$ Akibatnya, banyak simpul minimum di $G$ secara keseluruhan adalah
$$\dfrac12(n+1) + \dfrac12(n+1) = n+1.$$Hal ini kontradiksi dengan fakta bahwa $G$ hanya memiliki $n$ simpul. Jadi, pengandaian salah. Disimpulkan bahwa $G$ terhubung. $\blacksquare$

[collapse]

Soal Nomor 5

Misalkan $G = (V, E)$ merupakan graf dengan $|V(G)| = n.$ Buktikan bahwa jika $\text{deg}(u) + \text{deg}(v) \ge n-1$ untuk setiap dua simpul yang tidak bertetangga $u, v \in V(G),$ maka $G$ terhubung dan $\text{diam}(G) \le 2.$
Catatan: Diameter dari $G,$ dinotasikan $\text{diam}(G),$ merupakan jarak terjauh dari dua simpul sembarang di $G.$

Pembahasan

Misalkan $G = (V, E)$ merupakan graf dengan $|V(G)| = n.$ Ambil sembarang simpul $u, v \in V(G)$ dengan $\{u, v\} \notin E(G)$ sehingga $\text{deg}(u) + \text{deg}(v) \ge n-1.$ Akan ditunjukkan bahwa $G$ terhubung, artinya terdapat lintasan yang menghubungkan setiap dua simpul di $G.$ Selanjutnya, akan ditunjukkan juga bahwa lintasan itu memiliki panjang minimum $2.$
Karena $\text{deg}(u) + \text{deg}(v) \ge n-1,$ terdapat paling sedikit $n-1$ sisi yang menghubungkan simpul $u$ atau $v$ ke $n-2$ simpul yang lain. Karena banyak simpul tersebut lebih sedikit dari banyak sisi minimum, akan ada simpul $w \in V(G)$ sehingga $\{u, w\} \in E(G)$ dan $\{v, w\} \in E(G).$ Dengan demikian, diperoleh $(u, w, v)$ yang merupakan lintasan dengan panjang $2.$ Berdasarkan definisi, $G$ terhubung dan $\text{diam}(G) \le 2.$ $\blacksquare$

[collapse]

Soal Nomor 6

Buktikan bahwa sisi $e$ dari suatu graf $G$ merupakan jembatan jika dan hanya jika $e$ bukan sisi pembentuk siklus di $G.$

Pembahasan

Kita akan membuktikan proposisi di atas dari dua arah karena proposisi tersebut berupa biimplikasi.
Arah kiri:
Misalkan sisi $e$ dari suatu graf $G$ merupakan jembatan. Akan dibuktikan bahwa $e$ bukan sisi pembentuk siklus di $G.$
Dengan menggunakan metode kontradiksi, andaikan $e$ merupakan sisi pembentuk siklus di $G.$ Akibatnya, penghapusan sisi $e$ tidak membuat dua simpul tertentu menjadi takterhubung karena ada lintasan lain yang dapat dilalui. Hal ini kontradiksi dengan definisi jembatan. Jadi, pengandaian salah. Disimpulkan bahwa $e$ bukan sisi pembentuk siklus di $G.$
Arah kanan:
Misalkan $e$ bukan sisi pembentuk siklus di $G.$ Akan dibuktikan bahwa sisi $e$ dari graf $G$ merupakan jembatan.
Dengan menggunakan metode kontradiksi, andaikan sisi $e$ dari graf $G$ bukan jembatan. Ini berarti penghilangan sisi $e$ merupakan graf tetap terhubung. Dengan kata lain, ada lintasan yang berawal dan berakhir di simpul ujung $e,$ tetapi tidak melintasi sisi $e.$ Oleh karena itu, akan ada siklus di $G$ yang melintasi sisi $e.$ Hal ini kontradiksi dengan permisalan bahwa $e$ bukan sisi pembentuk siklus di $G.$ Jadi, pengandaian salah. Disimpulkan bahwasisi $e$ dari graf $G$ merupakan jembatan.
Dari sini, disimpulkan bahwa sisi $e$ dari suatu graf $G$ merupakan jembatan jika dan hanya jika $e$ bukan sisi pembentuk siklus di $G.$
$\blacksquare

[collapse]