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).
Banyak 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:
G' Subgraph dari G'
(namun bukan dibentuk oleh V'={A,B,D})
Contoh Spanning Sub Graph :
G' Subgraph yang dibentuk oleh V'={A,B,}
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 disamping Jumlah Semua Simpul = 4, maka
Jumlah
Derajat Semua Simpul = 8
Jika
Derajat masing-masing simpul pada Graph berjumlah
Genap
maka Graph tersebut disebut EULER Gr aph.
Suatu simpul disebut genap/ganjil tergantung
apakah derajat simpul tersebut genap/ganjil.
Kalau
terdapat self-loop, maka 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 tertutup, yg 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 yang
tertutup dengan setiap simpul = 2 Cycle dengan panjang k disebut
dengan k-cycle. Demikia pula jalur dengan panjang k disebut k-jalur.
Contoh :
>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 Graph terhadap jalur yang mengubungkan 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 :
Terlihat
misalnya antara D dan A Tak ada jalur.
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 dirent tang oleh V'.
GRAPH
TAK TERARAH (UNDIRECTED GRAPH)
Graph Tak Terarah adalah Graph yang
menghubungkan 2 verteks V1 dan V2 dan V2 ke V1 (2 arah) mempunyai
busur edge sama dengan :
CRITICAL
PATH
Menggunakan Graph berbobot dan Mempunyai Arah
Simpul asal : 1
Simpul Tujuan : 5
|
|
PATH
|
BOBOT
|
|
Alternatif :
|
1-->4-->5
|
16
|
|
|
1-->2-->5
|
15
|
|
|
1-->2-->3-->5
|
24
|
|
|
1-->4-->3-->5
|
19
|
|
|
1-->2-->3-->4-->5
|
29
|
|
|
1-->4-->3-->2-->5
|
22
|
Diproleh : Critical Path (Lintasan Kritis) = 29
Shortest Path (Lintasan Terpendek) = 15
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
Total Minimum
Spanning Tree = 22
PENULISAN
GRAPH
Dapat dilakukan dengan 2 cara, yaitu :
1.Depth First Search (DFS)
2.Breadth First Search (BFS)
1.Depth
First Search (DFS)
Penelusuran
dengan DFS pada Graph Tak Berarah dengan melakukan pengecekan pada
Node dengan kedalaman pertaman dari Node yang ditinjau.
2.
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.
|
Dari gambar di atas akan diperoleh urutan :
V1 , V2 ---> V3
, V4 ---> V5 ---> V6 ---> V7,
V8
|
>Sekian... :)
