2
Contoh 2 Dari graf G pada Gambar 1 didapat e1 incident dengan simpul v1 dan v2, e2 incident dengan simpul v1 dan v3, e3 tidak incident dengan simpul v1, v5, dan v3. Definisi 3 (Adjacent) Jika e={p,q} E, maka simpul p dikatakan adjacent (berelasi) dengan simpul q. (Foulds 1992) Contoh 3 Dari graf G pada Gambar 1 didapat v1 adjacent dengan v2, v3, dan v4, v2 adjacent dengan v1 dan v4, v3 tidak adjacent dengan v2 dan v4. Definisi 4 (Neighbourhood dari simpul) Misalkan diberikan graf G=(V,E). Neighbourhood dari v ∈ V, ditulis dengan NG(v) atau N(v), adalah himpunan simpul yang adjacent dengan v, yaitu NG(v)={u V(G) | vu E(G)}. (Foulds 1992) Contoh 4 Dari graf G pada Gambar 1 diperoleh N(v2)={v1,v4}, N(v1)={v3,v2,v4}, dan lainnya. Definisi 5 (Graf Berbobot) Suatu graf G=(V,E) dikatakan berbobot jika terdapat sebuah fungsi w: E→R (dengan R adalah himpunan bilangan real) yang memadankan setiap sisi di E dengan sebuah bilangan real yang disebut bobot. Setiap bobot w(uv) dengan uv∈E dinotasikan dengan wuv. (Foulds 1992) Contoh 5 G:
v1 v2
4 2
v3
1
v4
2
v5
Gambar 2 Contoh graf berbobot. Pada Gambar 2 terdapat graf berbobot dengan bobot w(uv) sebagai berikut: sisi {v2v3} memiliki bobot w(v2v3)=2, sisi {v3v4} memiliki bobot w(v3v4)=1. Definisi 6 (Walk) Suatu walk dalam suatu graf G adalah sebuah barisan berayun dari simpul dan sisiyang berbentuk W : v0, e1, v1, e2, v2,...,en–1, vn–1, en, vn yang dimulai dari simpul v0 dan diakhiri di simpul vn dengan e = vi–1vi untuk i=1,2,..,n.
Karena sisi ei sudah dicerminkan dari simpul yang mengapitnya, maka untuk selanjutnya walk dapat dituliskan dengan barisan simpul W : v0, v1, v2,...,vn–1, vn. Walk yang dimulai dari v0 dan berakhir di vn disebut walk v0–vn dan walk W mempunyai panjang n karena melalui n sisi (tidak harus berbeda). (Chartrand & Oellermann 1993) Contoh 6 G1: 1
v1
2
v3
3
4
5
2
1
v4
v2
1
v6
1
v7
2
v5
Gambar 3 Graf G1 dengan 7 simpul dan 10 sisi. Pada Gambar 3 didapatkan walk v1– v7 antara lain walk v1– v7: v1, v2, v5, v1, v3, v4, v6, v7. Definisi 7 (Path) Suatu path dalam graf G adalah suatu walk dengan semua simpulnya berbeda. (Ahuja et al. 1993) Contoh 7 Pada Gambar 3 terdapat contoh path, yaitu sebagai berikut: Path v1– v7: v1, v3, v4, v6, v2, v5, v7, Path v1– v7: v1, v5, v7, Path v1– v7: v1, v3, v4, v6, v7, dan seterusnya. Definisi 8 (Panjang Path) Misalkan diberikan path p, yaitu barisan simpul v0–v1–v2–...–vk. Panjang path p adalah jumlah semua panjang sisi yang terdapat pada path tersebut atau dapat dituliskan sebagai: k
d ( p) = d (v0 , vk ) = ∑ d ( vi −1 , vi ). i =1
(Cormen et al. 1990) Contoh 8 Pada Gambar 3 didapatkan beberapa path yang menghubungkan simpul v1 dan simpul v7 dengan panjang path yang berbeda, yaitu: path v1– v7: v1– v3– v4– v6– v2– v5– v7 dengan panjang d(v1, v7)=13, path v1– v7: v1– v5– v7 dengan panjang d(v1, v7)=7, path v1 – v7: v1– v3– v4– v6– v7 dengan panjang d(v1, v7) =5.
3
Definisi 9 (Path Terpendek) Path u–v dikatakan path terpendek jika path yang menghubungkan simpul u dan simpul v tersebut memiliki panjang yang minimum di antara path u–v yang lainnya. (Hu 1981)
H1 :
Definisi 10 (Subgraf ) Suatu graf G’=(V’,E’) adalah subgraf dari graf G=(V,E) jika V’⊆V dan E’⊆E.
Gambar 6 Subgraf H 1 yang diinduksi oleh himpunan simpul S.
(Ahuja et al. 1993) Contoh 9 Pada Gambar 4 didapat salah satu subgraf dari graf G1=(V1,E1), G1’:
v1
v3
v4
v2
v6
Subgraf H 1 diinduksi oleh himpunan simpul S, karena H 1 =〈S〉 yaitu subgraf yang menghubungkan simpul-simpul di S secara maksimal. H2 :
v2
v4
v3 v2
v3
v6
v4
v7 '
'
'
Gambar 4 Subgraf G1 = ( V1 , E1 ) dari graf G1 pada Gambar 3. Definisi 11 (Subgraf yang diinduksi oleh simpul) Misalkan S⊆V(G) dan S≠∅. Subgraf yang diinduksi oleh S dapat dituliskan 〈S〉, H=〈S〉 disebut subgraf maksimal dari G dengan himpunan simpul S. H=〈S〉 ialah subgraf yang menghubungkan simpul-simpul di S secara maksimal. Ini berarti 〈S〉 memuat semua sisi dari G yang menghubungkan simpul-simpul di S. (Chartrand & Oellermann 1993) Contoh 10 H: v3
v4
v2
Gambar 7 Subgraf H 2 tidak diinduksi oleh himpunan simpul S. Subgraf H2 tidak diinduksi oleh himpunan S, karena ada sisi yang menghubungkan simpul v3 dan simpul v4 di G tetapi tidak menghubungkan simpul v3 dan simpul v4 di H2. Definisi 12 (Graf terhubungkan) Graf G=(V,E) dikatakan terhubungkan (connected) jika setidaknya ada satu path yang menghubungkan setiap pasang simpul pada graf tersebut. Jika tidak ada, maka graf tersebut dikatakan tidak terhubungkan (disconnected). (Ahuja et al. 1993) Contoh 11 G:
v1
v5 v6
e1,2
v7
v2 e v3 e v6 3,6 2,3
e2,4 v8
Gambar 5 Graf H=(V, E).
v4 e4,5
Diketahui himpunan S={v2, v3, v4, v6}
e1,3
v5
e6,9
e5,7
v7
e7,11
v11
e7,8 e11,12
v8
e8,9
v9
e9,10
v10
e8,12
v12
Gambar 8 Graf G=(V,E) terhubungkan.
4
G 1:
K4:
v1 e1,3
e1,2
v6
v2 e v3 2,3
v6 Gambar 13 Komponen ke-4 dari graf G1.
v4 e4,5
v5
e5,7
v7
e8,9
v8
e7,11
v9
e9,10
v10
e8,12
v11
v12
Gambar 9 Graf G1=(V1,E1) tidak terhubung. Definisi 13 (Komponen dari Graf) Suatu subgraf terhubung yang tidak termuat pada subgraf lainnya yang juga terhubung disebut komponen graf. (Balakrishnan 1997) Contoh 12 Graf G1 pada Gambar 9 terdiri atas 4 buah komponen, yaitu K1, K2, K3, dan K4, yaitu sebagai berikut: K1:
v1 e1,3
e1,2
v2 e v3 2,3 Gambar 10 Komponen ke-1 dari graf G1. K2:
v4
2.3 Masalah Set covering Misalkan diberikan suatu himpunan S={1, 2, ..., n}. Misalkan juga elemen dari himpunan I merupakan himpunan bagian dari S. Misalkan elemen dari himpunan I terdapat sebanyak K yang dinyatakan dengan Ij, j∈{1, 2, …, K} dan masing-masing memiliki bobot. Definisi 14 (Kover) Misalkan himpunan S={1, 2, …, n} dan himpunan I={I1, I2, …, IK} dengan Ij ⊆ S, j∈ J={1, 2, …, K}. Himpunan Ij dengan j∈ J* ⊆ J merupakan kover dari S jika U I j = S. * j∈ J
e5,7
v5
(Garfinkel & Nemhauser 1972)
v7
e7,11
v11 Gambar 11 Komponen ke-2 dari graf G1. K3:
v8
2.2 Integer Programming Integer programming (IP) atau pemrograman integer adalah suatu pemrograman linear dengan variabel yang digunakan berupa bilangan bulat (integer). Jika semua variabel harus berupa integer, maka masalah tersebut dinamakan pure integer programming, dan jika hanya sebagian yang harus berupa integer dinamakan mixed integer programming. Jika IP dengan semua variabel harus bernilai 0 atau 1, maka disebut 0–1 IP. (Garfinkel & Nemhauser 1972)
e8,9
v9
e9,10
v10
e8,12
v12 Gambar 12 Komponen ke-3 dari graf G1.
Contoh 13 Misalkan himpunan S={a,b,c,d,e,f} dan dengan j J={1,2,3,4,5}. I={I1,I2,I3,I4,I5} Misalkan I1={a,b}, I2={a,c}, I3={b,e}, I4={d,e,f}, I5={a,c,f}. Kover dari S di antaranya adalah {I1,I2,I4}, karena untuk J* ={1,2,4} berlaku U I j = I 1 U I 2 U I 4 = {a , b , c , d , e , f } = S .
j∈ J *
Definisi 15 (Masalah Set Covering/SC) Misalkan diberikan c j > 0 adalah bobot yang berpadanan dengan setiap Ij, dengan j J. Bobot total dari suatu kover {Ij} dengan j∈J* adalah ∑ j∈J * c j , dengan J* adalah himpunan bagian dari J. Masalah set covering merupakan suatu masalah yang menemukan kover dengan bobot minimum yang dapat ditulis sebagai berikut:
5
Minimumkan ⎫ z = ∑ cjxj ⎪ j =1 ⎪ terhadap ⎪ ⎬ ( P1 ) K ∑ a ij x j ≥ 1, i = 1,..., m ⎪ j =1 ⎪ x j = 0 atau 1, j = 1,..., K ⎪⎭ dengan ⎧1, jika I j anggota dari kover xj = ⎨ ⎩ 0, jika selainnya. K
⎧1, jika i elemen dari I j ai, j = ⎨ ⎩0, jika selainnya. (Garfinkel & Nemhauser 1972) Contoh 14 Misalkan diberikan himpunan-himpunan S={a,b,c,d,e,f,g} dan I={I1,I2,I3,I4,I5} dengan j J={1,2,3,4,5}. Misalkan I1={a,b,g}, I2={a,c,g}, I3={b,e,g}, I4={d,e,f}, I5={a,c,f}. Misalkan setiap elemen dari I dipadankan dengan suatu bobot untuk mengkover setiap elemen dari S. Akan ditentukan formulasi untuk mengkover semua elemen dari S oleh elemen-elemen dari I, dengan bobot minimum. Untuk itu, diperlakukan model pemrograman integer murni 0-1. Misalkan: ⎧1, jika i ∈ I j ai, j = ⎨ ⎩0, selainnya ⎧1, jika I j anggota dari kover xj = ⎨ ⎩ 0, selainnya. Jika diasumsikan setiap elemen dari I mempunyai bobot=1, dan fungsi objektifnya adalah meminimumkan banyaknya elemen I yang digunakan untuk mengkover elemen dari S. Maka formulasi IP yang sesuai dengan Definisi 15 adalah Minimumkan z = x1 + x 2 + x 3 + x 4 + x 5
⎫ ⎪ ⎪ ⎪ ⎪ x1 + x 3 ≥ 1 ⎪ ⎪⎪ x2 + x5 ≥ 1 ⎬ ( P2 ) x4 ≥ 1 ⎪ ⎪ x3 + x 4 ≥ 1 ⎪ x4 + x5 ≥ 1 ⎪ ⎪ x1 + x 2 + x 3 ≥ 1 ⎪ x j ∈ {0,1}, un tuk j = 1, ..., 5 ⎪⎭
terhad ap x1 + x 2 + x 5 ≥ 1
Banyaknya kendala pada formulasi di atas merepresentasikan banyaknya elemen dari S. Misalkan kendala ke-1 menyatakan bahwa elemen pertama dari S, yaitu a, dapat dikover
oleh I1={a,b,g}, I2={a,c,g}, atau I5={a,c,f} yang berturut-turut merupakan elemen ke-1, elemen ke-2 dan elemen ke-5 dari himpunan I. Dengan menggunakan LINGO 11.0, solusi ILP (P2) dapat diperoleh yaitu x3=1, x4=1, x5=1, dan z=3. Dari solusi ILP, himpunan dari {I3,I4,I5} merupakan kover dari S (lihat Lampiran 1). Hal ini dikarenakan I3∩I4∩I5= {b,e,g}∩{d,e,f}∩{a,c,f}={a,b,c,d,e,f,g}=S. Definisi 16 (Kover terhubungkan) Kover terhubungkan merupakan suatu kover dan juga merupakan graf terhubungkan, sedangkan kover tidak terhubungkan adalah suatu kover dan juga merupakan graf tidak terhubungkan. (Cerdeira et al. 2005) 2.4 Penentuan Path Terpendek dengan Algoritme Dijkstra Algoritme Dijkstra akan digunakan untuk menentukan path terpendek dari u0 ke setiap simpul di suatu graf atau digraf berbobot. Bobot tersebut adalah bilangan taknegatif. Misalkan diberikan G=(V,E) dengan himpunan simpul V(G) adalah graf berbobot dan tak berarah yang setiap sisi u0v∈E(G) memiliki bobot taknegatif w(u0v). Jika path u0–v ada, maka jarak d(u0,v) dimisalkan jarak di antara pasangan simpul u0,v di G yang memiliki bobot minimum dari setiap path u0– v. Jika path u0–v tidak ada, maka jarak d(u0,v)=+∞. Setiap simpul v (≠u0) akan dilabeli l(v) sehingga l(v)=d(u0,v). Pada proses awalnya, label dari simpul u0 adalah l(u0)=0, sedangkan label dari simpul v (≠u0) adalah l(v)=+∞. Label dari simpul v (≠u0) mungkin turun dari ∞ ke jarak d(u0,v) yang ditentukan. Untuk simpul v (≠u0), PARENT(v) adalah simpul sebelum v di path terpendek u0–v. Ketika l(v) diperbaharui, path terpendek u0–v akan ditemukan dan PARENT(v) diperbaharui untuk mengindikasi simpul yang lebih dulu di path terpendek u0–v. Misalkan S adalah himpunan bagian dari himpunan simpul V(G) yang berisi simpul-simpul di G yang sudah ditentukan jaraknya dari u0. Langkah-langkah pada algoritme Dijkstra untuk menentukan jarak dari u0 ke setiap simpul di graf G dengan banyaknya simpul p adalah sebagai berikut: LANGKAH 1 [Misalkan semua simpul v (≠u0) di G dilabeli dengan l(v)=+∞ dan l(u0)=0. Indeks variabel i
6
dimulai dari i=0. Pada saat ini S={u0}, dan S’=V(G)–{u0}] i←0, S←{u0}, S’←V(G)–{u0}, l(u0) ←0, dan l(v) ←+∞. Jika p=1, maka proses dihentikan. Jika tidak, lanjutkan ke LANGKAH 2.
i ← i+1. Jika i=p–1, maka proses berhenti. Jika tidak, Kembali ke Langkah 2. (Chartrand & Oellermann 1993) Contoh 15 Misalkan diberikan graf tak berarah dan berbobot seperti pada Gambar 14. G:
LANGKAH 2 [Jika label v di S’ yang adjacent dengan ui berubah, maka PARENT(v) diubah menjadi ui] Untuk setiap v∈S’ sehingga ui,v∈E(G), jika l(v) ≤ l(ui) + w(uiv), proses dilanjutkan, jika tidak, maka l(v) ← l(ui) + w(uiv), dan PARENT(v)←ui.
u0
8
16
v1 v6 v2
LANGKAH 3 [Langkah ini menentukan simpul ui+1∈S’ dengan jarak d(ui,ui+1) yang sudah ditemukan] Tentukan m=min{l(v)|v∈S’}. Jika vj∈S’ dipilih sebagai simpul dengan l(vj)=m, maka m adalah jarak antara u0 dan vj, dan ui+1 = vj.
v5
10
13
6 14
11
9
7
17
v7
v4
5
v3
Gambar 14 Graf G tak berarah dan berbobot. Pada Gambar 14 terdapat 8 simpul dan 11 sisi beserta jarak antarsimpulnya. Misalkan akan ditentukan path terpendek dari u0 ke setiap simpul di G beserta jarak yang minimum. Dengan menggunakan algoritme Dijkstra (lihat Lampiran 2) akan diperoleh path terpendek dari u0 ke semua simpul di G beserta jaraknya.
LANGKAH 4 [Pembaharuan S dan S’] S=S ∪ { ui+1 }, S’ =S’ – { ui+1 }. LANGKAH 5 [Pembaharuan indeks variabel i]
Tabel 1 Jarak terpendek dari simpul u0 ke semua simpul di G dari algoritme Dijkstra Iterasi
u0
v1
v2
v3
v4
v5
v6
0 1 2 3 4 5
0
(∞, – ) (∞, – ) (18, v5) (18, v5) (18, v5) –
(∞, – ) (13, u0) (13, u0) – – –
(∞, – ) (∞, – ) (25,v5) (25,v5) (20, v4) (20, v4)
(∞, – ) (16,u0) (15, v5) (15,v5) – –
(∞, – ) (8,u0) – – – –
(∞, – ) (∞, – ) (∞, – ) (∞, – ) (∞, – ) (∞, – )
Dari Tabel 1, dapat diketahui beberapa path terpendek dari simpul u0 ke semua simpul v (path terpendek Q). Contoh path terpendek dari simpul u0 ke simpul v1 ialah path terpendek Q1= u0 – v5 – v1 dengan jarak 18, untuk path terpendek dari simpul u0 ke simpul v2, yaitu path terpendek Q2= u0 – v2 dengan jarak 13.
Penambahan S
v7 (∞, – ) (∞, – ) (∞, – ) (∞, – ) (∞, – ) (∞, – )
u0 v5 v2 v4 v1 v3
G: u0
8
16
v1
13
v5
10
v6
v7 v2
v4 v3
5
Gambar 15 Path terpendek Qi.
