pengenalan graph

Disusun Oleh: Budi Arifitama

Pertemuan 9

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?

Implementasi Tree (Preorder,Inorder & Postorder)

Sub TopikOverview : GraphJenis GraphImplementasi GraphGraph PropertyRepresentasi 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.

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

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.

GraphBanyaknya simpul (anggota V) disebut order

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

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.

Contoh GraphContoh persoalan di dunia nyata yang dapat

direpresentasikan dengan graph adalah : Jaringan pertemanan pada Facebook.

Toni

Nina

Ale

Firda

Joko

Riza

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

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}}

Jenis GraphDirected Graph (Digraph)Undirected Graph

Complete Undirected GraphConnected Undirected Graph

Weigth 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

Contoh Digraph (1)2

3

1

45

67

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)}.

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

Contoh Undi-Graph (1)2

3

8101

45

911

67

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}}.

Complete Undirected GraphSemua node memiliki edge/lines untuk setiap

node pada graph.

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

n = node

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

Contoh Connected Graph2

3

8101

45

911

67

Contoh Not Connected Graph2

3

8101

45

911

67

Connected Components

23

8101

45

911

67

Weigth GraphJika semua lines/edge dalam graph memiliki

bobot/nilai (value).

B

A

C

E

F

D

2

2

2

4

4

5

Istilah pada graphDegree (derajat), indegree dan outdegree

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

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.

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

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

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

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

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

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

Directed Adjency List Graph

A

C

D

B

E

D

A

B

C

E

C

B

E

B

A C

D E

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.

Vertex degreeDegree : Jumlah edge/lines yang dimiliki

node/vertex.

Contoh Vertex Degree

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

23

8101

45

911

67

In-DegreeJumlah edge yang mengarah ke Node/Vertex.

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

23

8101

45

911

67

Out-DegreeJumlah edge yang keluar dari Node/Vertex.

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

23

8101

45

911

67

Aplikasi Jaringan Komunikasi

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

23

8101

45

911

67

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

Peta kota

Some streets are one way.

23

8101

45

911

67

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.

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.

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.

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 -