BAB 2 LANDASAN TEORI

BAB 2 LANDASAN TEORI

2.1 Definisi Graf

Sebuah graf G adalah pasangan sebuah himpunan hingga tidak kosong dari simpul (bentuk tunggal adalah titik) bersama dengan sebuah himpunan berurut dari simpul yang berbeda dari G yang disebut busur.

2.2 Graf Berarah (Directed Graph atau Digraph)

Graf berarah merupakan graf yang setiap busurnya diberikan orientasi arah. Sisi pada graf berarah biasanya disebut busur (arc). Graf berarah dapat dilihat pada Gambar 2.1.

Gambar 2.1 Graf Berarah

Di dalam situasi yang dinamis, seperti pada komputer digital ataupun pada sistem aliran, konsep graf berarah lebih sering digunakan dibandingkan dengan konsep graf tak berarah. Apabila ruas suatu graf berarah mempunyai suatu bobot, graf berarah tersebut dinamakan suatu jaringan atau network. Beberapa Pengertian dalam jaringan:

a. Derajat ke luar (out degree) suatu simpul adalah banyaknya ruas yang berawal/ keluar dari simpul tersebut.

Universitas Sumatera Utara

6

b. Derajat ke dalam (in degree) suatu simpul adalah banyaknya ruas yang berakhir / masuk ke simpul tersebut. c. Simpul berderajat ke dalam = 0 disebut source, sedangkan simpul berderajat ke luar = 0 disebut sink. Pada graf berarah terdapat 3 pengertian keterhubungan, yakni :

a. Terhubung lemah, jika terdapat suatu semi path antara setiap 2 simpul dari graf. b. Terhubung unilateral, jika antara setiap 2 simpul u dan v dari graf, terdapat jalur dari u ke v atau dari v ke u. c. Terhubung kuat, jika antara setiap 2 simpul u dan v dari graf, terdapat jalur dari u ke v dan dari v ke u. Contoh :

Gambar 2.2 Connected Graf

2.3 Lintasan (Path)

Jika u dan v adalah dua simpul dalam graf G maka sebuah lintasan (path) u-v adalah urutan bolak simpul dan busur dimulai dari u dan berakhir di v tanpa ada simpul yang diulang. Gambar 2.3 adalah contoh sebuah lintasan a-e: a,b,c,d,f,e. Dengan kata lain, dapat dimulai dari simpul a menuju ke simpul b, dari b menuju ke c , kemudian ke d, dari d menuju ke f dan berakhir di e. Perhatikan bahwa simpul berturut-turut di lintasan-lintasan yang berdekatan satu sama lain. Dalam lintasan tidak diperbolehkan mengulang simpul dan busur. (Slamin, 2006).


7

b

a

c g

d f

e

Gambar 2.3 Lintasan (Path) pada Graf

2.4 Pohon (Tree) Tree adalah suatu diagram yang digambar dengan menggunakan titik dan garis di mana setiap garis berfungsi untuk menghubungkan dua buah titik. Tree mempunyai kekhususan, yaitu dari simpul yang satu ke simpul yang lain hanya terhubung oleh serangkaian busur dengan jalur tunggal yang berarti tidak ada dua jalur antara dua simpul. (Zakaria T.M, 2005).

Jika T = (V,E) adalah sebuah graf dengan n simpul, maka pernyataan berikut adalah ekuivalen: 1.

T adalah sebuah pohon (tree).

2.

T tidak sirkuit dan mempunyai n-1 busur .

3.

T terhubung dan mempunyai n-1 busur.

4.

Setiap busur dari T adalah titik potong (cut set).

5.

Untuk setiap u,v Є V hanya satu lintasan (path) u-v.

6.

Untuk setiap busur e yang baru, yang bergabung T + e mempunyai satu sirkuit.


8

Gambar 2.4 Contoh-contoh Tree

2.5 Arus Optimal Pada Jaringan Multiple Source dan Sinks Sebuah graf berbobot adalah kembar tiga (triplet) η = (V, Ą, c), dimana V adalah sebuah himpunan hingga tak kosong (nonempty finite set) dimana elemennya adalah sebuah simpul, Ą adalah sebuah himpunan dari pasangan berurut yang mengapit dua simpul dan c adalah sebuah fungsi dari Ą ke non negatif yang real yang disebut fungsi kapasitas. Jaringan adalah diasumsikan sebagai simpul-simpul yang terkoneksi untuk menghubungkan simpul (x, y) yang memenuhi persamaan x = x0, x1, …, xm = y, dimana untuk setiap i, 1 ≤ i ≤ m, dengan (xi-1, x) atau (x1, xi-1) adalah sebuah busur. Untuk setiap pasangan dari himpunan bagian X, Y ⊂ V, (X, Y) = {(x,y): x  X, y  Y, (x,y)  Ą} ……………………….……… (1)

Sebuah pasangan dari bentuk (X,VX) adalah disebut sebuah cut, jika g adalah sebuah fungsi dari Ą untuk bilangan real yang didefinisikan sebagai berikut:

g(X,Y) =

𝑥,𝑦 ∈(𝑥,𝑦) 𝑔(𝑥, 𝑦)

…………………………………………………….… (2)

dan untuk setiap simpul x didefinisikan sebagai: net (g,x) =g(V,{x}) – g ({x}),V) ………………………………………….………. (3)


9

Diberikan S ⊂ V untuk diletakkan di source dan T ⊂ V \ S yang di letakkan di sinks pada jaringan. Sebuah aliran adalah sebuah fungsi f dari Ą ke nonegative real (bilangan real bukan negatif) sebagai: f(x,y) ≤ c(x,y) …………………………………………………………..….. (4) Untuk semua busur (x,y) dan untuk setiap simpul x, maka: ≤ 0 𝑗𝑖𝑘𝑎 𝑥 ∈ 𝑆, G (f,x) ≥ 0 𝑗𝑖𝑘𝑎 𝑥 ∈ 𝑇, …………………………………………….……. (5) = 0 𝑠𝑒𝑙𝑎𝑖𝑛 𝑖𝑡𝑢 Definisi dari klas dari semua aliran adalah τ. Diberikan sebuah aliran f, T(f) didefinisikan sebagai |T|-tuple dari nomor graf (f,t), t  T, sesuai dari penambahan magnitudo. Analogi beri S(f) sebagai |S|-tuple dari nomor graf (f,s), s  S, sesuai dengan pengurangan magnitudo. Sebuah aliran f* adalah disebut sink yang optimal atau source yang optimal jika untuk setiap f Є τ, T(f*) (S(f*)) adalah lexicographically greater (less) maka atau sama dengan ke T(f) (S(f)) (Megiddo, 1974).

2.6 Primal Simplex Variant untuk Max Flow Problem

Pada sebuah graf G (V,A) adalah graf langsung dari simpul yang ditetapkan sebagai V, dan sebuah busur yang ditetapkan sebagai A. Setiap busur k Є A mungkin sebagai sebuah pasangan berurut dari simpul (u,v). Sebagai gambaran untuk setiap busur k = (u,v) adalah sebuah variabel aliran xk dan sebuah batas atas atau koefisien kapasitas uk. Penambahan dua simpul yang spesifik s Є V dan t Є V disebut source dan sink. Sebuah rumusan dari permasalahan aliran maksimum dari sebuah source (s) ke sebuah sink (t) adalah disajikan sebagai: Maximize y1, Subject to

-

𝑥𝑘 +𝑦1 =0, 𝑘∈𝐹𝑆(𝑠) 𝑥𝑘 −𝑦2=0, 𝑘∈𝑅𝑆(𝑖)

−

𝑥𝑘 + 𝑘∈𝐹𝑆(𝑖)

𝑘∈𝐹𝑆(𝑖)

=0,

i Є N – {s,t},

y1 + y2 =0,


10

0 ≤ xk ≤ uk, untuk semua k  A, y1, y2 ≥ 0, dimana FS(i) = {k:k = (i,j)  A} dan RS(i) = {k:k = (j,i)  A}. FS (i) adalah disebut sebagai permulaan dari simpul i dan suatu himpunan bagian dari busur pada simpul i. RS(i) adalah disebut kebalikan dari simpul i dan himpunan bagian dari busur pada akhir simpul i (Glover, 1984).

Secara sederhana, permasalahan aliran maksimum dapat dideskripsikan sebagai masalah pencarian untuk mencari aliran maksimum yang dapat mengalir pada sebuah graf yang hanya memiliki sebuah source dan sebuah sink. Aplikasi dari permasalahan aliran maksimum ini adalah sebagai berikut: “Terdapat pipa-pipa yang berhubungan, dengan kapasitas / daya tampung yang berbeda – beda. Pipa – pipa ini terhubung dengan sebuah keran, berapa volume maksimum air yang dapat dialirkan dari penampungan air sampai dengan keran di rumah” atau “Sebuah perusahaan memiliki sebuah pabrik di kota x dimana barang yang selesai di produksi harus di kirim ke kota y. Kasus di atas memiliki data jalan satu arah yang menghubungkan setiap kota dan jumlah maksimum truk yang dapat melewati jalan tersebut” Tentukan jumlah maksimum truk yang dapat dikirimkan sekali kirim. Dengan pengamatan pertama, dapat menyimpulkan bahwa truk yang masuk ke kota y pasti sama dengan jumlah truk yang keluar dari x (Schrijver, 2002).

Gambar dibawah ini menunjukkan solusi optimal untuk salah satu permasalahan di atas, setiap busur diberi tanda dengan sebuah nilai f/c yang diasosiasikan dengannya, dimana f/c adalah aliran yang dialirkan pada suatu graf terhadap kapasitas dari tiap busurnya.

Gambar 2.5 Optimum Solution in Network


11

Jika aliran dari x-y lebih kecil dari pada kapasitas maka busur x-y memiliki kapasitas yang sama dengan perbedaan antara kapasitas dan alirannya dan jika alirannya bernilai positif, maka terdapat busur balik y-x dengan kapasitas setara dengan aliran di x-y yang disebut residual capacity. Sebuah augmenting path adalah sebuah jalan dari source ke sink dalam sebuah residual network (jaringan yang masih memiliki kapasitas sisa ), yang bertujuan untuk meningkatkan aliran suatu graf. Sangatlah penting untuk mengerti bahwa busur yang menghasilkan jalur ini dapat menunjuk arah yang salah tergantung dari graf asal. Kapasitas dari lintasan ini adalah kapasitas minimum dari seluruh kapasitas busur-busur yang dilalui oleh lintasan tersebut. Sebagai contoh diberikan sebuah graf berbobot aliran maksimum yang selanjutnya kita sebut sebagai jaringan ( network ) seperti pada Gambar 2.6.

Gambar 2.6 Network Flow

Gambar 2.7 Residual network


12

Dengan memperhatikan jalan X-A-C-Y, maka dapat meningkatkan aliran sebesar 1 busur X-A dan A-C memiliki kapasitas 3, tetapi busur C-Y memiliki kapasitas 1, dan dapat diambil nilai minimum untuk nilai-nilai dari setiap busur tersebut. Dari contoh diatas menghasilkan aliran seperti pada Gambar 2.8.

Gambar 2.8 Network Flow Nilai dari aliran sekarang adalah 2, seperti yang terlihat dalam Gambar 2.8. Kemudian alirannya ditingkatkan lagi, dan akan terlihat sudah tidak terdapat lagi lintasan yang memenuhi jaringan di atas, karena semua busur sudah diisi. Dalam kasus ini, dimungkinkan untuk meningkatkan aliran.

Gambar 2.9 Residual Network


13

Kemudian perhatikan bahwa jalan dari X ke Y adalah : X-A-C-B-D-E-Y, ini bukan jalan dalam sebuah jaringan, karena C-B adalah jalan dengan arah yang berlawanan. Jalan ini digunakan untuk meningkatkan aliran total dari jaringan asal. Proses akan memaksa masuk aliran dalam setiap busur, kecuali untuk C-B yang digunakan untuk menbatalkan aliran B-C. Jumlah operasi yang dipergunakan dibatasi oleh kapasitas setiap busur sepanjang lintasan. Kemudian sekali lagi ambil nilai minimum, ini untuk menyimpulkan bahwa lintasan tersebut juga berkapasitas 1. Dengan memperbaharui lintasasan ini seperti cara di atas akan menghasilkan aliran seperti pada Gambar 2.10. Proses dilakukan sampai tidak terdapat lagi sisa lintasan dimana jalan dari source ke sink tidak lagi tersedia.

Gambar 2.10 Aliran Maksimum pada Residual network

2.7 Algoritma Dekomposisi Untuk Min Cut Problem Dengan setiap busur (i,j)  A dari G digabung dengan sebuah bilangan positif uij, disebut kapasitas dari busur. Sebuah himpunan dan nonnegative integers fij adalah disebut sebuah aliran yang mungkin pada jaringan jika memenuhi persamaan di bawah ini:

∑i 𝑓𝑖𝑗 −

−𝑓 𝑗𝑖𝑘𝑎 𝑗 = 1 𝑘 𝑓𝑗𝑘 = 0 𝑗𝑖𝑘𝑎 𝑗 ≠ 1, 𝑛 𝑓 𝑗𝑖𝑘𝑎 𝑗 = 𝑛

Dan


14

0 ≤ fij ≤ uij untuk semua (i,j)  A, Dimana f adalah sebuah nonnegatif integer disebut bobot dari aliran. Sebuah himpunan dari aliran yang mungkin, dimana maksimal f adalah disebut aliran maksimum. Definisinya adalah sebuah X di subset pada sebuah simpul pada jaringan yang mana 1  X, v  X. Juga diberikan X = V– X. Pada (X, X ) diletakkan seperti pada sebuah busur (i,j)  (X, X ) jika i  X, j  X dan (i,j)  A atau j  X, i  X dan (i,j)  A Sehingga himpunan tersebut disebut dengan sebuah pemotongan (cut). Kapasitas dari sebuah pemotongan (X, X ) ditulis sebagai c (X, X ) disajikan seperti: c(X, X ) =

𝑖,𝑗 ∈(𝑋, x )

𝑢𝑖𝑗

𝑖∈𝑋,𝑗 ∈ x

Sehingga dapat didefinisikan sebuah pemotongan kapasitas minimum pada sebuah jaringan disebut sebagai minimum cut.

2.8 Max-Flow Min-Cut

Max-flow min-cut adalah metode untuk mencari maximum flow dan minimum cut pada sebuah network. Metode ini digunakan untuk menentukan besarnya kapasitas kanal untuk jalur transmisi data. Selain itu metode ini juga akan menghilangkan beberapa simpul yang nilai kapasitas kanalnya bernilai kecil dan tidak dipakai untuk melewatkan data.

Cut adalah membagi sebuah graf menjadi dua himpunan yang berbeda, misalkan disebut A dan B, dimana A adalah source dan B adalah sink. Nilai pemotongan adalah nilai yang diperlukan untuk membagi graf tersebut menjadi dua seperti pada Gambar 2.11.


15

Gambar 2.11 Cut in Network

Perhatikan bahwa total nilai untuk membagi jaringan tersebut adalah sama atau lebih kecil dari kapasitas setiap busur. Hal ini menunjukkan bahwa aliran maksimum adalah sama atau lebih kecil dari setiap cut dari setiap network. Dari sinilah asal mulai teorema max-flow min cut yang menyatakan bahwa nilai yang dibutuhkan untuk membagi suatu jaringan menjadi dua adalah sama dengan maximum flow-nya. Cara penyelesaiannya juga sama dengan cara mencari maksimum flow dari suatu graf. Diberikan sebuah jaringant, buang himpunan busur dengan nilai minimum untuk membuat sebuah simpul tidak terakses dari simpul yang lain. Hasilnya adalah sesuai dengan teorema max-flow min-cut yang merupakan maximum flow dari suatu graf. Untuk menentukan busur yang ingin dihilangkan, ambil setiap busur dari awal sampai akhir yang terakses dari simpul awal sampai simpul akhir, kemudian hilangkan simpul yang memiliki nilai minimum seperti pada Gambar 2.12.

Gambar 2.12 Minimum Cut in Network


16

2.9 Max-Flow Min-Cut Theorem

Diberikan graf G(V,A) adalah sebuah graf berarah dan berbobot dengan source (S) dan sink (T). Diberikan f sebagai sebuah aliran. Maka pernyataan berikut ini adalah ekivalen : 1. f adalah sebuah maximum flow pada G. 2. Gf tidak mengandung augmenting paths 3. |f| = C(S, T) untuk beberapa pemotongan pada (S, T). Pembuktian: a. (1)  (2): Jika Gf mengandung sebuah augmenting path maka |f +fp| > |f| jadi f bukan aliran maksimum. b. (2)  (3): Diberikan S = {u ∈ V : ∃ lintasan dari s ke v pada graf Gf}. T = V − S. maka f(S, T) = f(S, V )−f(S, S) = f(S, V ) = f(s, V )+f(S−s, V ) = |f|. Terlihat bahwa untuk setiap u ∈ S, v ∈ T, f(u, v) = c(u, v) Dalam hal lainnya cf(u, v) > 0 and v ∈ S. Dengan demikian C(S, T) = f(S, T) = |f| c. (3)  (1): Dilihat dulu untuk setiap aliran f′ harus memenuhi |f′| ≤ C(S, T) jika dan hanya jika |f| = C(S, T), f haruslah aliran maksimum. Algoritma Max-Flow-Min-Cut pada sebuah graf G = (V, A), dengan source S, terminal T serta kapasitas C adalah:

1. f := 0 (alirkan 0 ke semua sisi graf) 2. opt := false 3. WHILE not opt DO 3a.

Konstruksikan sebuah residual graph Gf

3b.

Cari sebuah jalur langsung P dari S ke T pada Gf (sebuah augmenting path)

3c.

IF augmenting path P ada THEN

3d. 3e.

update aliran f sepanjang P ELSE


17

4. 5 6

set opt := true; and X := set simpul-simpul pada Gf cabang dari S END IF LOOP

7. Masukkan f sebagai max flow dan ( X , V-X ) sebagai min-cut 8. END WHILE Sumber: Vatter, 2004

2.10 Penentuan Fungsi Find_Path

2.10.1 Depth First Search

Dalam menentukan implementasi dari fungsi find_path, langkah awal yang terpikirkan adalah dengan mengunakan algoritma depth-first search (DFS), karena mungkin merupakan metode termudah untuk di implementasikan. Tetapi sayangnya, memberikan hasil yang sangat jelek untuk beberapa network, dan normalnya lebih jarang dipakai dibanding dengan algortima yang akan kita pakai (Tanadi, 2001).

2.10.2 Breath First Search

Hal termudah lainnya yang sering dipakai adalah algoritma breadth-first search (BFS). Algoritma ini memberikan jalur terpendek dalam sebuah graf tak berbobot, dan dalam hal ini, kita dapat mengaplikasikannya untuk mendapatkan augmenting graf terkecil dari source ke sink. Pseudocode berikut secara sederhana menentukan jarur terpendek dari source ke sink, dan menghitung kapasitas minimum dari setiap busur sepanjang jalannya. Kemudian, dari setiap busur mengurangi kapasitasnya dan meningkatkan kapasitas setiap busur yang berkebalikan dengan kapastias jalannya. Pseudo code algoritma BFS adalah: function bfs:integer; //queue Q //push source ke Q //tandai source sebagai pernah dikunjungi //inisialisasi array from[x] //dengan simpul yang dikunjungi sebelumnya //dalam shortest_path dari source //ke x dengan nilai -1 (atau nilai sentinel lainnya); while Q not(empty)


18

where = pop dari Q for setiap simpul yang bertetanga dengan where if next not(visited) and (capacity[where][next] > 0) push next ke Q tandai next dengan visited from[next] = where if next = sink exit while loop end for end while // Menghitung kapasitas setiap jalan where = sink path_cap = infinity while from[where] > -1 prev = from[where] // node sebelumnnya path_cap = min(path_cap, capacity[prev][where]) where = prev end while // memperbaharui residual network, jika tidak terdapat jalan akhiri while loop will not be entered where = sink while from[where] > -1 prev = from[where] capacity[prev][where] -= path_capacity capacity[where][prev] += path_capacity where = prev end while // jika tidak terdapat jalan kapastias adalah tidak terhingga if path_cap = infinity return 0 else return path_cap

Metode diatas cukup mudah diimplementasikan, jumlah operasi terburuk yang akan dilakukan paling banyak N * M/2, dimana N adalah jumlah simpul dan M adalah jumlah busur dari sebuah network. Nilai ini terlihat cukup besar, namun, hal ini merupakan perkiraan kasar untuk setiap network, sebagai contoh, dalam network


19

diatas kita melihat ada 3 augmenting path yang diperlukan dibanding dengan batas atas yang memerlukan 28 buah. Karena kompleksitas dari algoritma BFS adalah O(M), maka diimplementasikan dengan adjacency lists, kompleksitas maksimum adalah O(N * M²), meskipun biasanya algoritma ini lebih baik dari hal ini.

2.10.3 Priority-First Search

Kemudian kita akan mempertimbangkan cara lain yaitu dengan mengunakan priorityfirst search (PFS). Yang sangat mirip dengan algoritma Dijkstra dengan implemntasi heap . Dalam kasus ini augmenting-path dengan kapasitas maksimum akan dipilih terlebih dahulu. Yang secara intuitif akan menghasilkan algoritma yang lebih cepat, karena dalam setiap langkahnya meningkatkan aliran dengan kemungkinan terbesar. Tetapi, tidak selalu begitu, dan impelemtasi BFS memberikan running time yang lebih cepat untuk beberapa network. Kita menentukan nilai setiap simpul dengan kapasitas minimum dari simpul ke busur. Kemudian kita mengambil setiap simpul yang memberikan nilai maksimum, seperti yang dilakukan algoritma Dijkstra, ketika kita mendapatkan sink, berarti kapasitas maksimum telah ditemukan, kemudian kita mengunakan struktur data yang menyebabkan kita dapat mengimplementasikan priority queue dengan tepat, meskipun mungkin membutuhkan space lebih. Ini adalah implementasi dalam pseudocode. function pfs:integer priority queue PQ //push simpul(source, infinity,1) ke PQ //keep the array from as in bfs() // jika tidak terdapat augmenting path, path_cap akan bernilai 0 path_cap = 0 while PQ not(empty) simpul aux = pop dari PQ where = aux.node cost = aux.priority if visited(where) continue from[where] = aux.from if where = sink path_cap = cost exit while loop //tandai where dengan visited //for setiap busur yang //bertetangga dengan where if capacity[where][next] > 0


20

new_cost = min(cost, capacity[where][next]) push node(next, new_cost, where) to PQ end for end while // update residual network where = sink while from[where] > -1 prev = from[where] capacity[prev][where] -= path_cap capacity[where][prev] += path_cap where = prev end while return path_cap Analisis diatas cukup rumit, tapi karena PFS paling banyak melakukan 2M1gU operasi (seperti dalam algoritma dijkstra), dimana U adalah kapasitas maksimum dari sebuah

isi dalam network. Seperti dalam BFS, jumlah ini sangat besar jika

dibandingkan dengan jumlah operasi dalam kebanyakan network. Dikombinasikan dengan kompleksitas O(M 1g M) dari fungsi search untuk menghasilkan worst-case dari algortima tersebut (Tanadi, Kevin, 2001).

2.11 Algoritma Augmenting Path

Sebuah augmenting path adalah sebuah jalur dari source ke sink dalam sebuah residual network yang berfungsi untuk meningkatkan flow suatu network. Algoritma augmenting path sebagai berikut:

1. Initialisasi total flow to 0 2. Residual graph G’= G 3. While augmenting path exist pada G’ 3a. Ambil sebuah augmenting path P pada G’ 3b. m = kapasitas bottleneck dari P 3c. Tambahkan m ke total flow 4. Push flow dari m sepanjang P 5. update G’


21

Untuk mengambil jalur Augmenting dengan cara: a. Cari jalur dengan kapasitas bottleneck yang maksimum. b. Cari sebuah jalur dengan panjang minimum

2.12 Aplikasi MATLAB

MATLAB merupakan salah satu paket aplikasi matematika yang sangat cepat dan menyenangkan untuk digunakan sebagai alat pemecahan masalah matematika secara numerik. Masalah komputasi yang ditemui di dalam matematika dapat diselesaikan secara lebih cepat dengan MATLAB daripada dengan menggunakan bahasa pemrograman baku seperti BASIC, Fortran, C/C++, Pascal, Java dan sebagainya. Khususnya, MATLAB sangat cocok dan cepat untuk melakukan perhitungan yang melibatkan matriks maupun graf. Hal ini sesuai dengan nama MATLAB yang merupakan singkatan dari Matrix Labolatory. MATLAB dapat digunakan untuk melakukan komputasi numerik, simbolik dan visualisasi serta pemrograman (Sahid, 2006).

MATLAB pada hakekatnya hanya bekerja dengan satu jenis objek, yakni matriks numerik dengan elemen-elemen riil maupun kompleks. Semua variabel di dalam MATLAB menyajikan matriks. Sebuah matriks adalah suatu array (jajaran) dua dimensi yang terdiri dari bilangan-bilangan riil dan kompleks dan disusun dalam baris dan kolom. Dalam beberapa situasi, matriks 1 x 1 dianggap sebagai skalar dan matriks yang hanya terdiri dari satu baris atau kolom, dianggap sebagai vektor. Matriks dapat didefinisikan oleh MATLAB dengan beberapa cara, diantaranya: a. Menuliskan daftar elemen-elemen matriks. b. Menggunakan perintah-perintah dan fungsi-fungsi yang tersedia. c. Menggunakan M-file yang merupakan skrip MATLAB atau memanggil file data eksternal. Sebagai contoh untuk membentuk matriks ordo tiga dengan cara: A = [1 2 3; 4 5 6; 7 8 9]


22

Hasilnya: 1 4 7

2 5 8

3 6 9

Perintah di atas berarti MATLAB mendefinisikan matriks 3 x 3 dan disimpan di dalam variabel A. Dengan kata lain, A adalah matriks 3 x 3 yang elemenelemennya seperti tertulis di atas. Elemen-elemen di dalam suatu baris sebuah matriks dapat dipisahkan dengan koma atau spasi. Tanda titik koma (;) atau perpindahan baris (ENTER) digunakan untuk menandai pergantian baris suatu matriks. Untuk membentuk graf seperti Gambar 2.13 di bawah ini:

Gambar 2.13 Graf Berbobot dan Berarah

Dapat dilakukan inisialisasi graf dengan perintah: cm = sparse([1 1 1 2 2 2 3 3 4 5 5 6 6 7],[2 3 4 3 6 5 4 6 7 6 8 7 8 8],[10 5 15 4 15 9 4 8 30 15 10 15 10 10],8,8), dimana [1 1 1 2 2 2 3 3 4 5 5 6 6 7] merupakan node sumber (sourse) pada graf, [2 3 4 3 6 5 4 6 7 6 8 7 8 8] merupakan node tujuan


23

(destination), [10 5 15 4 15 9 4 8 30 15 10 15 10 10] merupakan kapasitas path dan 8,8 adalah jumlah node pada graf. Selanjutnya pseudocode berikut adalah untuk menampilkan graf pada layar. view(biograph(F,[],'ShowWeights','on'))


BAB 2 LANDASAN TEORI

Recommend Documents