dasar-dasar teori graf - gunadarmasabri.staff.gunadarma.ac.id/downloads/files/71023/02...definisi...
TRANSCRIPT
Teori Graf (1)Matematika Informatika 4
Dr. Ahmad Sabri
Problem 7 Jembatan KΓΆnigsberg:
Adakah perjalanan yang melewati ketujuh jembatan tersebut tepat satukali dalam satu kali perjalanan?
Dr. Ahmad Sabri, Universitas Gunadarma 2
Abstraksi
Objek nyata Representasi graf
Keterangan:
= simpul (daratan)
= ruas (jembatan) Dr. Ahmad Sabri, Universitas Gunadarma 3
Definisi
Graf πΊ(π, πΊ) adalah struktur diskrit yang terdiri dari:
1. Himpunan π yang anggotanya adalah simpul-simpul π£1, π£2, β¦ , π£πpada graf πΊ
2. Himpunan πΈ yang anggotanya adalah pasangan tak-berurut π£ππ£π(disebut juga ruas) dengan ketentuan: π£ππ£π β πΈ jika terdapat ruasmenghubungkan π£π dengan π£π
Dr. Ahmad Sabri, Universitas Gunadarma 4
Representasi graf
β’ π = π£1, π£2, β¦ , π£5β’ πΈ = {π£1π£2, π£1π£4, π£1π£5, π£2π£3, π£2π£4, π£3π£4, π£4π£5}
π£1 π£2
π£3π£4π£5
Dr. Ahmad Sabri, Universitas Gunadarma 5
Definisi terkait keterhubungan pada graf
β’ Perjalanan (walk): barisan yang melalui simpul-ruas secarabergantian. Contoh: π£1π1π£2π7π£4π7π£2π2π£3
β’ Perjalanan terbuka (open walk): walk yang dimulai dan diakhiri oleh simpul yang berbeda. Contoh: π£1π1π£2π7π£4
β’ Perjalanan tertutup (closed walk): walk yang dimulai dan diakhiri oleh simpul yang sama. Contoh: π£1π1π£2π7π£4π3π£3π2π£2π7π£4π6π£1
β’ Lintasan (trail): perjalanan di mana semua ruasnya berbeda. Contoh: π£1π1π£2π7π£4π6π£1π5π£5π4π£4
β’ Jalur (path): perjalanan di mana semua simpulnya berbeda(dimungkinkan sama hanya untuk simpul pertama dan terakhir). Contoh: π£2π7π£4π3π£3, atau π£2π7π£4π3π£3π2π£2
β’ Sirkuit: jalur yang diawali dan diakhiri oleh simpul yang sama (closed path)
Catatan: terkadang perjalanan hanya ditulis simpul yang dilalui saja. Contoh: π£1π1π£2π7π£4π7π£2π2π£3 cukup ditulisπ£1π£2π£4π£2π£3
Dr. Ahmad Sabri, Universitas Gunadarma6
π£1 π£2
π£3π£4π£5
π2
π1
π3π4
π5 π7π6
β’ Derajat simpul: banyaknya ruas yang berpangkal di simpul tersebut. Contoh:pada πΊ2, deg π£1 = 3, deg π£2 = 2.
β’ Lintasan Euler: lintasan yang melewatisemua ruas pada graf tepat satu kali. Contoh: β’ pada πΊ1: π£1π£2π£3π£4π£1β’ pada πΊ2: π£1π£2π£3π£1π£4π£3β’ pada πΊ3 tidak ada
β’ Sirkuit Euler: lintasan Euler yang diawali dan diakhiri pada simpul yang sama. Contoh: β’ pada πΊ1: π£1π£2π£3π£4π£1β’ pada πΊ2 dan πΊ3: tidak ada
π£1 π£2
π£3π£4
π£1 π£2
π£3π£4
π£1 π£2
π£3π£4
πΊ1 πΊ2
πΊ3Dr. Ahmad Sabri, Universitas Gunadarma 7
Graf terhubung
Graf G dikatakan terhubung jika untuk sebarang dua simpul pada G selalu terdapat jalur yang menghubungkan keduanya.
8Dr. Ahmad Sabri, Universitas Gunadarma
π£1 π£2
π£3π£4π£5
π£1 π£2
π£3π£4π£5
Graf terhubung Graf tidak terhubung
β’ Euler membuktikan bahwa terdapat lintasan Euler pada grafterhubung jika banyaknya simpul berderajat ganjil adalah dua atautidak ada sama sekali.
β’ Graf Eulerian: graf terhubung yang memiliki sirkuit Euler
β’ Berdasarkan tabel, graf terhubung yang tidak memiliki simpulberderajat ganjil adalah Eulerian
Banyak simpul berderajatganjil
Ada lintasan euler? Ada sirkuit euler?
0 (tidak ada) Ya Ya
2 Ya Tidak
Selain 0 dan 2 Tidak Tidak
Dr. Ahmad Sabri, Universitas Gunadarma 9
1. Periksalah apakah terdapat lintasan euler dan sirkuit euler pada grafberikut.
2. Manakah yang eulerian?
10Dr. Ahmad Sabri, Universitas Gunadarma
πΊ1 πΊ2
πΊ3
Kembali ke 7 jembatan Konigsberg
Permasalahan 7 jembatan Konigsberg dapat dinyatakan sebagai: βapakah terdapat lintasan Euler pada graf berikut ini?β
Derajat = 3
Derajat = 3
Derajat = 3
Dr. Ahmad Sabri, Universitas Gunadarma 11
Jenis-jenis graf
Graf sederhana (simple) vs graf tidak sederhana (nonsimple)
β’ Graf sederhana: tidak berarah, tidak memiliki loop, tidak memilikiruas berganda
β’ Graf tidak sederhana: selain di atas
Dr. Ahmad Sabri, Universitas Gunadarma 14
Graf berarah (directed) vs graf tidak berarah (undirected)
β’ Graf berarah: ruas memiliki arah yang ditunjukkan oleh panah pada ruas
β’ Graf tidak berarah: tidak demikian
Dr. Ahmad Sabri, Universitas Gunadarma 15
Beberapa kelas graf
1. Graf linier (path) ππ
2. Graf lengkap (complete) πΎπ
3. Graf siklis (cyclic) πΆπ
4. Graf roda (wheel) ππ
π2 π3 π4 π5
Dr. Ahmad Sabri, Universitas Gunadarma 16
5. Graf kubus-π (π-cube) ππ
6. Graf bipartit π΅π,π
7. Graf bipartit lengkap πΎπ,π
πΎ3,2 πΎ2,5
Dr. Ahmad Sabri, Universitas Gunadarma 17
Graf Hamiltonian
β’ Jalur Hamiltonian: jalur yang melalui semua simpul tepat satu kali
β’ Siklus Hamiltonian: jalur Hamiltonian dengan yang diawali dan diakhiri oleh simpul yang sama
β’ Graf Hamiltonian: graf yang memuat siklus Hamiltoniane
20Dr. Ahmad Sabri, Universitas Gunadarma
Graf dodekahedron adalah Hamiltonian
21Dr. Ahmad Sabri, Universitas Gunadarma
β’ Siklus Hamiltonian atau jalur hamiltonian?
22Dr. Ahmad Sabri, Universitas Gunadarma
πΊ1
πΊ2 πΊ3
Pertanyaan latihan
1. Diberikan graf G berikut. Berapa ruas yang perlu ditambah agar graf G Eulerian?
2. Tentukan n sehingga graf lengkap Kn, n β₯ 2, adalah Eulerian
3. (Benar/Salah) Jika dua simpul terhubung oleh sebuah perjalanan (walk), makakedua simpul tersebut terhubung oleh sebuah path.
4. Apakah Graf Eulerian selalu Hamiltonian?
23Dr. Ahmad Sabri, Universitas Gunadarma