Tag: Graf Euler

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

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.

Jika Anda ingin mencari soal latihan yang lebih banyak, Anda dapat mengakses ke folder soal mathcyber1997.com dengan mendaftar di bit.ly/Akses_Soal. Folder soal tersebut berisi soal UTBK-SNBT, soal persiapan CPNS-PPPK, soal psikotes, soal TPA, soal ujian masuk perguruan tinggi (termasuk STAN), soal kompetensi matematika (termasuk OSN dan ON MIPA), dan masih banyak lagi.

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.

$$\overline{)\begin{array}{ccc}\text{No.}& \text{Bahasa Indonesia}& \text{Bahasa Inggris}\\ 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}\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)$

Bagian Uraian

Soal Nomor 1

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

Soal Nomor 2

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

Soal Nomor 3

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

Soal Nomor 4

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

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

Soal Nomor 6

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