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
Berikut ini merupakan beberapa artikel yang tersedia terkait dengan materi graf.
Materi, Soal, dan Pembahasan – Dasar-Dasar Graf dan Terminologinya
Materi, Soal, dan Pembahasan – Operasi pada Graf dan Konsep Subgraf
Materi, Soal, dan Pembahasan – Representasi Graf dan Isomorfisme Graf
Definisi: Lintasan
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
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
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
Berikutnya, kita akan mendefinisikan terminologi lain dari graf terhubung.
Definisi: Komponen
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 diskret 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
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
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
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
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
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)$
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)
Bagian Uraian
Soal Nomor 1
Dengan menggunakan lintasan, tunjukkan bahwa dua graf berikut tidak isomorfis.
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.
Soal Nomor 2
Jika $G$ merupakan graf dengan derajat simpul minimum $\delta,$ maka $G$ memuat lintasan dengan panjang $\delta.$
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 kontradiktif 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$
Soal Nomor 3
Misalkan $G$ merupakan graf sederhana. Buktikan bahwa setidaknya salah satu di antara $G$ atau $\overline{G}$ merupakan graf terhubung.
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.
- 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}.$
- 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$
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.
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 kontradiktif dengan fakta bahwa $G$ hanya memiliki $n$ simpul. Jadi, pengandaian salah. Disimpulkan bahwa $G$ terhubung. $\blacksquare$
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.$
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$
Soal Nomor 6
Buktikan bahwa sisi $e$ dari suatu graf $G$ merupakan jembatan jika dan hanya jika $e$ bukan sisi pembentuk siklus di $G.$
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 kontradiktif 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 kontradiktif dengan permisalan bahwa $e$ bukan sisi pembentuk siklus di $G.$ Jadi, pengandaian salah. Disimpulkan bahwa sisi $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