GRAF
description
Transcript of GRAF
GRAFGRAFGRAFGRAF
Matematika DiskritMatematika Diskrit
Matematika Diskrit 2
Pendahuluan
• Graf digunakan untuk merepresentasikan objek-objek diskrit dan hubungan antara objek-objek tersebut
• Representasi :• Objek : noktah, bulatan atau titik• Hubungan antar objek : garis
D
C
B
A
Matematika Diskrit 3
Definisi • Graf G didefinisikan sebagai pasangan himpunan (V,E)• Ditulis dengan notasi :
G = (V, E)V = himpunan tidak kosong dari simpul-simpul (vertices atau node)E = himpunan sisi (edges atau arcs) yang menghubungkan sepasang simpul
• Graf trivial adalah : Graf hanya mempunyai satu buah simpul tanpa
sebuah sisi• Simpul pada graf dinomori dengan :
Huruf (a,b, …,z) atau Bilangan (1, 2, … ) atau Huruf dan bilangan (a1, a2, …. )
• Sisi yang menghubungkan simpul u dan simpul v dinyatakan dengan pasangan (u,v) atau dinyatakan dengan e1, e2, …. Sehingga dapat ditulis :
e = (u,v)
Matematika Diskrit 4
Contoh 1
• G1 adalah graf dengan himpunan simpul V dan himpunan sisi E :
V = {1, 2, 3, 4}E = {(1,2), (1,3), (2,3), (2,4), (3,4)}
1
32
4
Graf sederhana
Matematika Diskrit 5
Contoh 2• G2 adalah graf dengan himpunan simpul V dan
himpunan sisi E :V = {1, 2, 3, 4}E = {(1,2), (2,3), (1,3), (1,3), (2,4), (3,4),
(3,4)} = {e1, e2, e3, e4, e5, e6, e7}
1
32
4
e2
e5
e1e4
e7
e3
e6
Graf ganda
• Pada G2 : sisi e3 = (1,3) dan sisi e4 = (1,3) dinamakan sisi ganda (multiple edges atau paralel edges)
Himp. Ganda
Matematika Diskrit 6
Contoh 3• G3 adalah graf dengan himpunan simpul V dan
himpunan sisi E :V = {1, 2, 3, 4}E = {(1,2), (2,3), (1,3), (1,3), (2,4), (3,4), (3,4),
(3,3)} = {e1, e2, e3, e4, e5, e6, e7, e8}
1
3
2
4
e2
e5
e1e4
e7
e3
e6
e8
Graf semu
• Pada G3 : e8 = (3,3) dinamakan gelang atau kalang (loop)
Himp. Ganda
Matematika Diskrit 7
Jenis-jenis Graf
Berdasarkan ada atau tidaknya gelang :• Graf sederhana (simple graph)
Graf tidak mengandung gelang maupun sisi ganda Sisi adalah pasangan tak terurut (unordered pairs)
• Graf tak-sederhana (unsimple graph) Graf yang mengandung sisi ganda atau gelangAda 2 macam graf tak-sederhana : Graf ganda (multigraph)
Graf yang mengandung sisi ganda, sisi ganda yang menghubungkan sepasang simpul bisa lebih dari dua buah
Graf semu (pseudograph)Graf yang mengandung gelang (loop), sisi graf semu
terhubung ke dirinya sendiri
Matematika Diskrit 8
Jenis-jenis Graf (Cont.)Berdasarkan orientasi arah pada sisi :• Graf tak-berarah (undirected graph)
Graf yang sisinya tidak mempunyai orientasi arah Urutan pasangan simpul yang dihubungkan oleh sisi
tidak diperhatikan
• Graf berarah (directed graph atau digraph) Graf yang setiap sisinya diberikan orientasi arah Biasanya disebut dengan busur (arc)Busur (u,v) : Simpul u = simpul asal (initial vertex) Simpul v = simpul terminal (terminal vertex)
Matematika Diskrit 9
Jenis-jenis Graf (Cont.)
Jenis Sisi Sisi ganda
Sisi gelang
Graf sederhana
Tak berarah Tidak Tidak
Graf ganda Tak berarah Ya Tidak
Graf semu Tak berarah Ya Ya
Graf berarah Berarah Tidak Ya
Graf ganda-berarah
Berarah Ya Ya
Matematika Diskrit 10
Kardinalitas Graf
• Kardinalitas graf adalah : Jumlah simpul pada graf
• Dinyatakan dengan :n = |V|
• Jumlah sisi dinyatakan dengan :m = |E|
Matematika Diskrit 11
Terminologi (Istilah) Dasar
• Adjacent (bertetangga)• Incident (bersisian)• Isolated vertex (simpul terpencil)• Null graph atau empty graph (graf kosong)• Degree (derajat)• Path (lintasan)• Cycle (siklus) atau circuit (sirkuit)• Connected (terhubung)• Subgraph (upagraf) dan Komplemen Upagraf• Spanning subgraph (upagraf merentang)• Cut – set• Weigted graph (graf berbobot)
Matematika Diskrit 12
Adjacent (bertetangga)
• Dua buah simpul pada graf tak berarah G dikatakan bertetangga bila keduanya terhubung langsung dengan sebuah sisi.
• Contoh :
simpul 1 bertetangga dengan simpul 2 dan 3 tetapi simpul 1 tidak bertetangga dengan simpul 4
1
32
4
Matematika Diskrit 13
Incident (bersisian)
• Untuk sembarang sisi e = (u,v), sisi e dikatakan bersisian dengan simpul u dan simpul v
• Contoh :
sisi (2,3) bersisian dengan simpul 2 dan simpul 3, sisi (2,4) bersisian dengan simpul 2 dan simpul 4 tetapi sisi (1,2) tidak bersisian dengan simpul 4
1
32
4
Matematika Diskrit 14
Isolated vertex (simpul terpencil)
• Simpul terpencil adalah simpul yang tidak mempunyai sisi yang bersisian dengannya.
• Dapat juga dinyatakan bahwa simpul terpencil adalah simpul yang tidak satupun bertetangga dengan simpul-simpul lainnya
• Contoh :
Simpul 5 adalah simpul terpencil
5
43
2
1
Matematika Diskrit 15
Null graph atau empty graph (graf kosong)
• Graf yang himpunan sisinya merupakan himpunan kosong disebut sebagai graf kosong
• Ditulis sebagai :Nn , n = jumlah simpul
• Contoh :
graf di atas adalah graf kosong N5
1
24
3
5
Matematika Diskrit 16
Degree (derajat)
• Derajat suatu simpul pada graf tak berarah adalah jumlah sisi yang bersisian dengan simpul tersebut
• Notasi :d(v) menyatakan derajat simpul v
• Contoh :
d(1) = d(4) = 2d(2) = d(3) = 3
• Sisi terpencil adalah simpul dengan d(v) = 0 karena tidak satupun sisi yang bersisian dengan simpul tersebut
• Sisi gelang (loop) dihitung berderajat dua• Jika terdapat g buah gelang dan e buah sisi bukan
gelang yang bersisian dengan simpul v maka derajat simpul v adalah :
d(v) = 2g + e
1
32
4
Matematika Diskrit 17
Degree (derajat)
• Simpul yang berderajat satu disebut anting-anting (pendant vertex)
• Pada graf berarah, derajat simpul v dinyatakan dengan din(v) dan dout(v), dalam hal ini :
din(v) = derajat masuk (in-degree) = jumlah busur yang masuk ke simpul v
dout(v) = derajat keluar (out-degree) = jumlah busur yang keluar dari simpul v
Dan d(v) = din(v) + dout(v)
Matematika Diskrit 18
Contoh • Derajat setiap simpul :
din(a) = 2 ; dout(a) = 1 din(b) = 2 ; dout(b) = 3 din(c) = 1 ; dout(c) = 2 din(d) = 2 ; dout(d) = 1
• Pada graf berarah G = (V,E) selalu berlaku hubungan :
• Sehingga :
b
d
a
c
EvdvdVv
outVv
in
EvdvdVv
outVv
in
712312122
Matematika Diskrit 19
Path (lintasan)
• Lintasan yang panjangnya n dari simpul awal vo ke simpul tujuan vn di dalam graf G adalah barisan berselang-seling simpul-simpul dan sisi-sisi yang berbentuk vo, e1, v1, e2, v2, …, vn-1, en, vn sedemikian sehingga e1 = (vo, v1), e2 = (v1, v2), …, en = (vn-1, vn) adalah sisi-sisi dari graf G
• Lintasan sederhana (simple path) : Jika semua simpulnya berbeda (setiap sisi yang dilalui hanya
sekali)• Lintasan tertutup (closed path) :
Lintasan yang berawal dan berakhir pada simpul yang sama• Lintasan terbuka (opened path) :
Lintasan yang tidak berawal dan berakhir pada simpul yang sama
• Panjang lintasan : Jumlah sisi dalam lintasan tersebut
Matematika Diskrit 20
Contoh
• Lintasan 1,2,4,3 adalah lintasan sederhana dan terbuka
• Lintasan 1,2,4,3,1 adalah lintasan sederhana dan tertutup
• Lintasan 1,2,4,3,2 bukan lintasan sederhana tetapi lintasan terbuka
• Lintasan 1,2,4,3 memiliki panjang lintasan = 3
1
32
4
Matematika Diskrit 21
Cycle (siklus) atau circuit (sirkuit)
• Lintasan yang berawal dan berakhir pada simpul yang sama disebut sirkuit atau siklus
• Sirkuit sederhana (simple circuit) : jika setiap sisi yang dilalui berbeda
• Contoh :• Lintasan 1,2,3,1 sirkuit sederhana• Lintasan 1,2,4,3,2,1 bukan sirkuit
sederhana karena sisi (1,2) dilalui 2 kali
Matematika Diskrit 22
Connected (terhubung)
• Graf tak-berarah G disebut graf terhubung (connected graph) jika untuk setiap pasang simpul u dan v di dalam himpunan V terdapat lintasan dari u ke v (yang juga harus berarti ada lintasan dari u ke v)
• Graf berarah G dikatakan terhubung jika graf tak berarahnya terhubung (graf tak berarah dari G diperoleh dengan menghilangkan arahnya)
• Graf berarah G disebut terhubung kuat (strongly connected) jika untuk setiap pasang simpul sembarang vi dan vj di G terhubung kuat
Matematika Diskrit 23
Contoh
• Graf di samping merupakan graf terhubung kuat karena untuk sembarang sepasang simpul di dalam graf terdapat lintasan
• Graf di samping merupakan graf terhubung lemah karena tidak semua pasangan simpul mempunyai lintasan dari dua arah
2
3
5
4
1
2
3
5
4
1
Matematika Diskrit 24
Subgraph (upagraf) dan Komplemen Upagraf
• Misalkan G = (V,E) adalah sebuah graf. G1 = (V1, E1) adalah upagraf (subgraph) dari G jika V1 V dan E1 E
• Komplemen dari upagraf G1 terhadap G adalah graf G2 = (V2, E2) sedemikian sehingga E2 = E - E1 dan V2 adalah himpunan simpul yang anggota-anggota E2 bersisian dengannya
2
3
54
1
6
3
54
1
2
3
5
1
6
Upagraf dari G1Graf G1
Komplemen dari upagrafyang bersesuaian
Matematika Diskrit 25
Contoh
• Tentukan komponen terhubung dari G = (V,E) dimana V = {a,b,c,d,e,f} dan E = {(a,d),(c,d)}Penyelesaian :simpul a bertetangga dengan d sedangkan simpul d bertetangga dengan c, ini berarti a juga terhubung dengan c. Simpul b,e dan f merupakan simpul terpencil. Sehingga ada : G1 = (V1, E1) dengan V1 = {a,c,d} dan E1 = {(a,d),(c,d)} G2 = (V2, E2) dengan V2 = {b} dan E2 = { } G3 = (V3, E3) dengan V3 = {e} dan E3 = { } G4 = (V4, E4) dengan V4 = {f} dan E4 = { }Dan V1 V2 V3 V4 = V E1 E2 E3 E4 = E G1 V2 V3 V4 =
d
c
e
b
a
f
Matematika Diskrit 26
Spanning subgraph (upagraf merentang)
• Upagraf G1 = (V1, E1) dan G = (V,E) dikatakan upagraf merentang jika = V1 = V (yaitu G1 mengandung semua simpul dari G)
2 3
54
1
2 3
54
1
Upagraf merentang dari GGraf G
2 3
1
Bukan upagraf merentang dari G
Matematika Diskrit 27
Cut – set
• Cut set dari graf terhubung G adalah himpunan sisi yang bila dibuang dari G menyebabkan G tidak terhubung
• Cut set selalu menghasilkan 2 buah komponen terhubung
• Nama lain : jembatan (bridge) adalah himpunan sisi apabila dibuang dari graf
menyebabkan graf tersebut tidak terhubung (menjadi 2 buah komponen terhubung)
Matematika Diskrit 28
Contoh
• Sisi (1,2) dibuang, graf tetap terhubung• Jika sisi (1,2) dan (1,5) dibuang, graf tetap terhubung• Jika sisi dari himpunan {(1,2),(1,5),(3,5),(3,4)} dibuang,
graf tidak terhubung cut-set• Cut-set terjadi pada himpunan :
{(1,2),(1,5),(3,5),(3,4)} {(1,2),(2,5)} {(1,3),(1,5),(1,2)} {(2,6)}
12
43
65
12
43
65
12
43
65
Himpunan {(1,2),(1,5),(3,5),(3,4)} adalah cut-set
Matematika Diskrit 29
Weigted graph (graf berbobot)
• Graf berbobot adalah graf yang setiap sisinya diberi sebuah harga (bobot)
• Bobot pada tiap sisi berbeda-beda tergantung pada masalah yang dimodelkan dengan graf
• Bobot dapat menyatakan : Jarak antara 2 kota Biaya perjalanan antara 2 kota Waktu tempuh pesan (message) dari sebuah simpul
komunikasi ke simpul komunikasi lain Ongkos produksi dll
• Istilah lain : graf berlabel
e b
cd
a
12
9
8
10
15
14
11
Matematika Diskrit 30
Graf Sederhana Khusus
• Complete graph (Graf lengkap)• Graf lingkaran• Regular graph (Graf teratur)• Bipartite graph (Graf bipartit)
Matematika Diskrit 31
Complete Graph (Graf Lengkap)
• Adalah graf sederhana yang setiap simpulnya mempunyai sisi ke semua simpul lainnya.
• Graf lengkap dengan n buah simpul dilambangkan dengan Kn
• Setiap simpul pada Kn berderajat n-1• Jumlah sisi :
K1 K2 K3K4 K5 K6
Graf lengkap Kn , 1 n 6
2
1nn
Matematika Diskrit 32
Graf Lingkaran
• Adalah graf sederhana yang setiap simpulnya berderajat 2
• Graf lingkaran dengan n simpul dilambangkan dengan : Cn
• Jika simpul-simpul pada Cn adalah v1, v2, …, vn, maka sisi-sisinya adalah :
(v1, v2), (v2, v3), …, (vn-1, vn) dan (vn, v1)• Ada sisi simpul dari simpul terakhir, vn, ke simpul
pertama, v1
Graf lingkaran Cn , 3 n 6
Matematika Diskrit 33
Regular graph (Graf teratur)
• Adalah : graf yang setiap simpulnya mempunyai derajat yang sama
• Jika derajat setiap simpul adalah r maka graf tersebut disebut sebagai graf teratur derajat r
• Jumlah sisi pada graf teratur derajat r dengan n buah simpul adalah :
Derajat 0 Derajat 1 Derajat 2
2
rn
Matematika Diskrit 34
Contoh (1)
i. Grafteratur berderajat 3 dengan 4 buah simpulii. Graf teratur berderajat 3 dengan 6 buah simpuliii. Graf teratur berderajat 3 dengan 8 buah simpul
(i) n = 4, r = 3 (ii) n = 6, r = 3 (iii) n = 8, r = 3
Matematika Diskrit 35
Contoh (2)
Berapa jumlah maksimum dan jumlah minimum simpul pada graf sederhana yang mempunyai 12 buah sisi dan setiap simpul berderajat sama yang 3 ?
Penyelesaian :• Tiap simpul berderajat sama berarti graf teratur• e = 12, r 3 • Jumlah sisi pada graf teratur berderajat r adalah e = nr/2 n = 2e/r
= 2 * 12/r = 24/r• Sehingga :
r = 3 n = 24/3 = 8 maksimum r = 4 n = 24/4 = 6 minimum r = 6 n = 24/6 = 4 tidak mungkin membentuk graf
sederhana r = 8 n = 24/8 = 3 tidak mungkin membentuk graf
sederhana r = 12 n = 24/12 = 2 tidak mungkin membentuk graf
sederhana r = 24 n = 24/24 = 1 tidak mungkin membentuk graf
sederhana• Jadi jumlah simpul paling sedikit (minimum) = 6 buah dan paling
banyak (maksimum) = 8 buah
Matematika Diskrit 36
Bipartite graph (Graf bipartit)
• Adalah graf G yang himpunan simpulnya dapat dikelompokkan menjadi 2 himpunan bagian V1 dan V2, sedemikian hingga setiap sisi di dalam G menghubungkan sebuah simpul di V1 ke sebuah simpul di V2
• Dinyatakan sebagai G(V1, V2)• Graf bipartit lengkap (complete bipartite graph) adalah :
Jika setiap simpul di V1 bertetangga dengan semua simpul di V2 • Dilambangkan dengan Km,n • Jumlah sisi : mn
V1 V2
Graf bipartit G(V1, V2)
Matematika Diskrit 37
Contoh (1)
• V1 = {a,b,d} dan V2 = {c,e,f,g}
• Setiap sisi menghubungkan simpul di V1 ke simpul V2
• Sehingga bentuk graf bipartit C6 adalah :a b
d
c
e
f
g
Matematika Diskrit 38
Contoh (2)
• Graf bipartit lengkap K2,3 , K3,3 dan K2,4 adalah :
K2,3K3,3 K2,4
Matematika Diskrit 39
Representasi Graf
• Adjacency matrix (matriks ketetanggaan)
• Incidency matrix (matriks bersisian)• Adjacency list (senarai ketetanggaan)
Matematika Diskrit 40
Adjacency matrix (matriks ketetanggaan)
• Adalah matriks dwimatra yang berukuran n x n• Jika A = [aij] maka aij = 1 simpul i dan j
bertetanggaan• Jika aij = 0 simpul i dan j tidak bertetanggaan• Matriks ketetanggaan berisi 0 dan 1 matriks nol-satu
(zero-one)• Matriks ketetanggaan untuk graf sederhana dan tidak
berarah selalu simetri• Matriks ketetanggaan untuk graf berarah belum tentu
simetri (akan simetri jika berupa graf berarah lengkap)• Matriks ketetanggaan tidak dapat digunakan untuk
merepresentasikan graf yang mempunyai sisi ganda (graf ganda)
• Untuk matriks semu, gelang pada simpul vi dinyatakan dengan nilai 1 pada posisi (i,i) di matriks ketetanggaan
Matematika Diskrit 41
Contoh
1
2 3
4
0110
1011
1101
0110
4
3
2
1
4321
1
2
3 4
5
1
2 3
4
00000
00100
01011
00101
00110
5
4
3
2
1
54321
0110
0001
1101
0010
4
3
2
1
4321
0210
2112
1101
0210
4
3
2
1
4321
1
2
3
4
e1
e2
e4
e5e7
e6e8
e3
Matematika Diskrit 42
Adjacency matrix• Jumlah elemen matriks ketetanggaan untuk graf dengan
n simpul adalah :n2
• Jika tiap elemen membutuhkan ruang memori sebesar p, maka ruang memori yang diperlukan seluruhnya adalah :
p n2
• Matriks ketetanggaan untuk graf tak-berarah sederhana simetri membutuhkan ruang memori :
p n2 / 2• Derajat tiap simpul i dapat dihitung
Untuk graf tak-berarah :
Untuk graf berarah :
n
jiji avd
1
n
iijjin ajkolompadanilaijumlahvd
1
n
jijiout aibarispadanilaijumlahvd
1
Matematika Diskrit 43
Contoh • Derajat matriks simpul 2 adalah :
1 + 0 + 1 + 1 = 3• Derajat matriks simpul 4 adalah :
0 + 1 + 1 + 0 = 2
• Derajat matriks simpul 4 adalah :0 + 0 + 1 + 0 + 0 = 1
• Derajat matriks simpul 5 adalah : 0 + 0 + 0 + 0 + 0 = 0
• Derajat masuk matriks simpul 2 adalah :1 + 0 + 0 + 1 = 2
• Derajat keluar matriks simpul 2 adalah : 1 + 0 + 1 + 1 = 3
1
2 3
4
1
2
3 4
5
1
2 3
4
Matematika Diskrit 44
Incidency matrix (matriks bersisian)
• Adalah matriks dwimatra yang berukuran n x m• Baris menunjukkan label simpul• Kolom menunjukkan label sisinya• Jika A = [aij] maka aij = 1 simpul i bersisian dengan sisi j• Jika aij = 0 simpul i tidak bersisian dengan sisi j• Digunakan untuk merepresentasikan graf yang
mengandung sisi ganda atau sisi gelang (loop)• Derajat setiap simpul i adalah : jumlah seluruh elemen
pada baris i (kecuali pada graf yang mengandung gelang)• Jumlah elemen matriks bersisian :
nm• Jika tiap elemen membutuhkan ruang memori sebesar p,
maka ruang memori yang diperlukan adalah : pnm
Matematika Diskrit 45
Contoh
Jumlah elemen matriks adalah 4 x 6 = 24
1 2
3
e1
4
e2
e3e4
e5
e6
110000
011100
000111
001011
4
3
2
1654321 eeeeee
Matematika Diskrit 46
Adjacency list (senarai ketetanggaan)
• Senarai ketetanggaan mengenumerasi simpul-simpul yang bertetangga dengan setiap simpul di dalam graf
1
2 3
4
1
2
3 4
5
1
2 3
4
Senarai ketetanggaan :1 : 2,32 : 1,3,43 : 1,2,44 : 2,3
Senarai ketetanggaan :1 : 2,32 : 1,33 : 1,2,44 : 35 : -
Senarai ketetanggaan :1 : 22 : 1,3,43 : 14 : 2,3
Matematika Diskrit 47
Isomorphic Graph (graf isomorfik)
• Dua buah graf, G1 dan G2 dikatakan isomorfik jika terdapat korespondensi satu-satu antara simpul-simpul keduanya dan antara sisi-sisi keduanya sedemikian hingga jika sisi e bersisian dengan simpul u dan v di G1, maka sisi e’ yang berkoresponden di G2 juga harus bersisian dengan simpul u’ dan v’ di G2
• G1 isomorfik dengan G2. Simpul 1,2,3 dan 4 di G1 berkoresponden dengan simpul a,b,c dan d di G2 . Sisi (1,2), (2,3), (3,1), (3,4), (1,4) dan (2,4) berkoresponden dengan sisi (a,b), (b,c), (c,d), (a,d), (a,c) dan (b,d). Semua simpul di G1 dan G2 berderajat 3
• G1 dan G2 tidak isomorfik dengan G3 karena simpul-simpul di G3 2 buah berderajat 2 dan 2 buah berderajat 3, sedangkan G1 dan G2 berderajat 3
1 2
3
4
G1 G2 G3a b
cd
x y
wv
Matematika Diskrit 48
Contoh
• Simpul a,b,c,d dan e di G1 masing-masing berkoresponden dengan simpul x, y, w, v dan z di G2
• Masing-masing simpul berderajat 3, 2, 3, 3 dan 1
a
b c
d
e
G1 G2
v
x
z
y
w
Matematika Diskrit 49
• Dua buah graf isomorfik harus memenuhi syarat :1. Mempunyai jumlah simpul yang sama2. Mempunyai jumlah sisi yang sama3. Mempunyai jumlah simpul yang sama berderajat tertentu
• Untuk memeriksa graf isomorfik, digunakan bantuan matriks ketetanggaan (adjacency matrix)
Isomorphic Graph (graf isomorfik)
a
b cd
eG1
G2 v
x
z
y
w
01000
10101
01011
00101
01110
1
e
d
c
b
a
A
edcba
G
01000
10101
01011
00101
01110
2
e
d
c
b
a
A
zvwyx
G
Matematika Diskrit 50
Graf Planar
• Graf planar adalah : Graf yang dapat digambarkan pada bidang datar
dengan sisi-sisi yang tidak saling memotong (bersilangan)
K4 adalah graf planar
K5 bukan graf planar
Matematika Diskrit 51
Graf Datar• Graf datar adalah :
Representasi graf planar yang digambarkan dengan sisi-sisi yang tidak saling berpotongan
• Sisi-sisi pada graf bidang membagi bidang datar menjadi beberapa wilayah (region) atau muka (face)
Graf planar dan graf bidangBukan graf bidang tetapi graf planar
Jumlah wilayah pada graf bidang = 4, R1, R2, R3 dan R4
R1 R2
R3 R4
Matematika Diskrit 52
Rumus Euler
• Jumlah wilayah (f) pada graf planar sederhana dapat dihitung dengan rumus Euler
n – e + f = 2 f = e – n + 2dimana :
e = jumlah sisin = jumlah simpul
• Lemma jabat tangan :jumlah derajat = 2 x jumlah sisi
r = 2 x e e = r / 2
Matematika Diskrit 53
Contoh (1)
• Pada gambar di atas : Jumlah sisi (e) = 9 Jumlah simpul (n) = 6
• Sehingga jumlah wilayah (f) pada graf bidang tersebut adalah :
f = e – n + 2 = 9 – 6 + 2f = 5
R1 R2
R3 R4
Matematika Diskrit 54
Contoh (2)
• Graf planar sederhana dan terhubung memiliki 24 buah simpul, masing-masing simpul berderajat 4. Representasi planar dari graf tersebut membagi bidang datar menjadi sejumlah wilayah atau muka. Berapa banyak wilayah yang terbentuk ?
• Penyelesaian : Diketahui n = 24 ; r = 4 Maka jumlah derajat seluruh simpul = 24 x 4 = 96Sehingga jumlah sisi (e), menurut lemma jabat tangan :
e = jumlah derajat / 2 = 96 / 2 = 48Jadi jumlah wilayah (f) pada graf planar sederhana :
f = e – n + 2 = 48 – 24 + 2f = 26
Matematika Diskrit 55
Ketidaksamaan Euler
• Pada graf planar sederhana dan terhubung dengan f wilayah, n buah simpul dan e buah sisi (dengan e > 2) berlaku :
e 3f/2 f 2e/3• Berdasarkan rumus Euler maka :
n – e + f 2n – e + 2e/3 23n – 3e + 2e 63n – e 6e 3n - 6
• Ketidaksamaan Euler digunakan untuk menunjukkan keplanaran suatu graf sederhana
• Jika G adalah graf sederhana terhubung dengan e adalah jumlah sisi dan v adalah jumlah simpul, dalam hal ini v 3, maka berlaku ketidaksamaan Euler, e 3v - 6
Matematika Diskrit 56
Ketidaksamaan Euler
• Pada graf planar sederhana dan terhubung dengan f wilayah, n buah simpul dan e buah sisi (dengan e > 2) berlaku :
e 4f/2 f e/2• Berdasarkan rumus Euler maka :
n – e + f 2n – e + e/2 22n – 2e + e 42n – e 4e 2n - 4
• Jika G adalah graf sederhana terhubung dengan e adalah jumlah sisi dan v adalah jumlah simpul, dalam hal ini v 3 dan tidak ada sirkuit yang panjangnya 3, maka berlaku ketidaksamaan Euler, e 2v - 4
Matematika Diskrit 57
Contoh (1)
• Pada graf K4 :n = 4 ; e = 6
Ketidaksamaan Euler :e 3n – 66 3 (4) – 66 6 terpenuhi
K4 merupakan graf planar
K5K4
• Pada graf K5 :n = 5 ; e = 10
Ketidaksamaan Euler :e 3n – 610 3 (5) – 610 9 tidak
terpenuhi K5 merupakan graf bukan planar
Matematika Diskrit 58
Contoh (2)
• Pada graf K3,3 :n = 6 ; e = 9
Ketidaksamaan Euler :e 2n – 49 2 (6) – 49 8 tidak terpenuhi
K3,3 merupakan graf bukan planar
K3,3
Matematika Diskrit 59
Teorema Kuratowski
• Graf Kuratowski I, yaitu graf lengkap yang mempunyai 5 buah simpul (K5) adalah graf tidak planar
• Graf Kuratowski II, yaitu graf terhubung teratur dengan 6 buah simpul dan 9 buah sisi (K3,3) adalah graf tidak planar
• Sifat graf Kuratowski : Kedua graf Kuratowski adalah graf teratur Kedua graf Kuratowski adalah graf tidak planar Penghapusan sisi atau simpul dari graf Kuratowski menyebabkan
menjadi graf planar Graf Kuratowski I adalah graf tidak planar dengan jumlah simpul
minimum dan graf Kuratowski II adalah graf tidak planar dengan jumlah sisi minimum. Keduanya graf tidak planar paling sederhana
• Graf G adalah tidak planar jika dan hanya jika mengandung upagraf yang isomorfik dengan K5 atau K3,3 atau homeomorfik (homeomorphic) dengan salah satu dari keduanya
K3,3G Graf G tidak planar karena mengandung upagraf K3,3
Matematika Diskrit 60
Homeomorphic (homeomorfik)
• Dua graf G1 dan G2 dikatakan homeomorfik jika salah satu dari kedua graf dapat diperoleh dari graf lain dengan cara menyisipkan dan/atau membuang secara berulang-ulang simpul berderajat 2
G G1K5
c b
a
c d
e f g
h
i b a
d
e f g
hi
• Graf G tidak planar karena upagrafnya, G1, homeomorfik dengan K5
a
c
eg
h
Matematika Diskrit 61
Graf Euler
• Lintasan Euler adalah : Lintasan yang melalui masing-masing sisi di dalam
graf tepat satu kali.
• Sirkuit Euler adalah : Sirkuit yang melewati masing-masing sisi tepat satu
kali
• Graf Euler (Eulerian graph) adalah : Graf yang mempunyai sirkuit Euler
• Graf semi-Euler (semi-Eulerian graph) adalah : Graf yang mempunyai lintasan Euler
Matematika Diskrit 62
• Lintasan Euler pada graf : 4,2,1,4,3,2
• Graf yang mempunyai lintasan Euler (graf semi-Euler)
Graf Euler
1
4 3
2 1
4 3
2
1
56
2
34
• Lintasan Euler pada graf : 1,2,4,6,2,3,6,5,1,3• Graf yang mempunyai lintasan Euler (graf
semi-Euler)
• Lintasan Euler pada graf : 7,1,2,4,6,2,3,6,5,3,1,5,7
• Graf yang mempunyai sirkuit Euler (graf Euler)
1
56
2
347
Matematika Diskrit 63
Graf Euler
1
43
2
5
1
43
2
5
6
Graf yang tidak mempunyai lintasan Euler (graf semi-Euler) dan sirkuit Euler (graf Euler)
Matematika Diskrit 64
• Graf terhubung tak-berarah G adalah : graf Euler (memiliki sirkuit Euler) jika dan hanya jika
setiap simpul di dalam graf tersebut berderajat genap graf semi-Euler (memiliki lintasan Euler) jika dan
hanya jika di dalam graf tersebut terdapat tepat 2 simpul berderajat ganjil
• Graf terhubung berarah G memiliki : sirkuit Euler jika dan hanya jika G terhubung dan
setiap simpul memiliki derajat masuk dan derajat keluar sama
Lintasan Euler jika dan hanya jika G terhubung dan setiap simpul memiliki derajat masuk dan derajat keluar sama kecuali 2 simpul :1. Memiliki derajat keluar 1 lebih besar dari derajat masuk2. Memiliki derajat masuk 1 lebih besar dari derajat keluar
Graf Euler
Matematika Diskrit 65
Graf berarah yang memiliki sirkuit Euler (a,g,c,b,g,e,d,f,a)
Graf Euler
a
e d
b
g
cf
d
ab
c
Graf berarah yang memiliki lintasan Euler (d,a,b,d,c,b)
d
ab
c
Graf berarah yang tidak memiliki lintasan Euler dan sirkuit Euler
Matematika Diskrit 66
Graf Hamilton
• Lintasan Hamilton adalah : lintasan yang melalui tiap simpul di dalam
graf tepat satu kali• Sirkuit Hamilton adalah :
Sirkuit yang melalalui tiap simpul di dalam graf tepat satu kali, kecuali simpul asal (sekaligus simpul akhir) yang dilalui 2 kali
• Graf Hamilton adalah : Graf yang memiliki sirkuit Hamilton
• Graf semi-Hamilton adalah : Graf yang hanya memiliki lintasan Hamilton
Matematika Diskrit 67
Graf Hamilton
a) Graf yang memiliki lintasan Hamilton (misal : 3, 2, 1, 4)b) Graf yang memiliki sirkuit Hamilton (1, 2, 3, 4, 1)c) Graf yang tidak memiliki lintasan maupun sirkuit Hamilton
(a)
1
4 3
2
(b)
1
4 3
2
(c)
1
4 3
2
Graf yang mengandung sirkuit Hamilton
Matematika Diskrit 68
• Teorema Dirac : Jika G adalah graf sederhana dengan n buah simpul (n
3) sedemikian hingga derajat tiap simpul paling sedikit n/2 (yaitu d(v) n/2 untuk setiap simpul v di G) maka G adalah graf Hamilton
• Teorema Ore : Jika G adalah graf sederhana dengan n buah simpul (n
3) sedemikian hingga d(v) + d(u) n untuk setiap pasang simpul tidak bertetangga u dan v, maka G adalah graf Hamilton
• Setiap graf lengkap adalah graf Hamilton• Di dalam graf lengkap G dengan n buah simpul (n 3)
terdapat sebanyak (n – 1)! / 2 buah sirkuit Hamilton• Di dalam graf lengkap G dengan n buah simpul :
n 3 dan n ganjil, terdapat (n – 1)/2 buah sirkuit Hamilton yang saling lepas (tidak ada sisi yang beririsan)
n 4 dan n genap, terdapat (n – 2)/2 buah sirkuit Hamilton yang saling lepas
Graf Hamilton
Matematika Diskrit 69
Contoh• Sembilan anggota sebuah klub bertemu tiap hari untuk makan
siang pada sebuah meja bundar. Mereka memutuskan duduk sedemikian hingga setiap anggota mempunyai tetangga duduk berbeda pada setiap makan siang. Berapa hari pengaturan tersebut dilaksanakan ?
• Penyelesaian :Dapat direpresentasikan oleh sebuah graf dengan 9 buah simpul sedemikian hingga setiap simpul menyatakan anggota klub dan sisi yang menghubungkan 2 buah simpul menyatakan kedua simpul tersebut bertetangga tempat duduk
1
2
3
4
56
7
8
9
Pengaturan tempat duduk adalah : 1,2,3,4,5,6,7,8,9,1 (gaaris tebal dan merah) 1,3,5,2,7,4,9,6,8,1 (garis putus-putus dan
hijau)Ada 2 buah sirkuit Hamilton yang saling lepasJumlah pengaturan tempat duduk yang berbeda (n = 9) :
(n -1) / 2 n ganjil(9 – 1) / 2 = 4
Jadi pengaturan tempat duduk yang berbeda diterapkan selama 4 hari, setiap haarinya setiap peserta mempunyai tetangga yangberbeda dengan hari sebelumnya
Matematika Diskrit 70
Aplikasi Graf
• Lintasan terpendek (shortest path)• Persoalan pedagang keliling
(travelling salesman problem)• Persoalan tukang pos Cina• Pewarnaan graf (graph colouring)
Matematika Diskrit 71
Lintasan terpendek (shortest path)
• Graf yang digunakan dalam pencarian lintasan terpendek adalah graf berbobot (weighted graph), yaitu graf setiap sisinya diberikan suatu nilai atau bobot
• Beberapa persoalan : Lintasan terpendek antara 2 buah simpul tertentu Lintasan terpendek antara semua pasangan simpul Lintasan terpendek dari simpul tertentu ke semua simpul
yang lain Lintasan terpendek antara 2 buah simpul yang melalui
beberapa simpul tertentu
• Algoritma untuk lintasan terpendek adalah algoritma Dijkstra
Matematika Diskrit 72
Algoritma Dijkstra
Procedure Dijkstra (input m : matriks, a: simpul awal){ Mencari lintasan terpendek dari simpul awal
a ke semua simpul lainnyamasukan : matriks ketetanggan (m) dari
graf berbobot G dan simpul awal a
keluaran : lintasan terpendek dari a ke semua simpul lainnya
}Deklarasi
s1, s2, …, sn : integer (tabel integer)d1, d2, …, dn : integer (tabel integer)i, j , k : integer
Algoritma { langkah 0 (inisialisasi) }for i 1 to n do
s(i) 0d(i) m(a(i))
endfor
{ langkah 1 }
s(a) 1 (karena simpul a adalah simpul
asal lintasan terpendek, jadi
simpul a sudah pasti terpilih
dalam lintasan terpendek)
d(a) (tidak ada lintasan terpendek
dari simpul a ke a)
{ langkah 2 }
for k 2 to n-1 do
j simpul dengan s(j) = 0 dan d(j)
minimal
s(j) 1 (simpul j sudah terpilih ke dalam
lintasan terpendek)
{perbarui tabel d)
for semua simpul i dengan s(i) = 0 do
if d(j) + m(ji) < d (i) then
d(i) d(j) + m(ji)
endif
endfor
endfor
Matematika Diskrit 73
Contoh (1) Tentukan lintasan terpendek dari graf berikut :
j=a b c d e f
i=a 0 50 10 40 45
b 0 15 10
c 20 0 15
d 20 0 35
e 30 0
f 3 0
Matriks ketetanggan M :
Lintasan terpendek dari :•a ke c adalah : a,c p = 10•a ke d adalah : a,c,d p = 25•a ke b adalah : a,c,d,b p =
45•a ke e adalah : a,e p = 45•a ke f tidak ada lintasan
a
c d
b50 10
3
e
f
30
3520
15
40
1020
15
Matematika Diskrit 74
Contoh (2) Router
asalRouter tujuan
Lintasan terpende
k
1 123456
-1,4,21,4,6,31,41,4,2,51,4,6
2 123456
2,4,1-2,4,6,32,42,52,4,6
3 123456
3,6,4,13,6,4,2-3,6,43,53,6
4 123456
4,14,24,6,3-4,2,54,6
5 123456
5,2,4,15,25,35,2,4-5,3,6
6 123456
6,4,16,4,26,36,46,3,5-
Router 1
1040
km
, 10
kbpsRouter 2 Router 4
Router 3 Router 5
Router 6
560 km, 56 kbps
450 km, 30 kbps
1210
km
, 11
kbps
350 km, 5 kbps
2275 km, 25 kbps
890 km, 10 kbps
1225 km, 35 kbps
340km, 20 kbps
Jaringan komputer
Matematika Diskrit 75
Router 1
Router 5
1040
km
, 10
kbps
Router 2 Router 4
Router 3
Router 6
560 km, 56 kbps
450 km, 30 kbps
1210
km
, 11
kbps
350 km, 5 kbps
2275 km, 25 kbps
890 km, 10 kbps
1225 km, 35 kbps
340km, 20 kbps
Lintasan terpendek yang dilalui oleh pesan dari
router 1 ke router 5
Matematika Diskrit 76
Persoalan Pedagang Keliling (Travelling Salesman Problem)
Graf lengkap dengan n = 4 memiliki :(n – 1)! /2 = (4 – 1)! /2
= 3! / 2 = 3*2*1 / 2
= 3 sirkuit HamiltonYaitu :• S1 = (a,b,c,d,a) atau (a,d,c,b,a) dengan panjang rute = 10 + 15 + 8 + 12 =
45• S2 = (a,c,d,b,a) atau (a,b,d,c,a) dengan panjang rute = 12 + 9 + 15 + 5 =
41• S3 = (a,c,b,d,a) atau (a,d,b,c,a) dengan panjang rute = 10 + 9 + 8 + 5 = 32Sehingga lintasan terpendek dari sirkuit Hamilton adalah :
S3 = (a,c,b,d,a) atau (a,d,b,c,a) Dengan panjang rute 32
a
dc
b12
8
15
105
9
a
dc
b12
8
15
105
9
Matematika Diskrit 77
Latihan Soal1. Sebuah graf akan dibentuk dari 25
buah sisi. Berapa jumlah maksimum simpul di dalam graf sederhana yang dapat dibuat dari 25 buah sisi dengan r 4
2. Berapa jumlah maksimum dan jumlah minimum simpul pada graf sederhana yang mempunyai 12 buah sisi dan tiap simpul berderajat 3?
3. Gambarkan dua buah graf teratur berderajat 3 dengan 6 buah simpul