Materi, Soal, dan Pembahasan – Keterhubungan Graf

Teori 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 e1,e2,,en di G sehingga terdapat suatu barisan simpul x0=u,x1,x2,,xn1,xn=v yang sisi ei-nya memiliki simpul ujung xi1 dan xi untuk i{1,2,,n}. 

Jika grafnya sederhana, kita menotasikan lintasan dengan menggunakan barisan simpul (x0,x1,,xn) (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 x1,x2,,xn1 atau melintasi (traverse) sisi e1,e2,,en. 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 H1 merupakan graf terhubung karena terdapat lintasan di antara setiap pasang simpul berbeda dari graf tersebut. Sebaliknya, graf H2 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 n2 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 v2 dan v3 terhubung kuat karena ada lintasan berarah (v2,v3) dan (v3,v4,v1,v2) yang menghubungkan dua simpul tersebut. Simpul v1 dan v5 terhubung lemah karena tidak terdapat lintasan berarah yang berawal dari v5 dan berakhir di v1. Lebih lanjut, vi(1i5) dan v6 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 vi dan vj 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 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

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 K1 tidak memuat lintasan Euler. Berbeda darinya, graf K2 dan K3 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.

Jika Anda ingin mencari soal latihan yang lebih banyak, Anda dapat mengakses ke folder soal mathcyber1997.com dengan mendaftar di bit.ly/Akses_SoalFolder 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.

No.Bahasa IndonesiaBahasa Inggris1.KeterhubunganConnectivity2.LintasanPath3.SirkuitCircuit4.SiklusCycle5.PanjangLength6.Melalui (Melewati)Pass Through7.MelintasiTraverse8.Graf TerhubungConnected Graph9.Graf TakterhubungDisconnected Graph10.Graf Terhubung LemahWeakly Connected Graph11.Graf Terhubung KuatStrongly Connected Graph12.KomponenComponent13.Lintasan EulerEulerian Path14.Jejak EulerEulerian Trail15.Siklus EulerEulerian Cycle16.Sirkuit EulerEulerian Circuit17.Graf Semi-EulerSemi-Eulerian Graph18.Graf EulerEulerian Graph19.Lintasan HamiltonHamiltonian Path20.Jejak HamiltonHamiltonian Trail21.Siklus HamiltonHamiltonian Cycle22.Sirkuit HamiltonHamiltonian Circuit23Graf Semi-HamiltonSemi-Hamiltonian Graph24.Graf HamiltonHamiltonian Graph25.DiameterDiameter


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

Bagian Uraian

Soal Nomor 1

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

Pembahasan

Soal Nomor 2

Jika G merupakan graf dengan derajat simpul minimum δ, maka G memuat lintasan dengan panjang δ.

Pembahasan

Soal Nomor 3

Misalkan G merupakan graf sederhana. Buktikan bahwa setidaknya salah satu di antara G atau G merupakan graf terhubung.

Pembahasan

Soal Nomor 4

Misalkan G=(V,E) merupakan graf sederhana dengan n simpul. Buktikan bahwa jika deg(v)12(n1) untuk setiap vV, maka G terhubung.

Pembahasan

Soal Nomor 5

Misalkan G=(V,E) merupakan graf dengan |V(G)|=n. Buktikan bahwa jika deg(u)+deg(v)n1 untuk setiap dua simpul yang tidak bertetangga u,vV(G), maka G terhubung dan diam(G)2.
Catatan: Diameter dari G, dinotasikan diam(G), merupakan jarak terjauh dari dua simpul sembarang di G.

Pembahasan

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