GRAPH
1
Konsep
Graph adalah suatu diagram yang memuat informasi tertentu. Contoh :
Struktur organisasi
2
Contoh Graph
Bagan alir pengambilan mata kuliah
3
Contoh Graph
Peta
4
5
Dasar-dasar Graph Suatu graph terdiri dari 2 himpunan berhingga, yaitu himpunan titik/vertex (V(G)) dan himpunan garis/edge (E(G)). Graf yang tidak mempunyai vertex (sehingga tidak mempunyai edge) disebut graf kosong. Jika semua edgenya berarah maka disebut graph berarah (directed graph) Jika semua edgenya tidak berarah disebut graph tak berarah (undirected graph) Edge yang berhubungan dengan satu vertex disebut loop.
6
Dasar-dasar Graph (2)
Dua edge berbeda yang menghubungkan vertex yang sama disebut garis paralel. Dua vertex dikatakan berhubungan (adjacent) jika ada edge yang menghubungkan keduanya. Vertex yang tidak mempunyai edge yang berhubungan dengannya disebut isolated vertex. Sebuah graf yang tidak mempunyai loop dan tidak mempunyai rusuk-rusuk yang sejajar disebut graf sederhana. Jika terdapat sebuah edge e yang menghubungkan verteks v dan w, kita tulis e = (v,w). Dalam konteks ini, (v,w) menyatakan sebuah edge antara v dan w dalam sebuah graph. 7
Graph Berarah
Sebuah graf terarah atau digraf G terdiri dari suatu himpunan V dari verteks dan suatu himpunan E dari edge sedemikian rupa sehingga setiap edge e E menghubungkan pasangan verteks terurut. v1
himpunan verteks-verteks e3 V = {v1, v2, v3, v4, v5} dan himpunan edge v4 E = {e1, e2, e3, e4, e5, e6}
e2 v2
e1
v3
e5 e6 e4
v5
8
Weighted Graph
Sebuah graf dengan bilangan-bilangan pada edge-nya disebut graf berbobot (weighted graph). Dalam sebuah graf berbobot, panjang lintasan adalah jumlah bobot edge dalam lintasan. 8 a
c 2
4 d
3 4
b 6 9
5
12
e 9
Derajat Suatu Titik
Derajat titik v adalah jumlah garis yang berhubungan dengan titik v dan garis suatu loop dihitung 2 kali. Derajat total G adalah jumlah derajat semua titik dalam G
e3
e2
v3
e4 v5
v1
v2 e1
v4
D(v1)=4 D(v2)=2 D(v3)=1
D(v4)=2 D(v5)=1 D(v6)=0
e5 v6
Derajat total = 4+2+1+2+1+0 = 10 10
Walk
Misalkan v0 dan vn adalah verteks-verteks dalam sebuah graf. Sebuah walk dari v0 ke vn dengan panjang n adalah sebuah barisan berselang-seling dari n+1 verteks dan n edge yang berawal dengan verteks v0 dan berakhir dengan verteks vn, (v0, e1, v1, e2, …, vn-1, en, vn) dengan ei insiden pada verteks vi-1 dan vi untuk i = 1,2, …, n.
11
Path dan Sirkuit
Path adalah walk dari v ke w yang semua edgenya berbeda. Path sederhana adalah path dari v ke w yang semua vertexnya berbeda. Sirkuit/cycle adalah path yang dimulai dan diakhiri pada vertex yang sama. Sirkuit sederhana adalah sirkuit yang semua vertexnya berbeda.
12
Contoh e4 e5
v3
v4
e2 e3 v1
e7
v2 e1
e6
e10
e8 v6
e9
v5
Dari graph diatas tentukan barisan vertex dan edge berikut apakah Walk, path, path sederhana, sirkuit, sirkuit sederhana. a. v1 e1 v2 e3 v3 e4 v3 e5 v4 Path dari v1 ke v4 b. v1 e1 v2 e3 v3 e5 v4 e5 v3 e6 v5
Walk dari v1 ke v5
c. v2 e3 v3 e5 v4 e10 v5 e6 v3 e7 v6 e8 v2
Sirkuit
d. v2 e3 v3 e5 v4 e10 v5 e9 v6 e8 v2
Sirkuit sederhana 13
Graph terhubung dan Tidak Terhubung
Dua vertex v dan w dalam G dikatakan terhubung bila dan hanya bila ada walk dari v ke w. Graf G dikatakan terhubung (connected) bila dan hanya bila setiap 2 vertex terhubung. Graf G dikatakan tidak terhubung (unconnected) bila dan hanya bila ada 2 vertex yang tidak terhubung.
Connected Graph
Unconnected graph 14
Euler Path dan Cycle
Euler path adalah sebuah path pada graph G yang melewati setiap edge/garis tepat 1 kali dan melewati setiap vertex/titik paling sedikit sekali. Euler cycle/sirkuit adalah euler path yang kembali ke vertex awal.
15
Permasalahan 7 Jembatan Konigsberg A A B
C
B
C
D D
Masalah : mungkinkah seseorang berjalan mengelilingi kota yang dimulai dan diakhiri pada tempat yang sama, dengan melintasi ketujuh jembatan masing-masing tepat 1 kali ? Apakah graph tersebut merupakan sirkuit EULER ? 16
Teorema Euler
Jika graph G memiliki vertex berderajat ganjil, maka tidak ada euler cycle dalam G. Jika G adalah sebuah connected graph dan setiap vertexnya berderajat genap, maka terdapat EULER CYCLE dalam G. Jika graph G memiliki lebih dari 2 vertex berderajat ganjil, maka tidak ada euler path. Jika G connected graph dan memiliki tepat 2 vertex berderajat ganjil, maka ada EULER PATH yang berawal di satu vertex berderajat ganjil dan berakhir di vertex berderajat ganjil lainnya. 17
Contoh E
Euler path : E–D–B–A–C–D
D B
C A
2
4 3
1
Euler cycle : 1–3–4–5–3–2–1
5
18
Algoritma Fleury
Algoritma untuk mencari EULER CYCLE dalam sebuah connected graph yang tidak memiliki vertex berderajat ganjil. Langkah-langkah :
Pilih sembarang vertex (v). Dari v, pilih sebuah edge yang bukan merupakan cut edge (bridge). Beri tanda pada edge tersebut. Melalui edge tersebut, telusuri vertex lainnya. Ulangi langkah 2 dan 3 hingga semua edge terlewati dan berakhir di vertex awal (v).
19
A
B
Contoh
D
C
F
E A
B D
C E A
E A
B
E
A
B
F
E A
E
A
B
F
F B D
C
F
D
C
E
B
B D
C
F
D
C
F
D
C
E
A
B D
C
F
D
C
A
E A
F B D
C E
F 20
Hamilton Path dan Cycle
Hamilton path adalah path dalam sebuah graph yang melewati tiap vertex tepat 1 kali dan tidak harus melalui semua garis. Hamilton cycle adalah hamilton path yang kembali ke titik awal Graph yang mengandung hamilton cycle tidak memiliki loop dan multiple edge
21
Contoh E
Hamilton path : E-D-C-A-B
D B
C A
A
B
Hamilton cycle : A-B-C-D-A D
C
22
Teorema Hamilton
Jiia graph G memiliki hamilton cycle maka setiap vertex berderajat : d(v) >= n/2, n adalah jumlah vertex Misal m adalah jumlah edge pada G. Jika graph G memiliki hamilton cycle maka : m >= ½(n2-3n+6)
23
Masalah Perjalanan Wiraniaga
Jika kita menganggap verteks-verteks dalam graf berbobot sebagai kota dan bobot edge sebagai jarak, masalah perjalanan wiraniaga adalah mencari sebuah rute terpendek sehingga wiraniaga tersebut dapat mengunjungi setiap kota satu kali, berawal dan berakhir pada kota yang sama.
2
a
3
11 d
3
Panjang
(a, b, c, d, a) (a, b, d, c, a) (a, c, b, d, a) (a, c, d, b, a) (a, d, b, c, a) (a, d, c, b, a)
2+3+3+2 = 10 2+11+3+11 = 27 11+3+11+2 = 27 11+3+11+2 = 27 2+11+3+11 = 27 2+3+3+2 = 10
b 11
2
Siklus Hamilton
c
Kita lihat bahwa siklus Hamilton (a, b, c, d, a) dan (a, d, c, b, a) merupakan siklus Hamilton dengan panjang minimum untuk G. 24
Shortest Path Problem
Suatu permasalahan untuk mendapatkan path terpendek dari suatu titik awal ke titik akhir. Contoh : sebuah perusahaan telepon akan memasang kabel telepon yang akan menghubungkan beberapa kota. Cari jalur terpendek yang menghubungan seluruh kota tersebut. Algoritma penyelesaian :
Warshall Dijkstra
Menggunakan weighted graph, yaitu graph yang edge-nya memiliki bobot/nilai (misal : biaya, waktu, jarak, dsb). 25
Algoritma Dijkstra 1. 2.
3. 4.
5.
6.
Buat tabel, kolom berisi semua vertex dalam graph. Isi baris pertama dengan nilai NOL untuk vertex awal, vertex lain yang beradjacent dengan vertex awal = bobot edgenya dan ~ untuk vertex lain yang tidak beradjacent dengan vertex awal. Lalu beri label yang berisi path dari setiap vertex tersebut. Pilih bobot vertex yang paling kecil dan beri tanda, Pilih vertex yang beradjacent dengan vertex terpilih, yang belum pernah dilalui dan hitung bobotnya. Tulis label yang berisi path yang telah dilalui pada tiap bobot vertex yang beradjacent Ulangi langkah 3-5 sampai semua vertex dalam graph dilalui.
26
c
Contoh
7
b
c
d
e
f
3 7
2
a
5
1 2 8a
b
e
2
3
4
4
d
6
g
h
1
f
h
3 4
6 g
Visited vertex a
1 (ac) 4(ad) 2 (ae)
7(af)
~
~
c
-
4 (ad) 2 (ae)
7 (af)
~
4(ach)
e
8 (ab)
-
4 (ad)
-
7(af)
~
3 (aeh)
h
0
8 (ab)
-
4 (ad)
-
6 (aehf)
9(aehg)
-
d
0
6 (adb)
-
-
-
6 (aehf)
9(aehg)
-
b
0
-
-
-
-
6 (aehf)
9(aehg)
-
f
0
-
-
-
-
-
9(aehg)
-
g
0 (a)
8 (ab)
0
8 (ab)
0
27
Latihan 1. Untuk graf G = (V,E) dalam Gambar berikut a
b e
d
c
Nyatakan apakah lintasan yang diberikan dalam graf tersebut merupakan sebuah path sederhana, sebuah cycle, sebuah cycle sederhana. a. (b,b) d. (a,d,c,b,e) b. (a,b,c,d,e) e. (d,c,b) c. (b,c,d,a,b,e,d,c,b) f. (e,d,c,d) 6. 28
Latihan 2. Misalkan graf G = (V,E) Buktikan
bahwa G mempunyai siklus Euler. Carilah sebuah siklus Euler untuk G. v1 v2 v5
v3 v6
v4
v7
29
Latihan 3. Untuk graf tak terarah G terdiri dari himpunan verteks-verteks V = {a, b, c, d, e, f, g, h, i, j}dan himpunan rusuk-rusuk E = {(a,b), (b,c), (c,h), (h,j), (j,i), (i,d), (d,a), (a,e), (e,b), (b,g), (g,c), (a,i), (i,e), (e,f), (f,g), (g,h), (i,f), (f,j)}. a. Gambarlah graf G. b. Carilah sebuah siklus Hamilton.
30
Latihan 4.
Carilah panjang lintasan terpendek dan sebuah lintasan terpendek di antara setiap pasang verteks dalam graf berbobot tersambung tersebut. 1. a, f 2. a, g 3. a, z 4. b, j 5. h, d
b 3 a
5 e
5 4
2 5
c 2 f
4 7 h
5 2
3 6
d 7 g
2
4 4 i
3 6
6 4 j
z
5 31
