Graphs

Graph adalah himpunan pasangan terurut (V,E), V himpunan Vertex, E himpunan Edge.Untuk u,v Є V dikatakan u dihubungkan ke v oleh suatu garis, jika (u,v) anggota E.Maka pada struktur data dapat dikatakan Graph merupakan struktur data yang mempunyai hubungan antar elemen. Notasi Graph

• Node, titik, simpul. • Edge, arc, rusuk. Dimana G=(V,E)

Contoh Graph

Representasi Graph tersebut : V(G1) = {1,2,3,4} ; E(G) = {(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)} V(G2) = {1,2,3,4,5,6,7} = {(1,2),(1,2),(2,4),(2,5),(3,6), (3,7)} V(G3) = {1,2,3} = {(1,2),(2,1),(2,3)} Graph G2 adalah tree. Sebagaimana definisi diatas edges dan vertex dari graph adalah himpunan, maka ditentukan larangan terhadap graph sebagai berikut :

1. Graph tidak boleh memiliki edge dari vertex dirinya kembali kepada dirinya juga. Ex : (v,v) tidak dibolehkan. Edge seperti ini disebut self edge atau self loop. Jika kita abaikan larangan ini maka kita akan memperoleh obyek data yang mengarah pada graph with self edge.

2. Graph tidak boleh memiliki edge yang ganda/ lebih dari satu yang

menghubungkan dua vertex. Jika kita abaikan larangan ini, maka kita memperoleh obyek data yang dikenal sebagai multigraph.

Jumlah maksimum edges pada n vertex undirected graph adalah 2

)1( −nn , pada vertex

dengan undirected graph yang memiliki edge tepat 2

)1( −nn disebut complete

graph.Sebagai contoh adalah graph G1. Jika pada directed graph maka nilai maksimum edges dari n vertex adalah n(n-1). Jika (u,v) adalah edge pada E(G), maka vertex u dan v adalah adjacent dan edge(u,v) adalah incident di vertex u dan v. Subgraph dari G adalah graph G’ seperti V(G’) ⊆ V (G) dan E(G’) ⊆ E(G). Contoh subgraph G1 :

2 3

1

2 3

4

1

Beberapa subgraph dr Graph G1

2 3

4

Connectivity pada Graph

• Path adalah lintasan dari suatu vertex ke vertex yang lain yang semua titiknya/ vertex yang dilaluinya berlainan.

• Cycle adalah lintasan dimana vertex awal dan akhirnya sama, yang mempunyai path tertutup.

• Tree adalah suatu graph yang banyak vertexnya = n, (n>1) yang tidak mempunyai lingkar dan banyak rusuk (n-1) serta graph tersebut terhubung.

• Degree/ Derajat suatu vertex adalah banyaknya edge yang incident pada vertex tersebut.

o Indegree dari suatu vertex v adalah jumlah edge yang datang/masuk kearah v (directed graph).

o Outdegree dari suatu vertex v adalah jumlah edge yang pergi/keluar meninggalkan v(directed graph).

Jika di adalah degree dari vertex i pada graph G dengan n vertex dan e edge, maka jumlah dari edgenya adalah

e = 21∑=

n

idi

Representasi Graph Adjacency Matrix G = (V,E) adalah sebuah graph dengan n vertex, maka adjacency matrix dari G ialah nxn array dua dimensi dengan property dari a[i][j] = 1 jika edge (i,j),(i,j) untuk directed graph pada E(G). Elemen E[i][j] = 0 jika tidak ada edge di G.Sebagai contoh berikut ini adalah adjacency matrix dari G1 dan G3 : 4321 321

0111101111011110

4321

000101010

321

(a) G1 (b) G2 Untuk undirected graph degree dari vertex i ada pada jumlah baris :

∑=

n

jjia

1]][[

Untuk directed graph jumlah baris adalah outdegree, dan jumlah kolom adalah indegree. Adjacency List Pada representasi adjacency list dari suatu graph, n baris dari suatu adjacency matrix direpresentasikan sebagai n link list. Setiap vertex G memiliki sebuah list. Node pada list i mempresentasikan vertex terhubung dari vertex i. Setiap node setidaknya memiliki dua field; vertex dan link. Berikut ini adalah contoh adjacency list dari graph G1 dan G3:

Contoh definisi class graph pada C++ untuk adjacency list : Class Graph { private : int n; // number of vertices struct node { int vertex; struct node * link; }; struct node* headnodes[n+1]; public: Graph() {for (int i=1;i<=n;i++)headnodes[i] = NULL;} }; Adjacency Multilist Adjacency list merepresentasikan undirected graph, setiap edge(u,v) diwakilkan oleh dua masukan, satu pada list u dan yang lain pada list v. Pada beberapa aplikasi dibutuhkan masukan yang lain untuk edge tertentu dan memberi tanda bahwa edge sudah diperiksa. Hal ini dapat dilakukan dengan mudah jika adjacency list diperlakukan sebagai multililist(list yang nodenya dapat dishare/bagi ke beberapa list yang lain).Untuk setiap edge memiliki tepat 1 node, tetapi node ini berada pada dua list. Sebagai contoh untuk Graph G3 :

Struktur yang baru suatu adjacency multilist :

Dimana m adalah satu bit field tanda yang digunakan untuk mengidentifikasikan apakah edge sudah diperiksa.Contoh deklarasi dalam C++ : Class Graph { private: int n; // Number of vertices struct edge { bool m; int vertex1,vertex2; struct edge *path1,*path2; }; public: Graph() {for (int i=1;i<=n;i++) headnodes[i] = NULL;} }; Weighted Edges Pada banyak aplikasi, edge/rusuk dari suatu graph memiliki bobot/nilai. Nilai ini dapat mempersentasikan jarak dari suatu titik ke titik yang lain. Pada aplikasi ini adjacency matrix a[i][j] dapat digunakan untuk menyimpan informasi tersebut.Jika adjacency list yang digunakan,maka bobot dari edge dapat disimpan pada node list dengan menambahkan field tambahan ex; field weight.Graph dengan weighted edge disebut network.

Heasing

Heasing adalah suatu cara untuk menyimpan dan mengambil target data tanpa

searching, yaitu dengan cara menghitung lokasi dari target.Ketika diberikan suatu target key, maka alamat dapat dihitung dengan persamaan sebagai berikut: Alamat target = f(key) Perfect heasing function

• Pemetaan key ke alamat secara sempurna,one to one relation. • Fungsi memberikan alamat yang pasti dari suatu target data. • Set key harus telah diketahui sebelumnya.

Practical heasing function

• Gabungan antara perhitungan / mapping dengan searching. • Fungsi tidak perlu memberikan alamat yang pasti, tetapi cukup memberikan

Home Address(HA). HA = H(key)

• Diperlukan rehashing untuk mendapatkan alamat yang pasti. Ide dasar heasing adalah menyebar data secara acak kedalam table heashing.Berbeda dengan teknik search, dimana data terlebih dahulu diurutkan supaya search lebih efisien. Penempatan data kedalam table heashing Ex: Kapasitas table heasing = 5 Fungsi hash : H(key) = key mod 5 Tabel heashing

Alamat Data Keterangan [0] [1] [2] [3] [4]

Misalkan banyaknya data = 3, dengan nilai data sbb: Data ke 1 : 28 Data ke 2 : 15 Data ke 3 : 9

Maka data pertama masuk dengan key = 28, dihitung dengan H(28) = 28 mod 5 = 3, dengan demikian data pertama masuk dialamat 3. Data yang lain : H(12) = 15 mod 5 = 0 alamat 0 H(9) = 9 mod 5 = 4 alamat 4

Alamat Data Keterangan [0] 15 Data ke 2 [1] [2] [3] 28 Data ke 1 [4] 9 Data ke 3

Collision Jika data ke 4 bernilai 13, maka data tersebut akan menuju ke alamat : H(13) = 13 mod 5 = 3 alamat 3 Alamat 3 ternyata sudah terisi oleh data 28, maka terjadi collision (tabrakan).Untuk ini diperlukan adanya collision resolution strategies. Collision resolution strategies

1. Open address • Linear rehashing

k= (HA+j) mod kapasitas table j = 1,2,3,4,… hingga tempat kosong didapatkan.

Gejala tidak baik pada linear heashing : Primary clustering

Semua key jatuh pada suatu HA, akan mengikuti jalur yang sama, sebelum akhirnya menemukan tempat kosong.

Secondary clustering

Pola probe untuk rehash dari HA1 akan bergabung dengan pola probe untuk rehash dari HA2 (HA2 >HA1).

• Quadratic rehashing Menghindari secondary clustering dengan perhitungan : K= (HA + j 2 ) mod kapasitas tabel

• Double heashing Menghindari primary clustering dengan persamaan : K=(HA + j * c ) mod kapasitas tabel c(key)= [key mod (kapasitas table-2)]+1 Nilai c membuat loncatan pseudo-random.

2. External chaining Bila terjadi tabrakan, tidak dilakukan rehashing, melainkan menambah

tempat penampungan dengan cara extra linked list.

3. Coaleasced Chaining Tabel hash dibagi menjadi dua bagian : 1. Daerah Address 2. Daerah Cellar ( Cadangan)

Alamat Data Keterangan

[0] [1] [2] Address [3]

[4] Cellar [5] epla

Epla = empty position with largest address. Bila terjadi tabrakan probe akan dilakukan pada elpa. Hashing function

1. Digit selection Misalkan key yang digunakan adalah NIM 10 digit, yaitu : D1 D2 D3 D4 D5 D6 D7 D8 D9 D10 Harus dipilih digit yang dapat menghindari tabrakan, bila dipilih D8 D9 D10 kemungkinan terjadi tebrakan sangat besar. Mungkin dapat diambil digit : D6 D8 D 10.

2. Division H(key) = key mod n N sebaiknya dipilih dari bilangan prima, bila bukan bilangan prima, misalkan tablesize = 25, maka semua key yang habis dibagi 5 akan dipetakan pada posisi : 0, hal ini akan membuat pemetaan menjadi terbias. Twin Prime bila tablesize = bilangan prima dan t= tablesize-2 = bialangan prima, yang akan menjamin exhaustive search tanpa pengulangan, artinya seluruh posisi dalam table sudah diprobe dan kembali ke posisi awal, sebagai tanda search berakhir.

3. Multiplication Misalkan key menjadi 5 digit ; D1 D2 D3 D4 D5

Lakukan perkalian : D1 D2 D3 D4 D5 D1 D2 D3 D4 D5 --------------------------------------------X R1 R2 R3 R4 R5 R6 R7 R8 R9 R10 Ex : key = 54321 54321 54321 --------x 54321 108624 162963 217284 271605 ----------------- 2950771041

2-digit terakhir yaitu 41 merupakan hasil perkalian 1x21 dan 2x21, dengan demikian setiap key yang mempunyai digit terakhir = 21 akan menempati alamat 41.Ambil digit tengah maka H(54321)=77.

4. Folding

Misalkan key mempunyai 5 digit : D1 D2 D3 D4 D5 H(key) = D1 + D2 + D3 + D4 + D5 Hasilnya akan berada didaerah : 0 <= H<= 45 Bila table yang lebih besar diperlukan, dapat dilakukan penambahan jumlah digit misal menjadi 2 digit. H(key) = 0D1 + D2 D3 + D4 D5 Hasilnya akan berada didaerah : 0 <= H <= 207 Folding digunakan bersama division. Ex : key = 987654321 Dilakukan folding 4 digit : Fold (key) = 0009 + 8765 + 4321 = 13095 H(key) = Fold(key) mod n = 13095 mod n. Dimana n tergantung dari kapasitas table disesuaikan dengan banyaknya data agar tidak berlebih.

TUGAS

PERANCANGAN dan ANALISA ALGORITMA

O L E H

RARAS WIRASTO 0600640982

DOSEN