MATERI 10
Definisi Graf • Diagram yang memuat informasi tertentu dan dilambangkan dengan suatu keterhubungan antar titik. • Menggambarkan berbagai macam struktur yang ada, misalnya: struktur organisasi, rute jalan, bagan alir pengambilan mata kuliah, dan lain-lain. • Tujuannya untuk menggambarkan obyekobyek agar lebih mudah dimengerti.
Komponen Graf • Himpunan simpul/verteks/titik/node yang dilambangkan dengan V = V(G) = {v1, v2, ..., vn}, yang berhingga dan tidak kosong. • Himpunan ruas/garis/edge yang dilambangkan dengan E = E(G) = {e1, e2, ..., em}, yang berhingga dan boleh kosong. • Setiap ruas menghubungkan dua simpul. • Suatu graf dinyatakan dengan G(V, E), dimana simpul dinyatakan dengan titik dan ruas dinyatakan dengan garis.
Contoh Graf
Gambar 8.1
Jenis Graf • Dua simpul dikatakan berdekatan (adjacent) jika terdapat ruas yang menghubungkan langsung kedua simpul tersebut. Setiap ruas merupakan 2 himpunan bagian dari himpunan semua simpul. • Graf yang tidak mempunyai ruas dinamakan graf kosong (null graph). Gambar 8.1 (f) merupakan contoh graf kosong.
Jenis Graf • Graf yang mempunyai simpul yang dihubungkan dengan lebih dari satu ruas dinamakan multiple graph (multigraph)., sedangkan Gambar 8.1 (e) merupakan contoh multigraph.
Jenis Graf • Graf yang semua ruasnya tidak berarah dinamakan graf tak berarah (undirected graph). Contoh Gambar 8.1 (a), (b), (c) • Graf yang semua ruasnya berarah dinamakan graf berarah (directed graph atau digraph). Contoh Gambar 8.1 (d), (e). • Dalam bab ini, jika hanya disebutkan graf saja, maka yang dimaksud adalah graf tak berarah.
Jenis Graf • Graf yang setiap simpulnya dihubungkan ke simpul yang lain disebut graf lengkap (complete graph). Gambar 8.1 (b) merupakan contoh graf lengkap.
Jenis Graf • Graf yang tidak mempunyai gelang atau ruas ganda dinamakan graf sederhana (simple graph). – (a), (b), (d), merupakan contoh graf sederhana.
• Graf yang mempunyai gelang atau ruas ganda dinamakan graf tidak sederhana (unsimple graph). – (c), (e) merupakan contoh graf tidak sederhana.
Graf • Graf G mempunyai 7 simpul, yaitu v1, v2, …, v7 dan 10 ruas, yaitu e1, e2, …, e10. • Ruas-ruas pada graf G dinyatakan oleh: e1 = {v1, v5}, e2 = {v1, v2}, e3 = {v2, v6}, e4 = {v2, v3}, e5 = {v3, v6}, e6 = {v3, v4}, e7 = {v4, v7}, e8 = {v4, v5}, e9 = {v4, v5}, e10 = {v5, v5}.
Graf • Ruas yang mempunyai simpul ujung sama dinamakan ruas ganda (parallel edges atau multiple edges). – Ruas ganda adalah e8 dan e9.
• Jika suatu ruas menghubungkan simpul yang sama, maka ruas tersebut dinamakan gelang (loop). – Gelang adalah e10.
Graf • Titik yang tidak mempunyai garis yang berhubungan dengannya disebut titik terasing (isolating point). – Titik terasing adalah v7.
Derajat Graf • Banyaknya simpul dalam graf disebut order, dinyatakan dengan |V |. • Banyaknya ruas dalam graf disebut size, dinyatakan dengan |E |. • Jika v adalah suatu simpul dalam graf G, maka derajat simpul v yang dinyatakan dengan d(v ) adalah banyaknya ruas yang terhubung pada simpul tersebut. • Simpul gelang mempunyai derajat 2.
Derajat Graf • Derajat total G adalah jumlah derajat semua simpul dalam G. • Jumlah derajat semua simpul suatu graf adalah dua kali banyaknya ruas graf, karena setiap ruas dihitung dua kali.
Derajat Graf • Berapakah jumlah simpul dan ruas dari graf tersebut? • Berapakah derajat masing-masing simpulnya? • Berapa derajat totalnya?
Subgraf • Graf G’ dikatakan subgraf G jika semua simpul dan ruas G’ juga merupakan simpul dan ruas dalam G. • Dengan kata lain jika G = (V, E) dan G’ = (V’, E’ ), maka G’ merupakan subgraf G jika dan hanya jika V’ himpunan bagian V dan E’ himpunan bagian E.
Contoh Subgraf
Isomorfisma • Konsep isomorfisma sama dengan konsep kongruen dalam geometri. • Dua graf disebut isomorfis jika keduanya menunjukkan "bentuk" yang sama. • Kedua graf hanya berbeda dalam hal pemberian label titik dan garisnya saja.
Isomorfisma • Jika G = (V, E } dan G’ = (V’, E’ ), maka G’ dikatakan isomorfis dengan G (ditulis G ≈ G’ ) jika dan hanya jika terdapat korespondensi satu-satu sedemikian sehingga: – Setiap simpul di G’ mempunyai tepat satu nama. – (vi, vj) ∈ G jika dan hanya jika (vi’, vj’) ∈ G’ – vi dihubungkan oleh k (k > 1) ruas dengan vj jika dan hanya jika vi’ dihubungkan oleh k (k > 1) ruas dengan vj’.
Contoh Isomorfisma
Contoh Isomorfisma • Pasangan manakah yang isomorfisma?
Komplemen Graf • Komplemen (complement) dari suatu graf sederhana G = (V, E ) adalah graf sederhana H= (V, E ) dimana ruas-ruas di H secara tepat adalah ruas-ruas yang tidak ada di G.
Contoh Komplemen Graf
Contoh Komplemen Graf • Bagaimana komplemennya?
Walk (Lintasan) • Lintasan adalah urutan simpul dan ruas yang bergantian tidak kosong dan berhingga yang dimulai dan diakhiri dengan simpul, dimana setiap ruas menghubungkan dua simpul (sebelum dan sesudah ruas tersebut). Dalam lintasan, simpul dan ruas bisa diulang. • Lintasan dengan panjang n dari simpul u ke w dituliskan sebagai: v1, e1, v2, e2, ..., vn-1, en-1, vn, en dengan v1 = u, vn = w, vj-i dan vi adalah simpulsimpul ujung ruas ei.
Trail (Tapak) • Tapak merupakan lintasan dimana semua ruasnya berlainan (tidak diulang), sedangkan simpulnya boleh diulang. • Tapak dengan panjang n dari simpul u ke w dituliskan sebagai: v1, e1, v2, e2, ..., vn-1, en-1, vn, en dengan v1 = u, vn = w, ei ≠ ej untuk i ≠ j.
Path (Jalur) • Jalur merupakan tapak dimana semua simpulnya berlainan, kecuali jika jalur tersebut merupakan jalur tertutup sehingga simpul awal sama dengan simpul akhir. • Jalur dengan panjang n dari simpul u ke w dituliskan sebagai: v1, e1, v2, e2, ..., en-1, vn-1, en, vn dengan v1 = u, vn = w, ei ≠ ej untuk i ≠ j dan vk ≠ vm untuk k ≠ m.
Sirkuit • Sirkuit adalah jalur yang tertutup. • Sirkuit dengan panjang n dari simpul u kembali ke u lagi dituliskan sebagai: v1, e1, v2, e2, ..., en1, vn-1, en, vn dengan v1 = vn = u, ei ≠ ej untuk i ≠ j dan vk ≠ vm untuk k ≠ m.
Contoh • Cari beberapa walk, trail, path, sirkuitnya
Graf Bipartite • Suatu graf G yang simpul-simpulnya dapat dipisahkan menjadi dua himpunan V1 dan V2 yang saling asing, sedemikian sehingga jika x adalah ruas dari G dan x menghubungkan suatu simpul di V1 dengan simpul di V2. sedangkan simpul V1 maupun V2 tidak ada yang berdekatan, maka G disebut graf bipartit. • Apabila pada graf bipartit, setiap simpul di V1 berhubungan dengan setiap simpul di V2, maka graf tersebut disebut graf bipartit lengkap.
Contoh Graf Bipartite
Contoh Graf Bipartite • Tentukan graf berikut merupakan graf bipartit tidak lengkap, graf bipartit lengkap, atau bukan graf bipartit
Pohon • Pohon merupakan graf tak berarah yang tidak mempunyai sirkuit dan terhubung, yang merupakan salah satu contoh graf planar. • Sifat-sifat pohon : – Setiap pasang simpul di dalam graf G terhubung dengan lintasan tunggal. – Graf G mempunyai (n-1) buah ruas.
Contoh Pohon dan Bukan Pohon • Gambar 8.17 (a), (b), (c), (d) merupakan pohon karena graf tersebut terhubung dan tidak mempunyai sirkuit. • Gambar 8.17 (e) bukan merupakan pohon karena dari graf tersebut dapat dibentuk sirkuit. • Gambar 8.17 (f) bukan merupakan pohon karena graf tersebut tidak terhubung.
