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

Dasar-dasar Teori Graf (3)

Dr. Ahmad SabriUniversitas Gunadarma

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

3Ahmad Sabri, Universitas Gunadarma

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

• 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

6Ahmad Sabri, Universitas Gunadarma

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

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

8Ahmad Sabri, Universitas Gunadarma

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

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

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

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

13Ahmad Sabri, Universitas Gunadarma

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

14Ahmad Sabri, Universitas Gunadarma

• Matriks lintasan

jika terdapat lintasan dari vi ke vj

tidak demikian

15Ahmad Sabri, Universitas Gunadarma

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

17Ahmad Sabri, Universitas Gunadarma

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

Masalah terkait graf berarah

1. Masalah rute terpendek2. Masalah arus maksimal

19Ahmad Sabri, Universitas Gunadarma

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

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

Algoritma Dijkstra untuk menemukan jalur terpendek

Berikut adalah penyelesaian masalah tersebut berdasarkan algoritma Dijkstra:

22Ahmad Sabri, Universitas Gunadarma

Algoritma Dijkstra (lanjutan)

23Ahmad Sabri, Universitas Gunadarma

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

v ← c ← y ← z ← u

Dengan total jarak = 8

24Ahmad Sabri, Universitas Gunadarma

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

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

Langkah penyelesaian

ruas/busur pengirim

ruas

27Ahmad Sabri, Universitas Gunadarma

Total aliran maksimal = 22

28Ahmad Sabri, Universitas Gunadarma

Total aliran maksimal = 22

29Ahmad Sabri, Universitas Gunadarma