pengenalan graph
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 PresentationTRANSCRIPT
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 -