Teori Graf: Konsep Dasar
Teori graf merupakan pokok bahasan yang sudah tua usianya namun memiliki banyak terapan sampai saat ini. Graf digunakan untuk merepresentasikan objek-objek diskrit dan hubungan antara objek-objek tersebut. Representasi visual dari graf adalah dengan menyatakan objek dinyatakan sebagai noktah, bulatan, atau titik, sedangkan hubungan antara objek dinyatakan dengan garis.
1. Masalah Jembatan Königsberg
Masalah Jembatan Königsberg, yang pertama kali menggunakan konsep graf pada tahun 1736, melibatkan tujuh jembatan di kota Königsberg (sekarang Kaliningrad). Pertanyaannya adalah apakah mungkin melewati ketujuh jembatan tersebut masing-masing satu kali dan kembali ke titik awal.
Leonhard Euler, seorang matematikawan Swiss, memecahkan masalah ini dengan memodelkannya sebagai graf: daratan sebagai titik (vertex) dan jembatan sebagai sisi (edge). Ia menyimpulkan bahwa perjalanan tersebut tidak mungkin dilakukan jika derajat (jumlah garis yang bersisian dengan sebuah noktah/titik) setiap titik tidak seluruhnya genap.
Lebih lanjut, jika tidak semua titik berderajat genap, maka tidak mungkin ada sirkuit Euler (perjalanan yang melewati setiap sisi tepat satu kali dan kembali ke titik awal). Contohnya, titik C berderajat 3, titik B dan D berderajat 2, dan titik A berderajat 5. Konsep derajat dan sirkuit ini akan dibahas lebih mendalam.
2. Definisi dan Terminologi Graf
A. Definisi
Definisi: Graf G didefinisikan sebagai pasangan himpunan (V, E), ditulis dengan notasi G = (V, E), yang dalam hal ini V adalah himpunan tak kosong dari titik-titik atau simpul (vertices atau node) dan E adalah himpunan sisi (edges atau arcs) yang menghubungkan sepasang titik.
Catatan:
Definisi ini menyatakan bahwa V tidak boleh kosong, sedangkan E boleh kosong. Jadi, sebuah graf dimungkinkan tidak mempunyai sisi satu buah pun, tetapi titiknya harus ada, minimal satu. Graf yang hanya mempunyai satu buah titik tanpa sebuah sisi pun dinamakan graf trivial.
B. Penyimbolan
titik pada graf dapat dinamai dengan huruf A, a, B, b; angka 1, 2, 3; atau huruf berindeks v₁, v₂, v₃. Sedangkan sisi e yang menghubungkan titik u dengan titik v dinyatakan dengan pasangan (u, v), dituliskan e = (u, v); atau dinyatakan dengan lambang berindeks e₁, e₂, e₃.
C. Visualisasi
Secara visual graf digambarkan sebagai sekumpulan noktah (titik) di dalam bidang dwimatra yang dihubungkan dengan sekumpulan garis (sisi).
D. Terminologi
• Setiap elemen e dalam E(G) merupakan sebuah diploid (pasangan tak berurutan) dari titik-titik di V(G).
• Setiap sisi menghubungkan satu titik ke titik lain (boleh titik yang sama), dan titik itu sebagai titik ujung (endpoint) dari sisi.
• Ordo (order) suatu graf menyatakan banyaknya titik pada graf.
• Ukuran (size) suatu graf menyatakan banyaknya sisi pada graf.
• Kardinalitas (cardinality) suatu graf ditentukan oleh ordo (banyak titik) graf.
• Loop atau gelang adalah sebuah sisi yang berawal dan berakhir pada titik yang sama.
• Link adalah sebuah sisi yang berawal dan berakhir pada titik yang berbeda.
• Sisi Rangkap (multiple edge / parallel edge) adalah dua sisi yang mempunyai dua titik ujung yang sama.
• Graf yang tidak memiliki sisi loop dan sisi parallel disebut graf sederhana.
• Titik terisolasi adalah suatu titik yang bukan merupakan titik ujung dari sisi manapun.
• Titik ujung dari sebuah sisi disebut incident terhadap sisi.
• Dua buah titik yang incident terhadap sisi yang sama, dengan kata lain dua titik yang terhubung oleh sebuah sisi disebut titik-titik yang adjacent.
Contoh:
Misalkan diberikan graf G terdiri dari himpunan titik V dan himpunan sisi E dengan
V = {v₁, v₂, v₃, v₄, v₅}, E = {e₁, e₂, e₃, e₄, e₅, e₆, e₇, e₈}, dimana
e₁ = (v₁, v₂), e₂ = (v₂, v₃), e₃ = (v₃, v₃), e₄ = (v₃, v₄), e₅ = (v₂, v₄), e₆ = (v₄, v₅), e₇ = (v₂, v₅), e₈ = (v₂, v₅).
a. Gambarkan graf tersebut!
Graf pada poin (a) memiliki 5 titik dan 8 sisi.
Graf ini memiliki loop, yaitu e₃ yang mana kedua titik ujungnya sama, yaitu v₃.
Graf ini memiliki sisi rangkap, yaitu e₇ dan e₈, yang mana keduanya menghubungkan titik-titik yang sama, yaitu v₂ dan v₅.
3. Jenis-Jenis Graf
A. Jenis-jenis graf berdasarkan keberhinggaan titik
• Graf tak hingga
Graf dengan himpunan dari tak berhingga titik atau tak berhingga sisi disebut graf tak hingga.
• Graf hingga
Graf dengan berhingga titik dan berhingga sisi disebut graf hingga.
B. Jenis-jenis graf berdasarkan ada atau tidaknya loop atau sisi rangkap
• Graf sederhana (simple graph)
Graf sederhana adalah graf yang tidak memiliki loop dan sisi rangkap.
• Graf tidak sederhana (unsimple graph)
Graf tidak sederhana adalah graf yang memiliki loop atau sisi rangkap. Graf yang memiliki sisi rangkap disebut graf ganda (multigraph), sedangkan graf yang memiliki loop disebut graf semu (pseudograph).
C. Jenis-jenis graf berdasarkan keterarahan sisi
• Graf tak berarah (undirected graph)
Graf yang sisinya tidak mempunyai orientasi arah disebut graf tak-berarah. Pada graf tak-berarah, urutan pasangan titik yang dihubungkan oleh sisi tidak diperhatikan. Jadi, (u, v) = (v, u) adalah sisi yang sama.
• Graf berarah (directed graph)
Graf yang setiap sisinya diberikan orientasi arah disebut sebagai graf berarah. Kita lebih suka menyebut sisi berarah dengan sebutan busur (arc). Pada graf berarah, (u, v) dan (v, u) menyatakan dua buah busur yang berbeda, dengan kata lain (u, v) ≠ (v, u). Untuk busur (u, v), titik u dinamakan titik asal (initial vertex) dan titik v dinamakan titik terminal (terminal vertex). Graf berarah sering dipakai untuk menggambarkan aliran proses, peta lalu lintas suatu kota (jalan searah atau dua arah), dan sebagainya. Pada graf berarah sederhana, loop diperbolehkan, tetapi sisi rangkap tidak.
Berikut ini tabel jenis-jenis graf:
|
Jenis |
Sisi |
Sisi rangkap diperbolehkan ? |
Loop diperbolehkan ? |
|
Graf sederhana |
tidak berarah |
tidak |
tidak |
|
Graf ganda |
tidak berarah |
ya |
tidak |
|
Graf semu |
tidak berarah |
ya |
ya |
|
Graf berarah sederhana |
berarah |
tidak |
tidak |
|
Graf berarah ganda |
berarah |
ya |
ya |
|
Graf campuran |
berarah dan tidak berarah |
ya |
ya |
4. Lebih Lanjut Terminologi
A. Bertetangga / Bersebelahan (Neighbor / Adjacent) dan Bersisian (Incident)
Dua titik u dan v pada suatu graf tak berarah G disebut bersebelahan (bertetangga) jika u dan v adalah titik ujung dari suatu sisi e dari G. Sisi e yang demikian disebut bersisian dengan titik u dan v, dan dikatakan e menghubungkan u dan v.
Pada graf berarah, sisi kita sebut busur. Jika (u, v) adalah busur maka u dikatakan bertetangga dengan v dan v dikatakan tetangga dari u.
B. Lingkungan (Neighborhood)
Himpunan semua tetangga dari titik v pada graf G = (V, E), ditulis N(v), disebut lingkungan (neighborhood) dari v. Jika A ⊆ V, notasi N(A) menyatakan himpunan semua titik pada graf G yang bertetangga dengan setidaknya satu titik di A.
C. Titik Terpencil / Terisolasi (Isolated Vertex)
Titik terpencil adalah titik yang tidak ada sisi yang incident dengannya. Dapat juga dinyatakan titik terpencil adalah titik yang tidak ada titik yang adjacent dengannya.
D. Graf Kosong (Null Graph / Empty Graph)
Graf kosong adalah graf yang tidak memiliki sisi. Dapat juga dinyatakan bahwa graf kosong adalah graf yang semua tititknya terisolasi.
Suatu graf kosong yang memiliki n-titik dinotasikan dengan Nₙ.
5. Derajat Titik (Degree of Vertex)
A. Derajat titik graf tidak berarah
Derajat dari suatu titik pada graf tak berarah adalah banyaknya sisi yang bersisian dengannya, kecuali untuk loop pada titik tersebut menyumbang 2 derajat titik tersebut. Derajat dari titik v dinotasikan dengan deg(v).
Alasan mengapa loop mengkontribusikan dua untuk derajat titiknya adalah karena loop direpresentasikan sebagai (v, v), dan titik v bersisian dua kali pada sisi (v, v).
Titik terisolasi berderajat nol.
Titik yang berderajat satu disebut anting (pendant vertex). Dengan kata lain, anting-anting hanya bertetangga dengan sebuah titik.
Misal v merupakan titik pada graf G. Hubungan antara derajat titik dan banyak anggota lingkungan adalah |N(v)| ≤ deg(v), lebih khusus lagi N(v) = deg(v) jika dan hanya jika G graf sederhana.
Contoh:
1. Perhatikan graf berikut:
deg(a) = 2, N(a) = {b, f}
deg(b) = 4, N(b) = {a, c, e, f}
deg(c) = 4, N(c) = {b, d, e, f}
deg(d) = 1, N(d) = {c}
deg(e) = 3, N(e) = {b, c, f}
deg(f) = 4, N(f) = {a, b, c, e}
deg(g) = 0, N(g) = ∅
2. Perhatikan graf berikut:
Pada graf ini titik c merupakan anting. Berikut ini derajat masing-masing titik dan lingkungannya:
deg(a) = 4, N(a) = {b, d, e}
deg(a) = 4, N(a) = {b, d, e}
deg(b) = 6, N(b) = {a, b, c, d, e}
deg(c) = 1, N(c) = {b}
deg(d) = 5, N(d) = {a, b, e}
deg(e) = 6, N(e) = {a, b, d}
B. Derajat graf berarah
Pada graf berarah, derajat titik v dinyatakan dengan dᵢₙ(v) dan dₒᵤₜ(v), yang dalam hal ini
dᵢₙ(v) = derajat-masuk (in-degree) = banyak busur yang masuk ke titik v
dₒᵤₜ(v) = derajat-keluar (out-degree) = banyak busur yang keluar dari titik v
deg(v) = dᵢₙ(v) + dₒᵤₜ(v)
Catatan:
• Sisi loop menyumbangkan 1 derajat masuk dan 1 derajat keluar.
• Jumlah semua derajat masuk sama dengan jumlah semua derajat keluar, karena setiap sisi memiliki 1 titik masuk dan 1 titik keluar.
Contoh: perhatikan graf berikut
dᵢₙ(a) = 2, dₒᵤₜ(a) = 4
dᵢₙ(b) = 2, dₒᵤₜ(b) = 1
dᵢₙ(c) = 3, dₒᵤₜ(c) = 2
dᵢₙ(d) = 2, dₒᵤₜ(d) = 2
dᵢₙ(e) = 3, dₒᵤₜ(e) = 3
dᵢₙ(f) = 0, dₒᵤₜ(f) = 0
C. Lemma jabat tangan
"Jumlah derajat semua titik selalu genap, yaitu sama dengan dua kali banyak sisi."
Lemma ini dikenal dengan lemma jabat tangan (handshaking lemma). Hal ini disebabkan oleh setiap sisi dihitung dua kali, yaitu pada ujung kiri sebagai bagian dari titik kiri dan pada ujung kanan dihitung sebagai bagian dari titik kanan. Layaknya orang berjabat tangan, maka banyak tangan yang berjabat adalah genap dan banyak tangan yang berjabat adalah dua kali banyak jabatan tangan yang terjadi. Lemma Jabat Tangan juga benar untuk graf berarah, yang dalam hal ini deg(v) = dᵢₙ(v) + dₒᵤₜ(v).
D. Akibat lemma jabat tangan
"Banyak titik berderajat ganjil selalu genap."
Hal ini berlaku karena hasil penjumlahan bilangan-bilangan genap selalu genap, sedangkan hasil penjumlahan bilangan-bilangan ganjil sesuai dengan banyaknya bilangan ganjil. Agar jumlah akhir genap, diharuskan banyak bilangan ganjil adalah genap.
6. Kunjungan Graf (Visiting Graph)
A. Lintasan (Path)
Lintasan yang panjangnya n dari titik awal v₀ ke titik tujuan vₙ di dalam graf G ialah barisan berselang-seling titik-titik dan sisi-sisi yang berbentuk v₀, e₁, v₁, e₂, v₂, ..., vₙ₋₁, eₙ, vₙ, sedemikian sehingga e₁ = (v₀, v₁), e₂ = (v₁, v₂), ..., eₙ = (vₙ₋₁, vₙ) adalah sisi-sisi dari graf G.
Jika graf yang ditinjau adalah graf sederhana, maka kita cukup menuliskan lintasan sebagai barisan titik-titik saja: v₀, v₁, v₂, ..., vₙ₋₁, vₙ, karena antara dua buah titik berturutan di dalam lintasan tersebut hanya ada satu sisi.
Pada graf yang mengandung sisi rangkap, kita harus menulis lintasan sebagai barisan berselang-seling antara titik dan sisi menghindari kerancuan sisi mana dari sisi-sisi ganda yang dilalui.
Titik dan sisi yang dilalui di dalam lintasan boleh berulang. Sebuah lintasan dikatakan lintasan sederhana (simple path) jika semua sisinya berbeda (setiap sisi yang dilalui hanya satu kali).
Lintasan yang berawal dan berakhir pada titik yang sama disebut lintasan tertutup (closed path), sedangkan lintasan yang tidak berawal dan berakhir pada titik yang sama disebut lintasan terbuka (open path).
B. Siklus (Cycle) atau Sirkuit (Circuit)
Lintasan yang berawal dan berakhir pada titik yang sama disebut siklus atau sirkuit. Dengan kata lain, siklus atau sirkuit ini merupakan nama lain dari lintasan tertutup.
Sirkuit yang setiap sisinya berbeda disebut sirkuit sederhana (simple circuit).
C. Jalan (Walk) dan Jejak (Trail)
Jalan (walk) merupakan nama lain dari lintasan.
Jejak (trail) merupakan nama lain dari lintasan sederhana.
7. Keterhubungan Graf (Connection of Graph)
Dua buah titik u dan v dikatakan terhubung jika terdapat lintasan dari u ke v. Jika dua buah titik terhubung maka pasti titik yang pertama dapat dicapai dari titik yang kedua. Dua titik terminal pada jaringan komputer hanya dapat berkomunikasi bila keduanya terhubung. Jika setiap pasang titik di dalam graf terhubung, maka graf tersebut kita katakan graf terhubung.
A. Keterhubungan graf tak berarah
Graf tak-berarah G disebut graf terhubung (connected graph) jika untuk setiap pasang titik u dan v di dalam himpunan V terdapat lintasan dari u ke v (yang juga harus berarti ada lintasan dari v ke u). Jika tidak, maka G disebut graf tak-terhubung (disconnected graph).
Sebagai catatan, graf yang hanya terdiri atas satu titik saja (tidak ada sisi) tetap kita katakan terhubung, karena titik tunggalnya terhubung dengan diringan sendiri, juga dikatakan graf terhubung.
Teorema: "Terdapat lintasan sederhana diantara setiap pasang titik yang berbeda pada suatu
graf tak berarah yang terhubung".
Berikut ini contoh graf tidak terhubung:
B. Keterhubungan graf berarah
Graf berarah G dikatakan terhubung jika graf tak-berarahnya terhubung (graf tak-berarah dari G diperoleh dengan menghilangkan arahnya).
Keterhubungan dua buah titik pada graf berarah dibedakan menjadi terhubung kuat dan terhubung lemah.
Dua titik, u dan v pada graf berarah G disebut terhubung kuat (strongly connected) jika terdapat lintasan berarah dari u ke v, dan juga sebaliknya lintasan berarah dari v ke u.
Jika u dan v tidak terhubung kuat tetapi tetap terhubung pada graf tak-berarahnya, maka u dan v dikatakan terhubung lemah (weakly connected).
C. Graf berarah terhubung kuat dan terhubung lemah
Graf berarah G disebut graf terhubung kuat (strongly connected graph) apabila untuk setiap pasang titik sembarang vᵢ dan vⱼ di G terhubung kuat. Kalau tidak, G disebut graf terhubung lemah.
berikut ini contoh graf berarah terhubung:
8. Subgraf
A. Subgraf dan komplemennya
Misal diberikan graf G = (V, E). Suatu graf G₁ = (V₁, E₁) dikatakan subgraf dari G jika V₁ ⊆ V dan E₁ ⊆ E. Sebaliknya, G merupakan supergraf dari G₁.
Sedangkan graf G₂ = (V₂, E₂) dikatakan komplemen subgraf dari G₁ terhadap G jika E₂ = E\E₁ dan titik-titik di V₂ merupakan titik-titik yang incident dengan sisi-sisi di E₂.
Perhatikan gambar berikut:
B. Komponen terhubung
Jika graf tidak terhubung, maka graf tersebut terdiri atas beberapa komponen terhubung (connected component). Komponen terhubung (atau disebut "Komponen" saja) dari suatu graf G adalah suatu subgraf terhubung dari G yang bukan subgraf sejati dari subgraf terhubung lainnya dari G. Komponen terhubung dari suatu graf G adalah subgraf terhubung maksimal dari G. Suatu graf G yang tidak terhubung memiliki dua atau lebih komponen terhubung yang saling lepas (tidak beririsan) dan memiliki G sebagai gabungannya. Oleh karena itu, komponen-komponen dari graf tidak terhubung membentuk partisi.
Sedangkan graf terhubung hanya terdiri dari satu komponen, yaitu graf itu sendiri.
Sebagai contoh, perhatikan gambar berikut:
C. Komponen terhubung kuat
Pada graf berarah, komponen terhubung kuat (strongly connected component) adalah subgraf terhubung kuat dari graf G yang tidak terdapat di dalam subgraf terhubung kuat dari G yang lebih besar.
Sebagai contoh, perhatikan gambar berikut:
D. Subgraf merentang (spanning subgraph)
Misal diberikan graf G = (V, E). Suatu graf G₁ = (V₁, E₁) dikatakan subgraf merentang dari G jika V₁ = V dan E₁ ⊆ E.
Perhatikan gambar berikut:
E. Jembatan (bridge) atau cut-set
Terkadang membuang dari suatu graf suatu titik dan semua sisi yang bersisian dengannya menghasilkan subgraf dengan dengan komponen terhubung. Titik yang demikian disebut titik potong (titik artikulasi). Membuang suatu titik potong dari suatu graf terhubung menghasilkan subgraf yang tidak terhubung. Analog dengan itu, suatu sisi yang jika dibuang menghasilkan graf dengan lebih banyak komponen terhubung daripada graf aslinya di sebut sisi potong atau jembatan.
Cut-set dari graf terhubung G adalah himpunan sisi yang bila dibuang dari G menyebabkan G tidak terhubung. Jadi, cut-set selalu menghasilkan dua buah komponen terhubung.
Nama lain untuk cut-set adalah jembatan (bridge). Jembatan adalah himpunan sisi yang apabila dibuang dari graf menyebabkan graf tersebut tidak terhubung (menjadi dua buah komponen terhubung). Yang harus diingat, di dalam cut-set tidak boleh mengandung himpunan bagian yang juga cut set, sehingga cut-set yang dimaksudkan adalah fundamental cut-set.
Cut-set berperan besar dalam jaringan komunikasi dan transportasi.
9. Graf Berbobot
Graf berbobot adalah graf yang setiap sisinya diberi sebuah harga (bobot).
Bobot pada tiap sisi dapat berbeda-beda bergantung pada masalah yang dimodelkan dengan graf. Bobot dapat menyatakan jarak antara dua buah kota, biaya perjalanan antara dua buah kota, waktu tempuh pesan (message) dari sebuah titik komunikasi ke titik komunikasi lain (dalam jaringan komputer), ongkos produksi, dan sebagainya.
Istilah lain yang sering dikaitkan dengan graf berbobot adalah graf berlabel. Namun graf berlabel sesungguhnya lebih luas lagi definisinya. Label tidak hanya diberikan pada sisi, tetapi juga pada titik. Sisi diberi label berupa bilangan tak-negatif, sedangkan titik diberi label berupa data lain. Misalnya pada graf yang memodelkan kota-kota, titik diberi nama kota-kota, sedangkan label pada sisi menyatakan jarak antara kota-kota.
10. Revisi Graf
A. Menghapus dan menambahkan sisi
Diberikan graf G = (V, E) dan sisi e ∈ E, kita dapat menghasilkan graf bagian dari G dengan menghapus e. Graf bagian yang dihasilkan, ditulis dengan G − e, memiliki himpunan titik yang sama dengan V pada G dan himpunan sisi E\{e}. Sehingga G − e = (V, E\{e}).
Jika E′ ⊆ E, kita dapat menghasilkan graf bagian dari G dengan menghapus sisi-sisi pada E′ dari graf. Graf yang dihasilkan memiliki himpunan titik yang sama dengan V pada G. Himpunan sisinya adalah E \ E′.
Kita juga dapat menambahkan suatu sisi e untuk menambahkan graf yang lebih besar jika sisi ini menghubungkan dua titik pada G. Kita notasikasikan G + e sebagai graf baru yang dihasilkan dengan menambahkan sisi baru e menghubungkan dua titik yang sebelumnya tidak bersisian pada graf G, sehingga G + e = (V, E ∪{e}).
B. Kontraksi sisi
Terkadang ketika kita membuang sisi dari suatu graf, kita tidak ingin meninggalkan titik ujung sebagai titik-titik yang terpisah pada graf bagian baru yang dihasilkan. Dalam kasus ini kita bisa melakukan kontraksi sisi dengan cara:
• menghapus sisi dengan titik ujung u dan v
• menggabungkan u dan v menjadi satu titik w
• setiap sisi dengan u dan v sebagai titik ujung diganti dengan sisi dengan w sebagai suatu titik ujung dan titik ujung yang keduanya tetap sama
Sehingga kontraksi sisi e dengan titik ujung u dan v pada graf G = (V, E) menghasilkan graf G' = (V', E'), yang bukan merupakan graf bagian dari G, dengan V' = V \ {u, v} ∪ {w} dan E' adalah sisi-sisi di E yang tidak memiliki u atau v sebagai titik ujung dan diganti dengan sisi yang menghubungkan w dengan setiap lingkungan dari u atau v di V.
C. Menghapus titik
Jika kita menghapus titik v dan semua sisi yang bersisian dengan v dari graf G = (V, E), kita menghasilkan graf bagian yang baru, yang dinotasikan dengan G − v. Perhatikan bahwa G − v = (V \ {v}, E'), dimana E' adalah himpunan dari sisi-sisi di G yang tidak bersisian dengan v.
Jika V' ⊆ V, kita dapat menghasilkan graf bagian dari G dengan menghapus titik-titik pada V' dari graf G. Graf yang dihasilkan memiliki himpunan titik V \ V' dan himpunan sisinya adalah E' dengan E' adalah himpunan dari sisi-sisi di G yang tidak bersisian dengan simpul pada V'.
11. Gabungan dan Irisan Graf
A. Gabungan graf (graph union)
Gabungan dari graf sederhana G₁ = (V₁, E₁) dan G₂ = (V₂, E₂) adalah suatu graf sederhana dengan himpunan titik V₁ ∪ V₂ dan himpunan sisi E₁ ∪ E₂, dinotasikan dengan G₁ ∪ G₂.
B. Irisan graf (graph intersection)
Irisan dari graf sederhana G₁ = (V₁, E₁) dan G₂ = (V₂, E₂) adalah suatu graf sederhana dengan himpunan titik V₁ ∩ V₂ dan himpunan sisi E₁ ∩ E₂, dinotasikan dengan G₁ ∩ G₂.
Komentar
Posting Komentar