pengenalan graph

52
Disusun Oleh: Budi Arifitama Pertemuan 9

Upload: zan

Post on 11-Jan-2016

60 views

Category:

Documents


2 download

DESCRIPTION

Pengenalan Graph. Disusun Oleh: Budi Arifitama Pertemuan 9. Questions Review. Apa yang dimaksud dengan tree? Sebutkan penggunaan tree yang digunakan dalam kehidupan sehari hari Apa yang dimaksud dengan leaf? Apakah sebuah leaf dapat memiliki node dibawahnya? - PowerPoint PPT Presentation

TRANSCRIPT

Page 1: Pengenalan  Graph

Disusun Oleh: Budi Arifitama

Pertemuan 9

Page 2: Pengenalan  Graph

Questions Review1. Apa yang dimaksud dengan tree?2. Sebutkan penggunaan tree yang digunakan

dalam kehidupan sehari hari3. Apa yang dimaksud dengan leaf?4. Apakah sebuah leaf dapat memiliki node

dibawahnya?5. Seandainya Sebuah leaf memiliki node

dibawahnya sebutan apa kira kira yang tepat buat node tersebut?

6. Apa yang dimaksud dengan pohon biner?

Page 3: Pengenalan  Graph

Implementasi Tree (Preorder,Inorder & Postorder)

Page 4: Pengenalan  Graph
Page 5: Pengenalan  Graph

Sub TopikOverview : GraphJenis GraphImplementasi GraphGraph PropertyRepresentasi Graph

Page 6: Pengenalan  Graph

GraphGraph digunakan untuk merepresentasikan

objek-objek diskrit dan hubungan antara objek-objek tersebut.

Gambar berikut ini sebuah graph yang menyatakan peta jaringan jalan raya yang menghubungkan sejumlah kota di Provinsi Jawa Tengah.

Page 7: Pengenalan  Graph

Graph

Brebes Tegal

Slawi

Pemalang

Purwokerto

Cilacap

Banjarnegara

Wonosobo

Kebumen

Purworejo

KendalSemarang

Pekalongan

Purbalingga

Magelang

Salatiga

Klaten

Solo

Purwodadi

DemakKudus

Rembang

Blora

Sukoharjo

Wonogiri

SragenBoyolali

Kroya

Temanggung

Page 8: Pengenalan  Graph

Definisi Graf

Graf G (V, E), adalah koleksi atau pasangan dua himpunan

Himpunan V yang elemennya disebut simpul atau titik, atau vertex, atau point, atau node.

Himpunan E yang merupakan pasangan tak terurut dari simpul, disebut ruas

atau rusuk, atau sisi, atau edge, atau line.

Page 9: Pengenalan  Graph

GraphBanyaknya simpul (anggota V) disebut order

Graf G, sedangkan banyaknya ruas(anggota E) disebut ukuran (size) Graf G

Page 10: Pengenalan  Graph

GraphG = (V,E)Dimana :

V adalah Vertex, menyatakan entitas data.E adalah Edge, menyatakan garis penghubung antar node.

Vertex (Vertices) disebut juga sebagai node atau point.

Edge disebut juga sebagai arcs atau lines.Setiap edge menghubungkan dua

vertices.

Page 11: Pengenalan  Graph

Contoh GraphContoh persoalan di dunia nyata yang dapat

direpresentasikan dengan graph adalah : Jaringan pertemanan pada Facebook.

Page 12: Pengenalan  Graph

Toni

Nina

Ale

Firda

Joko

Riza

Graph dengan 6 node/vertex dan 7 lines/edge yang merepresentasikan jaringan pertemanan pada Facebook

Page 13: Pengenalan  Graph

PenjabaranNode(vertex): para pemakai FacebookLines(edge) : Garis penghubung antara

pemakai satu dengan yang lain.Sehingga dari contoh graph diatas dapat

dijabarkan sebagai berikut : V = {Nina, Toni, Ale, Riza, Joko, Firda}E = {{Nina,Toni},{Toni,Riza},{Nina, Riza}, {Toni,Ale}, {Ale,Joko},{Riza,Joko},{Firda,Joko}}

Page 14: Pengenalan  Graph

Jenis GraphDirected Graph (Digraph)Undirected Graph

Complete Undirected GraphConnected Undirected Graph

Weigth Graph

Page 15: Pengenalan  Graph

Directed Graph (Digraph)Graph yang memiliki orientasi/arah.Setiap lines/edge Digraph memiliki anak

panah yang mengarah ke node tertentu.Secara notasi sisi digraph ditulis sebagai

vektor (u, v).u = origin (vertex asal)v = terminus (vertex tujuan)

u v

Page 16: Pengenalan  Graph

Contoh Digraph (1)2

3

1

45

67

Page 17: Pengenalan  Graph
Page 18: Pengenalan  Graph

Contoh Digraph (2)G = {V, E}V = {A, B, C, D, E, F, G, H, I,J, K, L, M}E = {(A,B),(A,C), (A,D), (A,F), (B,C), (B,H),

(C,E), (C,G), (C,H), (C,I), (D,E),(D,F), (D,G), (D,K), (D,L), (E,F), (G,I),

(G,K), (H,I), (I,J), (I,M), (J,K), (J,M),(L,K), (L,M)}.

Page 19: Pengenalan  Graph

Undirected Graph (Digraph)Graph yang tidak memiliki orientasi/arah.Setiap sisi {u, v} berlaku pada kedua arah.Misalnya : {x,y}. Arah bisa dari x ke y, atau y

ke x.Secara grafis sisi pada undigraph tidak

memiliki mata panah dan secara notasional menggunakan kurung kurawal.

u v

Page 20: Pengenalan  Graph

Contoh Undi-Graph (1)2

3

8101

45

911

67

Page 21: Pengenalan  Graph
Page 22: Pengenalan  Graph

Contoh Undi-Graph (2)G = {V, E}V = {A, B, C, D, E, F, G, H, I,J, K, L, M}E = { {A,B},{A,C}, {A,D}, {A,F}, {B,C},

{B,H}, {C,E}, {C,G}, {C,H}, {C,I}, {D,E},

{D,F}, {D,G}, {D,K}, {D,L}, {E,F}, {G,I}, {G,K}, {H,I}, {I,J}, {I,M}, {J,K},

{J,M}, {L,K}, {L,M}}.

Page 23: Pengenalan  Graph

Complete Undirected GraphSemua node memiliki edge/lines untuk setiap

node pada graph.

n = 1 n = 2 n = 3 n = 4

n = node

Page 24: Pengenalan  Graph

Connected GraphTermasuk Jenis Undirected graph.Setiap pasang vertex memiliki edge.

Page 25: Pengenalan  Graph

Contoh Connected Graph2

3

8101

45

911

67

Page 26: Pengenalan  Graph

Contoh Not Connected Graph2

3

8101

45

911

67

Page 27: Pengenalan  Graph

Connected Components

23

8101

45

911

67

Page 28: Pengenalan  Graph

Weigth GraphJika semua lines/edge dalam graph memiliki

bobot/nilai (value).

Page 29: Pengenalan  Graph

B

A

C

E

F

D

2

2

2

4

4

5

Page 30: Pengenalan  Graph

Istilah pada graphDegree (derajat), indegree dan outdegree

Degree sebuah simpul adalah jumlah busur yang incident dengan simpul tersebut.

Page 31: Pengenalan  Graph

Indegree sebuah simpul pada graph berarah adalah jumlah busur yang kepalanya incident dengan simpul tersebut, atau jumlah busur yang “masuk” atau menuju simpul tersebut.

Outdegree sebuah simpul pada graph berarah adalah jumlah busur yang ekornya incident dengan simpul tersebut, atau jumlah busur yang “keluar” atau berasal dari simpul tersebut.

Page 32: Pengenalan  Graph

3. Adjacent Pada graph tidah berarah, 2 buah simpul disebut adjacent bila ada busur yang menghubungkan kedua simpul tersebut. Simpul v dan w disebut adjacent.

Pada graph berarah, simpul v disebut adjacent dengan simpul w bila ada busur dari w ke v.

w

ev

v

e w

Page 33: Pengenalan  Graph

4. Successor dan Predecessor

Pada graph berarah, bila simpul v adjacent dengan simpul w, maka simpul v adalah successor simpul w, dan simpul w adalah predecessor dari simpul v.

5. Path

Sebuah path adalah serangkaian simpul-simpul yang berbeda, yang adjacent secara berturut-turut dari simpul satu ke simpul berikutnya.

1

43

2

4

2

4

2

4

21

3

1

3

1

3

Page 34: Pengenalan  Graph

Representasi Graph dalam bentuk matrixAdjacency Matrix Graph tak berarah

0 1 0 1 0

1 0 1 0 1

0 1 0 1 1

1 0 1 0 1

0 1 1 1 0

B

A C

D E

Graph

A B

A

0

B

C

1 2 43C D E

D

E

0

1

2

4

3

Urut abjad

Degree simpul : 3

Page 35: Pengenalan  Graph

Representasi Graph dalam bentuk matrixDirected Adjacency Matrix Graph

0 1 0 1 0

1 0 1 0 1

0 1 0 1 1

0 0 1 0 1

0 0 0 0 0Graph

A B

A

0

B

C

1 2 43C D E

D

E

0

1

2

4

3

B

A C

D E

kedari

out

in

Page 36: Pengenalan  Graph

Contoh : untuk vertex A, memiliki 2 edge yang terhubung yaitu e1 dan e2.

A

C

D

B

E

e2

Graph

e1B

A C

D E

e1e3

e4

e7e5e2

e6

Urut abjad

Page 37: Pengenalan  Graph

List Matrix

A

C

D

B

E

D

A

B

A

B

C E

D E

C

C D

B

A C

D E

Graph

B

E

Page 38: Pengenalan  Graph

Directed Adjency List Graph

A

C

D

B

E

D

A

B

C

E

C

B

E

B

A C

D E

Page 39: Pengenalan  Graph

Directed & Weighted Graph

B

A C

D E

53

2

14

12

6

7

12

0 5 0 2 0

6 0 3 0 0

0 0 0 0 9

0 0 12

0 7

0 14

0 0 0

A

A

0

B

C

1 2 43

D

E

0

1

2

4

3

B C D E

Perhatikan pemilihan nilai 0.

Page 40: Pengenalan  Graph

Vertex degreeDegree : Jumlah edge/lines yang dimiliki

node/vertex.

Page 41: Pengenalan  Graph

Contoh Vertex Degree

degree(2) = 2, degree(5) = 3, degree(3) = 1degree(9) = ??? degree (11) = ???

23

8101

45

911

67

Page 42: Pengenalan  Graph

In-DegreeJumlah edge yang mengarah ke Node/Vertex.

indegree(2) = 1, indegree(8) = 0, indegree(7)=???

23

8101

45

911

67

Page 43: Pengenalan  Graph

Out-DegreeJumlah edge yang keluar dari Node/Vertex.

outdegree(2) = 1, outdegree(8) = 2, outdegree(7) = ???

23

8101

45

911

67

Page 44: Pengenalan  Graph
Page 45: Pengenalan  Graph

Aplikasi Jaringan Komunikasi

Node/Vertex = kota Lines/Edge = communication link.

23

8101

45

911

67

Page 46: Pengenalan  Graph

Peta Penelusuran Kota(Berdasarkan Jarak/Waktu)

Node/Vertex = KotaLines/edge = jalurWeight = jarak/waktu

23

810

1

45

911

67

48

6

6

7

5

24

4 53

Page 47: Pengenalan  Graph

Peta kota

Some streets are one way.

23

8101

45

911

67

Page 48: Pengenalan  Graph
Page 49: Pengenalan  Graph

Beberapa Aplikasi Grafa. Lintasan Terpendek (Shortest Path)graf berbobot (weighted graph), lintasan terpendek: lintasan yang memiliki total

bobot minimum.Contoh aplikasi: Menentukan jarak terpendek/waktu tempuh

tersingkat/ongkos termurah antara dua buah kota

Menentukan waktu tersingkat pengiriman pesan (message) antara dua buah terminal pada jaringan komputer.

Page 50: Pengenalan  Graph

Lintasan TerpendekTerdapat beberapa jenis persoalan lintasan

terpendek, antara lain:Lintasan terpendek antara dua buah simpul

tertentu.Lintasan terpendek antara semua pasangan

simpul.Lintasan terpendek dari simpul tertentu ke

semua simpul yang lain.Lintasan terpendek antara dua buah simpul yang

melalui beberapa simpul tertentu. ==> Di dalam kuliah ini kita memilih jenis

persoalan 3.

Page 51: Pengenalan  Graph

Lintasan TerpendekUraian persoalanDiberikan graf berbobot G = (V, E) dan

sebuah simpul a. Tentukan lintasan terpendek dari a ke setiap simpul lainnya di G. Asumsi yang kita buat adalah bahwa semua sisi berbobot positif.

Page 52: Pengenalan  Graph

Lintasan TerpendekGraph

45

50 10

35

30

315

1540

20 10 20

1 2

3 4 6

5

Simpul asal

Simpul Tujuan

Lintasan terpendek

Jarak

1 3 1 3 10

1 4 1 3 4 25

1 2 1 3 4 2 45

1 5 1 5 45

1 6 tidak ada -