BAB 2
LANDASAN TEORI
2.1. Konsep Dasar Graph
Sebelum sampai pada pendefinisian masalah network flow, terlebih dahulu pada bagian ini akan diuraikan mengenai konsep-konsep dasar dari model graph dan representasinya dalam memodelkan masalah network flow.
Definisi 2.1. Sebuah graph G adalah pasangan (V,E) di mana V adalah himpunan tak kosong yang anggotanya disebut verteks dan E adalah himpunan yang anggotanya adalah pasangan tak berurut dari verteks V yang disebut edge.
Secara umum graph dapat digambarkan dengan suatu diagram di mana verteks ditunjukkan sebagai titik yang dinotasikan dengan v i , i = 1, 2, …,P dan edge digambarkan dengan sebuah garis lurus atau garis lengkung yang menghubungkan dua verteks (v i , v j ) dan dinotasikan dengan e k . Sebagai ilustrasi dapat dilihat Gambar 2.1. yaitu suatu graph yang mempunyai lima verteks dan enam edge.
V1
e4
e1
e5
V2
e2
V3
e3
V5 e6
V4
Gambar 2.1. Graph dengan lima verteks dan enam edge
Universitas Sumatera Utara
2.2. Graph Berlabel
Hubungan antar verteks-verteks dalam graph perlu diperjelas. Hubungan tidak cukup hanya menunjukkan verteks-verteks mana yang berhubungan langsung, tetapi juga seberapa kuat hubungan itu. Sebagai contoh, andaikata suatu graph menyatakan “peta” suatu daerah. Verteks-verteks graph menyatakan kota-kota yang ada di daerah tersebut. Edge-edge dalam graph menyatakan jalan yang menghubungkan kota-kota tersebut.
Informasi tentang peta daerah perlu diperjelas dengan mencantumkan jarak antara 2 kota yang berhubungan. Informasi tentang jarak dibutuhkan karena dalam graph, letak verteks dan panjang edgenya tidak menyatakan jarak 2 kota yang sebenarnya seperti halnya dengan peta yang sebenarnya. Jadi setiap garis dalam graph berhubungan dengan suatu label yang menyatakan bobot garis tersebut.
Definisi 2.2. Graph Berlabel (weighted graph) adalah suatu graph tanpa edge paralel di mana setiap edgenya berhubungan dengan suatu bilangan riil tak negatif yang menyatakan bobot edge (w(e)) tersebut. Jumlah bobot semua edge disebut Total Bobot.
Matriks yang bersesuaian dengan graph berlabel G adalah matriks hubung A = (a ij ) dengan a ij = bobot edge yang menghubungkan verteks v i dengan verteks v j . Jika verteks v i tidak berhubungan langsung dengan verteks v j, maka a ij = ∞, dan a ij = 0 di mana i = j.
Contoh 2.1. Dalam suatu propinsi, ada 8 kota (v 1 , v 2 , …, v 8 ) yang akan dihubungkan dengan jaringan listrik. Biaya pemasangan jaringan listrik yang mungkin dibuat antar 2 kota adalah sebagai berikut:
Universitas Sumatera Utara
Edge
Kota yang dihubungkan
Biaya per satuan
e4
v2 – v3
3
e7
v4 – v6
4
e2
v1 – v7
5
e8
v3 – v4
5
e9
v3 – v5
5
e1
v1 – v2
15
e3
v1 – v4
15
e 10
v6 – v8
15
e5
v7 – v8
15
e 11
v5 – v6
15
e6
v6 – v7
18
a. Graph berlabel untuk menyatakan jaringan listrik di 8 kota dapat digambarkan pada Gambar 2.2. di bawah ini. Angka dalam kurung menyatakan bobot edge yang bersangkutan. Bobot tersebut menyatakan biaya pengadaan jaringan listrik.
e1 (15)
v1 e2 (5)
e3 (15)
v7 e5 (15) v8
v2
v4 e6 (18)
e10 (15) v6
e4 (3) e8 (5) v3
e7 (4)
e9 (5) v5
e11 (15)
Gambar 2.2.Graph Jaringan listrik di 8 kota
Universitas Sumatera Utara
b. Matriks hubung untuk menyatakan graph berlabel pada Gambar 2.2. adalah matriks A = (a ij ) dengan a ij = Jarak verteks v i dengan v j
di mana ada edge yang menghubungkan
verteks v i dengan v j ∞
di mana tidak ada edge yang menghubungkan verteks v i dengan v j
0
A =
di mana i = j
v1
v2
v3
v4
v5
v6
v7
v8
v1
0
15
∞
15
∞
∞
∞
∞
v2
15
0
3
∞
∞
∞
∞
∞
v3
∞
3
0
5
5
∞
∞
∞
v4
15
∞
5
0
∞
4
∞
∞
v5
∞
∞
5
∞
0
15
∞
∞
v6
∞
∞
∞
4
15
0
18
15
v7
5
∞
∞
∞
∞
18
0
15
v8
∞
∞
∞
∞
∞
15
15
0
Misalkan G adalah sebuah graph berarah. Sebuah edge berarah e = [u,v] dikatakan mulai pada verteks awal u dan berahkhir di verteks akhir v, u dan v dikatakan adjacent.
Definisi 2.3. Derajat luar dari v, (outdeg (v)) adalah jumlah edge yang berawal pada v, dan derajat dalam dari v (indeg (v)) adalah jumlah edge yang berakhir di v. Jika setiap edge mulai dan berakhir pada suatu verteks, maka jumlah derajat-dalam dan jumlah derajat-luar harus sama dengan n, yaitu jumlah edge pada G.
Definisi 2.4. Sebuah verteks v di G disebut sumber (source) bila mempunyai derajatluar positif tetapi derajat-dalam nol. Sedangkan, v disebut tujuan (sink) jika v mempunyai derajat-dalam positif tetapi derajat-luar nol. Perhatikan Gambar 2.3.
Universitas Sumatera Utara
A
C
B
E
D
G
F
Gambar 2.3. Graph G dengan 7 verteks
Gambar 2.3. di atas terdiri dari: Verteks
A
B
C
D
E
F
G
Derajat-dalam (indegree)
0
2
2
4
1
1
2
Derajat-luar (outdegree)
4
1
0
0
3
3
1
Jumlah derajat dalam dan jumlah derajat luar sama dengan 12 yaitu jumlah arc.
Pada Gambar 2.3. Verteks A adalah sumber (source) karena edgenya berawal pada A tetapi tidak berakhir di A. Sedangkan C dan D adalah verteks tujuan (sink) karena edgenya berakhir di C dan di D tetapi tidak berawal di verteks itu.
2.3.
Path Minimum
Salah satu aplikasi graph berarah berlabel yang sering dipakai adalah mencari path terpendek diantara 2 verteks. Jika masalahnya adalah mencari jalur tercepat, maka path terpendek tetap dapat digunakan dengan cara mengganti nilai edge.
Universitas Sumatera Utara
Definisi 2.5. Misalkan G adalah suatu graph. Di mana v dan w adalah 2 verteks dalam G. Suatu Walk dari v ke w adalah barisan verteks-verteks berhubungan dan edge secara berselang-seling, diawali dari verteks v dan diakhiri pada verteks w. Walk dengan panjang n dari v ke w ditulis: v 0 e 1 v 1 e 2 v 2 … v n-1 e n v n dengan v 0 = v; v n = w; v i-1 dan v i adalah verteks-verteks ujung edge e i. Path dengan panjang n dari v ke w adalah walk dari v ke w yang semua edgenya berbeda. Path dari v ke w dituliskan sebagai v = v 0 e 1 v 1 e 2 v 2 … v n-1 e n v n = w dengan e i ≠ e j untuk i ≠ j. Definisi 2.6. Lintasan adalah suatu barisan edge (ei1 , ei2 ,.........., eik ) sedemikian rupa sehingga verteks terminal ei j berimpit dengan verteks awal ei( j +1) untuk 1 ≤ j ≤ k – 1.
Contoh 2.2. e4 e5
v4
v3 e2 v1
e3 e6
v2 e1
e7
e10
e8 e9
v5
v6
Gambar 2.4. Graph dengan 6 verteks dan 10 edge
Pada Gambar 2.4. di atas terdapat: a. Semua edge berbeda (e 1 , e 3 , e 4 , dan e 5 masing-masing muncul sekali). Ada verteks yang berulang (v 3 muncul 2 kali). Verteks awal dan verteks akhir tidak sama (verteks awal = v 1 dan verteks akhir = v 4 ). Barisan ini merupakan path dari v 1 ke v 4 dengan panjang 4. b. Ada edge yang muncul lebih dari sekali, yaitu e 5 (muncul 2 kali) berarti barisan tersebut merupakan walk dari v 1 ke v 5 dengan panjang 5.
Universitas Sumatera Utara
2.4. Representasi Graph dalam Matriks
Matriks dapat digunakan untuk menyatakan suatu graph. Jika graph dinyatakan sebagai suatu matriks, maka perhitungan-perhitungan yang diperlukan dapat dilakukan dengan mudah.
Kesulitan utama merepresentasikan graph dalam suatu matriks adalah keterbatasan matriks untuk mencakup semua informasi yang ada dalam graph. Akibatnya ada bermacam-macam matriks untuk menyatakan suatu graph tertentu. Tiap-tiap matriks tersebut mempunyai keuntungan yang berbeda-beda dalam menyaring informasi yang dibutuhkan pada graph.
Misalkan G adalah sebuah graph dengan verteks-verteks v 1 , v 2, …, v m dan edge-edge e 1, e 2, …, e n . Definisi 2.7. Matriks adjacency Misalkan A = (a ij ) adalah matriks m x m yang didefinisikan oleh aij =
1
jika {u, v} adalah edge, yaitu v i adjacent terhadap v j
0
lainnya
A disebut matriks adjacency dari G. Perhatikan a ij = a ji , sehingga A adalah sebuah matriks simetris. (Didefinisikan sebuah matriks adjacency untuk sebuah multigraph dengan pemisalan a ij menyatakan jumlah edge {v i, v j }.) Definisi 2.8. Matriks Insiden Misalkan M = (m ij ) adalah matriks m x n yang didefinisikan oleh m =
1
verteks v i adalah incident pada edge e j.
0
lainnya
M disebut matriks incidence dari G.
Perhatikan Gambar 2.5 berikut ini.
Universitas Sumatera Utara
e5 e2
v1
v5 e6
e3
e1
e7
v4 e8
v2
e4
v3
Gambar 2.5. Graph dengan 5 verteks dan 8 edge
Pada Gambar 2.5. Matriks adjacency A = (a ij ) dari graph G. Karena G mempunyai 5 verteks maka A akan menjadi matriks 5 x 5. Jika ada sebuah edge antara v i dan v j , maka a ij = 1. Jika sebaliknya, maka a ij = 0. Ini akan menghasilkan matriks berikut:
A =
v1
v2
v3
v4
v5
v1
0
1
1
1
1
v2
1
0
1
0
0
v3
1
1
0
1
1
v4
1
0
1
0
1
v5
1
0
1
1
0
Pada Gambar 2.5. Matriks Incidence M = (m ij ) dari graph G. Jika G mempunyai 5 verteks dan 8 edge, maka M akan menjadi matris 5 x 8. Jika verteks v i anggota dari edge e j, maka m ij =1, jika sebaliknya, maka m ij = 0 untuk lainnya. Ini akan menghasilkan matriks berikut.
Universitas Sumatera Utara
A =
e1
e2
e3
e4
e5
e6
e7
e8
v1
1
1
1
0
1
0
0
0
v2
1
0
0
1
0
0
0
0
v3
0
0
1
1
0
0
1
1
v4
0
0
0
0
1
1
0
1
v5
0
1
0
0
0
1
1
0
2.5. Shortest Path
Setiap path dalam digraph mempunyai nilai yang dihubungkan dengan nilai path tersebut, yang nilainya adalah jumlah dari nilai edge path tersebut. Dari ukuran dasar ini dapat dirumuskan masalah seperti “ mencari lintasan terpendek antara dua verteks dan meminimumkan biaya”.
Banyak bidang penerapan mensyaratkan untuk menentukan lintasan terpendek berarah dari asal ke tujuan di dalam suatu distribusi aliran berarah. Algoritma yang diberikan dapat dimodifikasi dengan mudah untuk menghadapi lintasan berarah pada setiap iterasinya. Suatu versi yang lebih umum dari masalah lintasan terpendek adalah menentukan lintasan terpendek dari sembarang verteks menuju ke setiap verteks lainnya. Pilihan lain adalah membuang kendala tak negatif bagi “jarak”. Suatu kendala lain dapat juga diberlakukan dalam suatu masalah lintasan terpendek.
Definisi 2.10. Lintasan terpendek antara dua verteks dari s ke t dalam network adalah lintasan graph berarah sederhana dari s ke t dengan sifat di mana tidak ada lintasan lain yang memiliki nilai terendah.
Universitas Sumatera Utara
Contoh 2.4. 2 X1 1
2 2
4
X2
3 X3
5 X8
X5 X4
3 X7
1 3 4
5 1 X6
Gambar 2.6. Shortest path (garis tebal)
Pada Gambar 2.6. dapat dilihat bahwa setiap edge terletak pada path-path dari titik 1 ke titik 5. Edge merepresentasikan saluran dengan kapasitas tertentu (contohnya, air) dapat dialirkan melalui saluran. Sedangkan verteks merepresentasikan persimpangan saluran. Air mengalir melalui verteks pada verteks yang dilalui Lintasan terpendek dari verteks pada graph di atas adalah P = {1 – 4, 4 – 5} dengan kapasitas 4.
2.6. Linear Programming
Perumusan linear programming dapat membantu prosedur penyelesaian lebih efisien. Berikut ini adalah bentuk umum linear programming. Minimumkan c1 x1 + c2 x2 + ... + cn xn
(1)
Dengan kendala a11 x1 + a12 x2 + ... + a1n xn = b1
(2)
a21 x1 + a22 x2 + ... + a2 n xn = b2 . . am1 x1 + am 2 x2 + ... + amn xn = bm x1, x2, ..., xn ≥ 0
(3)
Universitas Sumatera Utara
Pada program linear ini, x 1 , x 2 , … , x n mewakili keputusan variabel yang tidak diketahui; c 1, c 2, … , c n adalah biaya koefisien; b 1 , b 2, … , b n adalah nilai di samping kanan; dan a ij , i = 1 sampai m dan j = 1 sampai n, dinamakan koefisien teknologi. Pernyataan (1) dinamakan fungsi objektif; (2) dinamakan kendala; dan (3) adalah kendala tidak negatif. Beberapa penyelesaian memenuhi semua kendala, dinamakan feasible solution.
Pada perumusan ini, kendala ditulis dalam bentuk persamaan. Umumnya, kendala linear programming mempunyai relasi ≥ atau ≤ tetapi selalu dapat diubah dalam persamaan dengan penjumlahan slack variabel. Fungsi objektif (1) juga dapat diekspresikan sebagai maksimum sebagai pengganti minimum. Dapat dirumuskan menjadi: n
∑c x
Minimumkan
j =1
j
j
Dengan kendala n
∑a x j =1
ij
j
x j ≥ 0,
= bi ,
i = 1,2,..., m j = 1,2,..., m
2.7. Flow
Definisi 2.10 Suatu flow pada network G = (N,A) adalah suatu graph berarah dan berkapasitas, di mana setap arc(x,y) Є A memiliki kapasitas nonnegative c(x,y) ≥ 0. Jika (x,y) Є A, maka diasumsikan c(x,y) = 0.
Universitas Sumatera Utara
6
V1
V3
8 a1
a4
6 a8
s
0
5
a5 a3
t
4 a7
a9
a2 6 6
V2
8 V4
a6
Gambar 2.7. Flow dalam network
Gambar 2.7 memperlihatkan bahwa setiap arc terletak pada tiap-tiap node dari sumber s ke tujuan t. Arc menggambarkan saluran dengan kapasitas tertentu. Kapasitas merupakan batas maksimal di mana setiap material (misalnya air, gas, listrik)
dapat
dialirkan
melalui
saluran.
Sedangkan
node
menggambarkan
persimpangan saluran. Material mengalir melalui node tanpa mengumpulkan material tersebut pada node yang dilalui (kecuali pada node sumber dan node tujuan).
2.8. Minimal Cost Flow
Definisi 2.11 Cost flow pada arc dalam network flow dengan arc cost adalah perkalian antara arc-arc flow dan cost. Cost pada flow adalah jumlah dari cost flow pada arc.
Andaikan sebuah directed network (jaringan berarah) G, terdiri atas beberapa node (titik) N = {1,2,…,m) dan beberapa directed arcs (busur berarah) S = {(i,j), (k,l),…,(s,t)} dan saling terhubung pada node N. Arc (i,j) disebut incident (peristiwa) dari node i dan j dan terhubung dari node i ke node j. Dengan demikian diperoleh bahwa network memiliki m node dan n arc.
Untuk setiap node i dalam network G, misalkan jumlah b i adalah ketersediaan barang (b i > 0) atau permintaan barang (b i < 0). Node dengan b i > 0 sering disebut sources (sumber), dan node dengan b i < 0 sering disebut tujuan (sinks). Jika b i = 0,
Universitas Sumatera Utara
maka tidak ada barang yang tersedia pada node i dan tidak diperlukan. Pada permasalahan ini node i sering disebut intermediate (perantara) node. Untuk setiap arc (i,j) pada x ij adalah jumlah aliran pada arc (asumsikan 0 ≤ x ij ) dan c ij adalah biaya pengiriman sepanjang arc.
Asumsikan bahwa total penyediaan barang sama dengan total permintaan di dalam network. Secara matematika dapat dituliskan sebagai berikut.
m
Minimumkan
m
∑∑ c i =1 j =1
Kendala
m
m
j =1
k =1
ij
xij
∑ xij − ∑ xki = b i
i = 1, 2, ...,m x ij ≥ 0
i,j = 1, 2, …,m
(2.1)
Persamaan (2.1) disebut flow conservation atau persamaan Kirchhoff . Di dalam m
xij menunjukkan jumlah aliran yang keluar dari node i persamaan mkekekalan, ∑ j =1
xki sedangkan ∑ menunjukkan jumlah aliran yang masuk ke node i. Persamaan tersebut k =1 m
m
j =1
k =1
mengharuskan aliran yang keluar dari node i, ∑ xij − ∑ x ki , akan sama dengan b i.
Jika b i < 0, maka akan lebih banyak aliran yang masuk pada node i dari pada yang keluar.
Universitas Sumatera Utara
