matematika diskrit bab11 teori graph.ppt ≠ vm untuk k ≠ m. sirkuit • sirkuit adalah jalur yang...

MATERI 10

Definisi Graf

• Diagram yang memuat informasi tertentu dandilambangkan dengan suatu keterhubunganantar titik.

• Menggambarkan berbagai macam strukturyang ada, misalnya: struktur organisasi, rutejalan, bagan alir pengambilan mata kuliah, danlain-lain.

• Tujuannya untuk menggambarkan obyek-obyek 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 dilambangkandengan E = E(G) = {e1, e2, ..., em}, yang berhinggadan 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 berarahdinamakan graf tak berarah (undirected graph). Contoh Gambar 8.1 (a), (b), (c)

• Graf yang semua ruasnya berarah dinamakangraf 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 kesimpul yang lain disebut graf lengkap(complete graph). Gambar 8.1 (b) merupakancontoh 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, …, v7dan 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, makaderajat simpul v yang dinyatakan dengan d(v ) adalah banyaknya ruas yang terhubung padasimpul tersebut.

• Simpul gelang mempunyai derajat 2.

Derajat Graf

• Derajat total G adalah jumlah derajatsemua simpul dalam G.

• Jumlah derajat semua simpul suatu grafadalah 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 simpuldan ruas G’ juga merupakan simpul dan ruasdalam G.

• Dengan kata lain jika G = (V, E) dan G’ = (V’, E’ ), maka G’ merupakan subgraf G jika danhanya 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’ dikatakanisomorfis dengan G (ditulis G ≈ G’ ) jika dan hanyajika terdapat korespondensi satu-satu sedemikiansehingga:– 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) ruasdengan vj’.

Contoh Isomorfisma

Contoh Isomorfisma

• Pasangan manakah yang isomorfisma?

Komplemen Graf

• Komplemen (complement) dari suatu grafsederhana G = (V, E ) adalah graf sederhanaH= (V, E ) dimana ruas-ruas di H secara tepatadalah 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 wdituliskan sebagai: v1, e1, v2, e2, ..., vn-1, en-1, vn, endengan v1 = u, vn = w, vj-i dan vi adalah simpul-simpul ujung ruas ei.

Trail (Tapak)

• Tapak merupakan lintasan dimana semuaruasnya berlainan (tidak diulang), sedangkansimpulnya boleh diulang.

• Tapak dengan panjang n dari simpul u ke wdituliskan 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 wdituliskan 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, ..., en-

1, 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 dapatdipisahkan menjadi dua himpunan V1 dan V2 yang saling asing, sedemikian sehingga jika x adalahruas dari G dan x menghubungkan suatu simpuldi V1 dengan simpul di V2. sedangkan simpul V1maupun V2 tidak ada yang berdekatan, maka Gdisebut graf bipartit.

• Apabila pada graf bipartit, setiap simpul di V1berhubungan dengan setiap simpul di V2, makagraf 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 tidakmempunyai 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.