dasar-dasar teori graf (3)sabri.staff.gunadarma.ac.id/.../03+dasar+teori+graf.pdf · • pada graf...

29
Dasar-dasar Teori Graf (3) Dr. Ahmad Sabri Universitas Gunadarma

Upload: others

Post on 06-Jan-2020

24 views

Category:

Documents


0 download

TRANSCRIPT

Page 1: Dasar-dasar Teori Graf (3)sabri.staff.gunadarma.ac.id/.../03+Dasar+Teori+Graf.pdf · • Pada graf berarah berikut, simpul mewakili kota, ruas (berarah) mewakili trayek angkutan,

Dasar-dasar Teori Graf (3)

Dr. Ahmad SabriUniversitas Gunadarma

Page 2: Dasar-dasar Teori Graf (3)sabri.staff.gunadarma.ac.id/.../03+Dasar+Teori+Graf.pdf · • Pada graf berarah berikut, simpul mewakili kota, ruas (berarah) mewakili trayek angkutan,

Graf berarahSebuah Graf berarah (digraf) terdiri dari dua komponen:1. Himpunan simpul V2. Himpunan ruas E yang dinyatakan dalam

pasangan berurut (u,v)

Dinyatakan sebagai Graf G(V,E)V(G) = himpunan simpul V dari graf GE(G) = himpunan ruas dari graf G

2Ahmad Sabri, Universitas Gunadarma

Page 3: Dasar-dasar Teori Graf (3)sabri.staff.gunadarma.ac.id/.../03+Dasar+Teori+Graf.pdf · • Pada graf berarah berikut, simpul mewakili kota, ruas (berarah) mewakili trayek angkutan,

3Ahmad Sabri, Universitas Gunadarma

Page 4: Dasar-dasar Teori Graf (3)sabri.staff.gunadarma.ac.id/.../03+Dasar+Teori+Graf.pdf · • Pada graf berarah berikut, simpul mewakili kota, ruas (berarah) mewakili trayek angkutan,

Subgraf berarah

• Subgraf dari G(V,E) adalah Graf H(V',E') di mana V'⊂ V, dan E' adalah himpunan semua ruas pada E yang menghubungkan simpul pada V'

• Contoh: H(V',E') adalah subgraf dari graf pada contoh sebelumnya jika

4Ahmad Sabri, Universitas Gunadarma

Page 5: Dasar-dasar Teori Graf (3)sabri.staff.gunadarma.ac.id/.../03+Dasar+Teori+Graf.pdf · • Pada graf berarah berikut, simpul mewakili kota, ruas (berarah) mewakili trayek angkutan,

• Derajat keluar simpul v: adalah banyaknya ruas yang berawal dari simpul v, dinotasikan sebagai outdeg(v)

• Derajat masuk simpul v: adalah banyaknya ruas yang berakhir pada simpul v, dinotasikan sebagai indeg(v)

5Ahmad Sabri, Universitas Gunadarma

Page 6: Dasar-dasar Teori Graf (3)sabri.staff.gunadarma.ac.id/.../03+Dasar+Teori+Graf.pdf · • Pada graf berarah berikut, simpul mewakili kota, ruas (berarah) mewakili trayek angkutan,

6Ahmad Sabri, Universitas Gunadarma

Page 7: Dasar-dasar Teori Graf (3)sabri.staff.gunadarma.ac.id/.../03+Dasar+Teori+Graf.pdf · • Pada graf berarah berikut, simpul mewakili kota, ruas (berarah) mewakili trayek angkutan,

Keterhubungan pada graf berarah

Graf berarah G dikatakan:• Terhubung kuat (strongly connected) jika

untuk sebarang dua simpul u dan v pada G terdapat path dari u ke v dan sebaliknya.

• Terhubung lemah (weakly connected) jika terdapat path antara sebarang dua simpul u dan v, jika graf dijadikan tak berarah.

• Terhubung unilateral jika untuk sebarang dua simpul u dan v pada G terdapat salah satu: path dari u ke v atau sebaliknya

7Ahmad Sabri, Universitas Gunadarma

Page 8: Dasar-dasar Teori Graf (3)sabri.staff.gunadarma.ac.id/.../03+Dasar+Teori+Graf.pdf · • Pada graf berarah berikut, simpul mewakili kota, ruas (berarah) mewakili trayek angkutan,

• Manakah di antara graf berikut yang terhubung kuat dan terhubung lemah?

8Ahmad Sabri, Universitas Gunadarma

Page 9: Dasar-dasar Teori Graf (3)sabri.staff.gunadarma.ac.id/.../03+Dasar+Teori+Graf.pdf · • Pada graf berarah berikut, simpul mewakili kota, ruas (berarah) mewakili trayek angkutan,

Pohon berakar

• Pohon berakar (rooted tree) dianggap sebagai graf berarah.

• Arah ruas adalah dari sebuah level menuju satu level di bawahnya

9Ahmad Sabri, Universitas Gunadarma

Page 10: Dasar-dasar Teori Graf (3)sabri.staff.gunadarma.ac.id/.../03+Dasar+Teori+Graf.pdf · • Pada graf berarah berikut, simpul mewakili kota, ruas (berarah) mewakili trayek angkutan,

level 0 (root)

level 1

level 2

level 3

Kedalaman (depth) = 3Jika u berada pada level sebelum v dan terdapat lintasan dari u ke v, maka dikatakan u mendahului v (atau v mengikuti u). Jika jika dalam hal di atas, jika panjang lintasan hanya 1, maka dikatakan v mengikuti langsung u

10Ahmad Sabri, Universitas Gunadarma

Page 11: Dasar-dasar Teori Graf (3)sabri.staff.gunadarma.ac.id/.../03+Dasar+Teori+Graf.pdf · • Pada graf berarah berikut, simpul mewakili kota, ruas (berarah) mewakili trayek angkutan,

Turnamen tenis di mana juaranya adalah pihak yang menang 2 set berturut-turut atau menang 3 set secara keseluruhan

Eko vs Muji

11Ahmad Sabri, Universitas Gunadarma

Page 12: Dasar-dasar Teori Graf (3)sabri.staff.gunadarma.ac.id/.../03+Dasar+Teori+Graf.pdf · • Pada graf berarah berikut, simpul mewakili kota, ruas (berarah) mewakili trayek angkutan,

Representasi Graf• Matriks ketetanggaan (adjacency)

A=[aij]

aij=banyaknya ruas berawal di vi dan berakhir di vj

Untuk AK= [aij], maka aij=banyaknya lintasan panjang K, berawal di vi dan berakhir di vj

12Ahmad Sabri, Universitas Gunadarma

Page 13: Dasar-dasar Teori Graf (3)sabri.staff.gunadarma.ac.id/.../03+Dasar+Teori+Graf.pdf · • Pada graf berarah berikut, simpul mewakili kota, ruas (berarah) mewakili trayek angkutan,

13Ahmad Sabri, Universitas Gunadarma

Page 14: Dasar-dasar Teori Graf (3)sabri.staff.gunadarma.ac.id/.../03+Dasar+Teori+Graf.pdf · • Pada graf berarah berikut, simpul mewakili kota, ruas (berarah) mewakili trayek angkutan,

• bij menyatakan banyaknya lintasan dari vi ke vj dengan panjang r atau kurang

14Ahmad Sabri, Universitas Gunadarma

Page 15: Dasar-dasar Teori Graf (3)sabri.staff.gunadarma.ac.id/.../03+Dasar+Teori+Graf.pdf · • Pada graf berarah berikut, simpul mewakili kota, ruas (berarah) mewakili trayek angkutan,

• Matriks lintasan

jika terdapat lintasan dari vi ke vj

tidak demikian

15Ahmad Sabri, Universitas Gunadarma

Page 16: Dasar-dasar Teori Graf (3)sabri.staff.gunadarma.ac.id/.../03+Dasar+Teori+Graf.pdf · • Pada graf berarah berikut, simpul mewakili kota, ruas (berarah) mewakili trayek angkutan,

Proposisi: A adalah matriks ketetanggaan dari graf G dengan m simpul. Didefinisikan

Maka matriks lintasan P memiliki entri taknol pada indeks yang sama dengan entri taknol pada Bm

16Ahmad Sabri, Universitas Gunadarma

Page 17: Dasar-dasar Teori Graf (3)sabri.staff.gunadarma.ac.id/.../03+Dasar+Teori+Graf.pdf · • Pada graf berarah berikut, simpul mewakili kota, ruas (berarah) mewakili trayek angkutan,

17Ahmad Sabri, Universitas Gunadarma

Page 18: Dasar-dasar Teori Graf (3)sabri.staff.gunadarma.ac.id/.../03+Dasar+Teori+Graf.pdf · • Pada graf berarah berikut, simpul mewakili kota, ruas (berarah) mewakili trayek angkutan,

Beberapa problem1. Temukan semua lintasan

sederhana dari X ke Z2. Temukan semua siklus di G3. Apakah G terhubung

unilateral?4. Apakah G terhubung kuat?5. Tentukan matriks

ketetanggaan A dari graf ini6. Tentukan matriks lintasan P

18Ahmad Sabri, Universitas Gunadarma

Page 19: Dasar-dasar Teori Graf (3)sabri.staff.gunadarma.ac.id/.../03+Dasar+Teori+Graf.pdf · • Pada graf berarah berikut, simpul mewakili kota, ruas (berarah) mewakili trayek angkutan,

Masalah terkait graf berarah

1. Masalah rute terpendek2. Masalah arus maksimal

19Ahmad Sabri, Universitas Gunadarma

Page 20: Dasar-dasar Teori Graf (3)sabri.staff.gunadarma.ac.id/.../03+Dasar+Teori+Graf.pdf · • Pada graf berarah berikut, simpul mewakili kota, ruas (berarah) mewakili trayek angkutan,

Jalur terpendek (shortest path)

• Untuk sepasang simpul u dan v pada graf terhubung G, jalur terpendek yang menghubungkan u dan v adalah sebuah jalur yang berawal di u dan berakhir di v dengan total bobot paling minimal.

20Ahmad Sabri, Universitas Gunadarma

Page 21: Dasar-dasar Teori Graf (3)sabri.staff.gunadarma.ac.id/.../03+Dasar+Teori+Graf.pdf · • Pada graf berarah berikut, simpul mewakili kota, ruas (berarah) mewakili trayek angkutan,

Masalah jalur terpendek• Pada graf berarah berikut, simpul mewakili kota, ruas

(berarah) mewakili trayek angkutan, bobot ruas mewakili jarak antar kota. Seseorang akan bepergian dari kota u ke kota v. Kota mana sajakah yang harus ia lalui agar jarak tempuhnya minimal?

2

Sumber: Teori dan algoritma graf, Suryadi H.S, Penerbit Gunadarma

21Ahmad Sabri, Universitas Gunadarma

Page 22: Dasar-dasar Teori Graf (3)sabri.staff.gunadarma.ac.id/.../03+Dasar+Teori+Graf.pdf · • Pada graf berarah berikut, simpul mewakili kota, ruas (berarah) mewakili trayek angkutan,

Algoritma Dijkstra untuk menemukan jalur terpendek

Berikut adalah penyelesaian masalah tersebut berdasarkan algoritma Dijkstra:

22Ahmad Sabri, Universitas Gunadarma

Page 23: Dasar-dasar Teori Graf (3)sabri.staff.gunadarma.ac.id/.../03+Dasar+Teori+Graf.pdf · • Pada graf berarah berikut, simpul mewakili kota, ruas (berarah) mewakili trayek angkutan,

Algoritma Dijkstra (lanjutan)

23Ahmad Sabri, Universitas Gunadarma

Page 24: Dasar-dasar Teori Graf (3)sabri.staff.gunadarma.ac.id/.../03+Dasar+Teori+Graf.pdf · • Pada graf berarah berikut, simpul mewakili kota, ruas (berarah) mewakili trayek angkutan,

Solusi:Berdasarkan penelusuran terbalik dari v ke u diperoleh jalur:

v ← c ← y ← z ← u

Dengan total jarak = 8

24Ahmad Sabri, Universitas Gunadarma

Page 25: Dasar-dasar Teori Graf (3)sabri.staff.gunadarma.ac.id/.../03+Dasar+Teori+Graf.pdf · • Pada graf berarah berikut, simpul mewakili kota, ruas (berarah) mewakili trayek angkutan,

Masalah arus maksimal• Tujuan: mengatur alokasi dan rute perjalanan

objek (orang/barang, dsb) dari tempat asal ke tempat tujuan, sehingga objek yang dialirkan semaksimal mungkin, berdasarkan kondisi jaringan

• Dalam graf, simpul mewakili tempat, ruas mewakili jalan. Simpul asal disebut sumber, simpul tujuan disebut muara

• Antara sumber dan muara terdapat simpul perantara, di mana aliran objek hanya dapat transit sementara sebelum mengalir ke simpul lainnya.

25Ahmad Sabri, Universitas Gunadarma

Page 26: Dasar-dasar Teori Graf (3)sabri.staff.gunadarma.ac.id/.../03+Dasar+Teori+Graf.pdf · • Pada graf berarah berikut, simpul mewakili kota, ruas (berarah) mewakili trayek angkutan,

Masalah arus maksimal• Tentukan aliran maksimal dari a ke d untuk jaringan

berikut. (Angka pada pangkal ruas adalah ketersediaan volume aliran menuju simpul yang dituju ruas tersebut).

Sumber: Teori dan algoritma graf, Suryadi H.S, Penerbit Gunadarma

26Ahmad Sabri, Universitas Gunadarma

Page 27: Dasar-dasar Teori Graf (3)sabri.staff.gunadarma.ac.id/.../03+Dasar+Teori+Graf.pdf · • Pada graf berarah berikut, simpul mewakili kota, ruas (berarah) mewakili trayek angkutan,

Langkah penyelesaian

ruas/busur pengirim

ruas

27Ahmad Sabri, Universitas Gunadarma

Page 28: Dasar-dasar Teori Graf (3)sabri.staff.gunadarma.ac.id/.../03+Dasar+Teori+Graf.pdf · • Pada graf berarah berikut, simpul mewakili kota, ruas (berarah) mewakili trayek angkutan,

Total aliran maksimal = 22

28Ahmad Sabri, Universitas Gunadarma

Page 29: Dasar-dasar Teori Graf (3)sabri.staff.gunadarma.ac.id/.../03+Dasar+Teori+Graf.pdf · • Pada graf berarah berikut, simpul mewakili kota, ruas (berarah) mewakili trayek angkutan,

Total aliran maksimal = 22

29Ahmad Sabri, Universitas Gunadarma