Modul BSI Struktur Data Pertemuan 11

Modul BSI Struktur Data

Modul BSI Struktur Data Pertemuan 11

GRAPH dan

MATRIK PENYAJIAN GRAPH

GRAPH
Suatu Graph mengandung 2 himpunan, yaitu :
1.   Himpunan V yang elemennya disebut simpul (Vertex atau Point atau Node atau Titik)
2.   Himpunan E yang merupakan pasangan tak urut dari simpul. Anggotanya disebut Ruas (Edge atau rusuk atau sisi)
     Graph seperti dimaksud diatas, ditulis sebagai G(E,V).

Banyaknya simpul (vertex) disebut Order, sedangkan banyaknya ruas (edge) disebut Size dari Graph.
Contoh :
Gambar berikut menanyakan Graph G(E,V) dengan :
1.   V mengandung 4 simpul, yaitu simpul  A,B,C,D.
2.   E mengandung 5 ruas, yaitu :
    e1 = (A,B)        e4 = (C,D)
    e2 = (B,C)        e5 = (B,D)
    e3 = (A,D)

Gambar dibawah ini menyatakan suatu Multigraph. Disini, ruas e2 pada kedua titik ujungnya adalah simpul yang sama, yaitu simpul A. Ruas semacam ini disebut Gelung atau Self-Loop. Sedangkan ruas e5 dan e6 mempunyai titik ujung yang sama, yaitu simpul-simpul B dan C. Kedua ruas ini disebut ruas berganda atau ruas sejajar.

Suatu Graph yang tidak mengandung ruas sejajar maupun self-loop, sering disebut juga sebagai Graph sederhana atau simple Graph.
Suatu Graph G’(E’,V’) disebut Sub Graph dari G(E,V), bila E’ himpunan bagian dari E dan V’ himpunan bagian dari V.
Jika E’ mengandung semua ruas dari E yang titik ujungnya di V’, maka G’ disebut Subgraph yang direntang oleh V’ (Spanning Subgraph).

Contoh Sub Graph:

Contoh Spanning Sub Graph :

GRAPH BERLABEL
Graph G disebut berlabel jika ruas dan atau simpulnya dikaitkan dengan suatu besaran tertentu. Khususnya jika setiap Ruas e dari G dikaitkan dengan suatu bilangan non negatif d(e), maka d(e)  disebut  bobot atau panjang dari ruas e.

Contoh :
Gambar berikut ini menyajikan hubungan antar kota.
Disini simpul menyatakan kota dan label d(e) menyatakan jarak antara dua kota.

DERAJAT GRAPH
Derajat simpul V, ditulis d(v) adalah banyaknya ruas yang menghubungi v. Karena setiap ruas dihitung dua kali ketika menentukan derajat suatu Graph, maka :

Jumlah derajat semua simpul suatu Graph (derajat) = dua kali banyaknya ruas Graph (Size) Atau dapat dituliskan :

Pada gambar diatas Jumlah Semua Simpul = 4, maka Jumlah  Derajat Semua Simpul = 8 Jika Derajat masing-masing simpul pada Graph berjumlah Genap maka Graph tersebut disebut EULER Graph

Suatu simpul disebut genap/ganjil tergantung apakah derajat simpul tersebut genap/ganjil. Kalau terdapat self-loop, maka self-loop dihitung 2 kali pada derajat simpul
Contoh :

Pada gambar diatas, banyak ruas/size = 7, sedangkan derajat masing-masing simpul adalah  :
    d(A)  = 2   
    d(B)  = 5
    d(C)  = 3
    d(D)  = 3       
    d(E)  = 1
    d(F)  = 0
maka, total jumlah derajat simpul adalah  : 14
E disebut simpul bergantung/akhir, yaitu simpul yang berderajat satu. Sedangkan F disebut simpul terpencil, yaitu simpul yang berderajat Nol.

KETERHUBUNGAN
Walk atau perjalanan dalam Graph G adalah barisan simpul dan ruas berganti-ganti :  V1,e1,V2,e2,......., e n-1, Vn
Disini ruas ei menghubungkan simpul Vi dan Vi+1.
Banyaknya ruas disebut Panjang Walk. Walk dapat ditulis lebih singkat dengan hanya menulis deretan ruas : e1,e2, ...., en-1 atau deretan simpul :  V1, V2,....., Vn-1, Vn
dimana : V1 = simpul awal
     Vn = simpul akhir.

Walk disebut tertutup bila  V1 = Vn

1. Walk disebut, yang menghubungkan v1 dan vn, yaitu setiap Ruas menghubungkan Simpul Awal dan Akhir

2. Trail adalah Walk dengan semua ruas dalam barisan adalah berbeda.
3. Path atau Jalur adalah Walk yang semua simpul dalam barisan adalah berbeda. Jadi suatu path pastilah sebuah Trail.

Graph merupakan Walk Terbuka, karena tidak ada ruas yang menghubungkan Simpul U dan T. Merupakan suatu Path atau Trail terbuka dengan derajat setiap simpulnya = 2, kecuali simpul awal U dan  simpul akhir T berderajat = 1.

1. Cycle atau sirkuit adalah suatu Trail tertutup dengan derajat setiap simpul = 2. Cycle dengan panjang k disebut dengan k-cycle. Demikian pula Jalur dengan panjang k disebut k-jalur.

•  Barisan ruas a,b,c,d,b,c,g,h adalah Walk bukan Trail (karena ruas b dua kali muncul).          
•  Barisan simpul A, B, E, F bukan Walk (karena tdk ada ruas yang menghubungkan simpul B ke F).           
•  Barisan simpul A, B, C, D, E, C, F adalah Trail bukan Jalur/Path (karena c dua kali muncul)·        
•  Barisan ruas a, d, g, k adalah Jalur/Path karena menghubungkan A dengan F·       
•  Ruas a, b, h, g, e, a, adalah Cycle.   Graph yang tidak mengandung Cycle disebut Acyclic. Contoh dari Graph Acyclic adalah pohon atau Tree.

Contoh dari acyclic

Suatu Graph G disebut terhubung jika untuk setiap 2 simpul dari Graph terdapat jalur yang menghubungkan 2 simpul tersebut.

Subgraph yang terhubung pada suatu Graph disebut komponen dari G bila subgraph tersebut tidak terkandung dalam Subgraph terhubung lain yang lebih besar.
Contoh :

GRAPH TERARAH (DIRECTED GRAPH / DIGRAPH)

Graph terarah adalah Graph yang dapat menghubungkan V1 ke V2 saja (1 arah).
Maksimum jumlah busur dari n simpul adalah :  n ( n - 1)
Suatu Graph Berarah (Directed Graph) D terdiri atas 2 himpunan :
1) Himpunan V, anggotanya disebut simpul.
2) Himpunan A, merupakan himpunan pasangan terurut, yang disebut ruas berarah atau arkus.

Contoh, Gambar dibawah ini adalah sebuah Graph Berarah D(V,A) dengan :
1.   V mengandung 4 simpul, yaitu 1, 2, 3 dan 4
2.   A mengandung 7 arkus, yaitu (1,4) ,(2,1), (2,1),(4,2), (2,3), (4,3) dan (2)
     Arkus (2,2) disebut gelung (self-loop), sedangkan arkus (2,1) muncul lebih dari satu kali, disebut arkus sejajar atau arkus berganda.

Bila arkus suatu Graph Berarah menyatakan suatu bobot, maka Graph Berarah tersebut dinamakan jaringan / Network. Biasanya digunakan untuk menggambarkan situasi dinamis.    
Bila V’ himpunan bagian dari V serta A’ himpunan bagian dari A, dengan titik ujung anggota A’ terletak di dalam V’, maka dikatakan bahwa D’(V’,A’) adalah Graph bagian (Subgraph) dari D(V,A). Bila A’ mengandung semua arkus anggota A yang titik ujungnya anggota V’, maka dikatakan bahwa D’(V’,A’) adalah Graph Bagian yang dibentuk atau direntang oleh V’.

GRAPH TAK TERARAH (UNDIRECTED GRAPH)

Graph TAk Terarah adalah Graph yang menghubungkan 2 verteks V1 ke V2 dan V2 ke V1 (2 arah). Bila Verteks = n, maka Graph tak terarah komplit akan mempunyai busur edge sama dengan : n(n-1)/2

CRITICAL PATH

Menggunakan Graph berbobot dan mempunyai Arah

MINIMUM SPANNING TREE

Merupakan Spanning Tree yang mempunyai Bobot dan tidak mempunyai arah dengan hasil penjumlahan bobotnya adalah minimum. Lihat gambar Graph G berikut :

Langkah yang dilakukan untuk membentuk minimum spanning tree adalah :
Bentuk kembali semua simpul tetapi tanpa ruas. Gambar dan telusuri ruas dengan bobot paling kecil, seterusnya (secara ascending) hingga semua simpul terhubung

PENELUSURAN GRAPH
Dapat dilakukan dengan 2 cara, yaitu :
1. Depth First Search (DFS)
2. Breadth First Search (BFS)

• Depth First Search (DFS)

Penelusuran dengan DFS pada Graph TAk Berarah dengan melakukan pengecekan pada Node dengan kedalaman pertama dari Node yang ditinjau.

• Breadth First Search (BFS)

Berbeda dengan cara BFS, dengan BFS penelusuran akan diawasi dari Node-1, kemudian melebar  pada  Adjacent Node   dari   Node-1 dan   diteruskan  pada Node-2, Node- 3 dan seterusnya.

Modul BSI Struktur Data Pertemuan 11

Untuk Download Latihan Soal dan Kunci Jawaban BSI klik Disini
Ketika membuka link klik "SKIP AD" pada pojok kanan atas

Artikel terkait :