APLIKASI GRAF

Program Studi Teknik InformatikaFakultas Teknologi IndustriUniversitas Atma Jaya Yogyakarta

MATAKULIAH MATEMATIKA DISKRET

APLIKASI GRAFRepresentasi graf dapat diterapkan untuk mempermudah penyelesaian beberapa masalah dalam riset operasi (operation research). Beberapa contoh masalah riset operasi sebagai berikut :shortest path (shortest route) problemspanning tree problemmaximal flow problem

SHORTEST PATH (SHORTEST ROUTE) PROBLEM Shortest path (shortest route) problem adalah masalah untuk menentukan jalur atau rute terpendek dari suatu simpul asal ke suatu simpul tujuan dalam suatu jaringan (network) Contoh kasus:

SHORTEST PATH (SHORTEST ROUTE) PROBLEM Seorang pengelana bermaksud pindah dari tempatnya semula (simpul 1) ke tempat lain (simpul 6). Untuk sampai ke tempat tujuannya, ia harus melewati beberapa simpul seperti yang ditunjukkan oleh graf berikut ini

SHORTEST PATH (SHORTEST ROUTE) PROBLEM

SHORTEST PATH (SHORTEST ROUTE) PROBLEM Masalahnya adalah berapakah jarak terpendek dan rute mana sebaiknya yang harus ditempuh sang pengelana untuk sampai ke tempat tujuannya?

SHORTEST PATH (SHORTEST ROUTE) PROBLEM Solusi: Menggunakan Algoritma DijkstraAlgoritma Djikstra akan memberi label pada simpul-simpul suatu graf yang akan ditinjau Pada setiap langkah dalam algoritma ini, akan ada simpul yang diberi label permanen, sedangkan yang lainnya diberi label sementara (temporer)

SHORTEST PATH (SHORTEST ROUTE) PROBLEM Algoritma ini dimulai dengan memberi label 0 untuk simpul awal S, dan sebuah label temporer untuk simpul-simpul lainnya Dari sini iterasi dimulai, yang akan memberikan label permanen dengan aturan sebagai berikut:

SHORTEST PATH (SHORTEST ROUTE) PROBLEM 1.Semua simpul j, simpul yang belum memiliki label permanen, akan memperoleh label sementara yang nilainya diberikan oleh:

min [label j yang lama, (label i yang lama + dij)]

SHORTEST PATH (SHORTEST ROUTE) PROBLEM dengan:i : simpul terakhir yang diberi label permanen pada iterasi sebelumnyadij : jarak langsung antara simpul i dan j. Bila simpul i dan j tidak terhubungkan oleh rusuk, maka dij = 2. Temukan nilai terkecil dari label-label temporer tersebut, dan jadikan label permanen

Contoh

Contoh

Contoh

ContohPerhatikan, pada langkah terakhir sebenarnya ada dua nilai yang sama. Pilihan label terkecil dijatuhkan pada label 6 karena dengan demikian iterasi dapat dihentikan

CONTOHSebuah komputer pada simpul B akan mengirimkan paket data ke komputer pada simpul G, pada sebuah jaringan dengan topologi sbb:

BACEDFG713243821210274

TUGASDiketahui graf seperti pada gambar. Tentukan jarak terpendek dari simpul 1 ke simpul 6 menggunakan algoritma Djikstra1234563749633312

MINIMUM SPANNING TREE PROBLEM Minimum Spanning tree problem adalah masalah untuk menentukan pohon perentang minimum dari suatu jaringan (network)Apakah pohon perentang itu?

MINIMUM SPANNING TREE PROBLEMContoh:Sebuah perusahaan swasta bermaksud membangun sebuah jaringan telekomunikasi bawah tanah yang menghubungkan kota-kota besar di pulau Jawa seperti yang direpresentasikan oleh graf berikut:

MINIMUM SPANNING TREE PROBLEM

MINIMUM SPANNING TREE PROBLEMBerapa panjang kabel minimum yang dibutuhkan untuk menghubungkan seluruh kota tersebut di atas? Bagaimana keterhubungan kota-kota tersebut? Solusi: menggunakan Algoritma Minimum Spanning Tree (MST)

MINIMUM SPANNING TREE PROBLEMLangkah-langkah algoritma MST: Dari sembarang simpul i, hubungkan simpul i dengan sebuah simpul j (simpul terdekat) dalam graf G. Sekarang kita memiliki dua anak graf, yaitu C = {i, j} dan C yang beranggotakan simpul-simpul selain i dan j. Rusuk (i, j) di sini menjadi pohon perentang minimum

MINIMUM SPANNING TREE PROBLEMTemukan sebuah simpul n (pada anak graf C) yang paling dekat dengan anak graf C. Hubungkan simpul n tersebut ke simpul i atau j (simpul n mungkin lebih dekat ke i atau ke j). Sekarang kedua anak graf tersebut diperbaharui menjadi C = {i, j, n}, dan C beranggotakan simpul-simpul selain i, j, n. Ulangi langkah 2 sampai anak graf C memiliki simpul yang sama dengan graf G

MINIMUM SPANNING TREE PROBLEMKita dapat melakukan iterasi terhadap langkah-langkah pada algoritma MST sebagai berikut: Iterasi 1 :Kita pilih YK sebagai simpul awal dan SLO adalah simpul terdekat dengan YK. Sekarang C = {YK, SLO}, dan C = {JKT, BDG, CRB, SMG, SBY}

MINIMUM SPANNING TREE PROBLEMYKJKTBDGCRBSMGSLOSBY1801504040012013060180370350400450

MINIMUM SPANNING TREE PROBLEMIterasi 2 :Simpul terdekat dengan anak graf C adalah SMG. Sekarang C = {YK, SLO, SMG}, dan C = {JKT, BDG, CRB, SBY}

MINIMUM SPANNING TREE PROBLEMYKJKTBDGCRBSMGSLOSBY1801504040012013060180370350400450

MINIMUM SPANNING TREE PROBLEMIterasi 3 :Simpul terdekat dengan anak graf C adalah SBY. Sekarang C = {YK, SLO, SMG, SBY}, dan C = {JKT, BDG, CRB}

MINIMUM SPANNING TREE PROBLEMYKJKTBDGCRBSMGSLOSBY1801504040012013060180370350400450

MINIMUM SPANNING TREE PROBLEMIterasi 4 :Simpul terdekat dengan anak graf C adalah CRB. Sekarang C = {YK, SLO, SMG, SBY, CRB}, dan C = {JKT, BDG}

MINIMUM SPANNING TREE PROBLEMYKJKTBDGCRBSMGSLOSBY1801504040012013060180370350400450

MINIMUM SPANNING TREE PROBLEMIterasi 5 :Simpul terdekat dengan anak graf C adalah CRB. Sekarang C = {YK, SLO, SMG, SBY, CRB, BDG}, dan C = {JKT}

MINIMUM SPANNING TREE PROBLEMYKJKTBDGCRBSMGSLOSBY1801504040012013060180370350400450

MINIMUM SPANNING TREE PROBLEMIterasi 6 :Simpul terdekat dengan anak graf C adalah JKT. Sekarang C = {YK, SLO, SMG, SBY, CRB, BDG, JKT}, dan C = {}

MINIMUM SPANNING TREE PROBLEMYKJKTBDGCRBSMGSLOSBY1801504040012013060180370350400450

MINIMUM SPANNING TREE PROBLEMSetelah melakukan 6 iterasi, kita menemukan panjang pohon perentang minimumnya : 60 + 120 + 180 + 350 + 40 + 150 = 900. Jadi, perusahaan tersebut membutuhkan kabel sepanjang 900 km untuk menghubungkan kota-kota tersebut. Keterhubungan kota-kota di atas adalah sebagai berikut :

MINIMUM SPANNING TREE PROBLEM YKJKTBDGCRBSMGSLOSBY1504012060180350

SOALTentukan minimum spanning tree dari graf berikut :abcdegfh151413464112279511

TUGASTentukan minimum spanning tree dari graf berikut :

ABCDEF111961045783

TUGASCari rute terpendek dari a ke h :abcdefgh432536157245

MAXIMAL FLOW PROBLEM Maximal Flow Problem (masalah aliran maksimum) dapat dimodelkan sebagai suatu jaringan (network) yang rusuk-rusuknya merepresentasikan saluran untuk melewatkan suatu komoditas tunggal Setiap rusuk pada jaringan tersebut memiliki kapasitas maksimal untuk melewatkan suatu komoditas, dan oleh karenanya dapat ditentukan aliran maksimal dari suatu simpul awal (source) ke suatu simpul tujuan (destination) pada jaringan tersebut

MAXIMAL FLOW PROBLEMContoh:Sebuah perusahaan minyak akan menyalurkan minyak bumi yang baru saja dieksploitasi dari sumur minyak (simpul so) ke pelabuhan (simpul si). Dalam perjalanannya dari simpul so, minyak harus melewati stasiun-stasiun tertentu, seperti pada gambar.

MAXIMAL FLOW PROBLEMKarena diameter pipa yang menghubungkan stasiun-stasiun berbeda-beda, maka kapasitas alir saluran antar simpulnya yang ditunjukkan oleh label pada rusuk (dalam 1000 barel per detik) juga bervariasi. Permasalahannya: Berapa kapasitas aliran maksimum dari sumur minyak sampai ke pelabuhan? Lewat jalur yang mana saja?

MAXIMAL FLOW PROBLEM

MAXIMAL FLOW PROBLEMSolusi: menggunakan algoritma maximal-flow minimal-cut dan algoritma pelabelan termodifikasi

MAXIMAL-FLOW MINIMAL-CUT1. Algoritma Maximal-Flow Minimal-CutDalam suatu jaringan G, bila sebuah komoditas tunggal dialirkan dari simpul asal ke simpul tujuan, nilai aliran-maksimumnya sama dengan nilai kapasitas-minimum dari cut-set jaringan itu, atau dalam bentuk matematis dapat direpresentasikan sebagai: fmaks = min {u(X, Y)}

MAXIMAL-FLOW MINIMAL-CUTBila dimisalkan X adalah himpunan dari simpul-simpul yang terdapat pada sebuah jaringan G yang selalu beranggotakan simpul asal, tetapi tidak termasuk simpul tujuan, dan Y = N - X, maka :(X, Y) {(i, j) ; i X, j Y }(X, Y) disebut sebagai cut-set, yaitu himpunan potongan (rusuk) yang memisahkan simpul asal dengan simpul tujuan

MAXIMAL-FLOW MINIMAL-CUTSimpul lainnya (selain simpul asal dan tujuan) dapat dianggap sebagai simpul tengah (intermediate node)

Dari definisi cut-set di atas, dapat kita susun tabel cut-set sebagai berikut:

MAXIMAL-FLOW MINIMAL-CUT

MAXIMAL-FLOW MINIMAL-CUTBila dimisalkan (X, Y) adalah sembarang cut-set yang memisahkan simpul asal dengan simpul tujuan pada jaringan G, maka kapasitas cut-set tersebut dapat dinyatakan sebagai berikut:

MAXIMAL-FLOW MINIMAL-CUTDengan memperhatikan rumus ini, tabel cut-set di atas dapat kita modifikasi menjadi tabel cut-set dan kapasitas maksimum cut-set sebagai berikut:

MAXIMAL-FLOW MINIMAL-CUT

MAXIMAL-FLOW MINIMAL-CUTBila teorema maximal-flow minimal-cut kita gunakan untuk menentukan nilai aliran maksimum untuk graf pada gambar diatas, maka kita peroleh :

MAXIMAL-FLOW MINIMAL-CUTfmaks = min {u(X, Y)} = 3Agar aliran maksimum, komoditas harus dilewatkan melalui :Rusuk (1, 2) sebanyak 1 satuanRusuk (3, 4) sebanyak 2 satuanIni dapat dilakukan dengan melewatkan komoditas tersebut melalui jalur 1-2-4 sebanyak 1 satuan dan jalur 1-3-4 sebanyak 2 satuan

MAXIMAL-FLOW MINIMAL-CUT

MAXIMAL-FLOW MINIMAL-CUT

MAXIMAL-FLOW MINIMAL-CUTDari tabel tersebut diperoleh:fmaks = min {u(X, Y)} = 45.000 barel/detikAgar aliran maksimum, komoditas harus dilewatkan melalui :Rusuk (1, 2) sebanyak 20 barel/detikRusuk (1, 3) sebanyak 10 barel/detikRusuk (4, 5) sebanyak 15 barel/detik

MAXIMAL-FLOW MINIMAL-CUTIni dapat dilakukan dengan melewatkan komoditas tersebut melalui jalur 1-2-5 sebanyak 20 barel/detik, dan jalur 1-3-5 sebanyak 10 barel/detik, dan jalur 1-4-5 sebanyak 20 barel/detik.

SOALSebuah ruas jalan yang sangat padat, mengalami perbaikan total selama 2 minggu, sehingga 6000 mobil/jam harus dialihkan ke ruas jalan lain. Ruas jalan alternatif tersebut dapat digambarkan seperti gambar 8-17. Gambar tersebut dapat diartikan sebagai berikut : Pada ruas jalan 1-2, 6000 mobil dapat lewat dari arah 1 menuju 2. Pada ruas jalan 1-3, 5000 mobil dapat lewat dari arah 1 menuju 3, dan 9000 mobil dari arah 3 menuju 1. Demikian seterusnya. Permasalahannya : Apakah 6000 mobil per jam yang biasanya melalui ruas jalan yang sedang diperbaiki itu dapat dialihkan ke jalan alternatif ? Seandainya tidak dapat seluruhnya, berapa mobil per jam yang dapat dialihkan ? Ruas jalan mana saja yang dapat digunakan ?

125346647336255

ALGORITMA PELABELAN TERMODIFIKASI Pada algoritma maximal-flow minimal-cut, tidak ada prioritas pengecekan jalur, sehingga seluruh cut-set harus dievaluasi kapasitas aliran maksimalnyaAlgoritma Pelabelan Termodifikasi mencoba mengidentifikasi jalur-jalur yang mungkin dilalui, baru kemudian mengevaluasi kapasitas aliran jalur tersebut

ALGORITMA PELABELAN TERMODIFIKASILangkah-langkahnya adalah sebagai berikut: Temukan jalur-jalur yang mungkinTemukan jalur terpendek. Tentukan kapasitas aliran maksimal jalur tersebut (kapasitas aliran maksimum jalur = kapasitas minimal rusuk pada jalur tersebut)

ALGORITMA PELABELAN TERMODIFIKASIKurangkan nilai kapasitas maksimal setiap rusuk dengan nilai kapasitas maksimum jalur tersebutUlangi langkah 2 sampai seluruh jalur terevaluasiJumlahkan seluruh kapasitas aliran maksimum jalur

ALGORITMA PELABELAN TERMODIFIKASI

Dari graf ini, dapat kita temukan jalur-jalur yang mungkin adalah : jalur 1-2-5, 1-2-4-5, 1-4-5, 1-3-4-5, dan 1-3-5

ALGORITMA PELABELAN TERMODIFIKASIIterasi 1 :Jalur terpendek : 1-2-5Kapasitas maksimum: 20Kapasitas rusuk: {[(1, 2), 0], [(2, 5), 8]} Iterasi 2 :Jalur terpendek : 1-4-5Kapasitas maksimum: 15Kapasitas rusuk : {[(1, 4), 15], [(4, 5), 0]}

ALGORITMA PELABELAN TERMODIFIKASIIterasi 3 :Jalur terpendek : 1-3-5Kapasitas maksimum: 10Kapasitas rusuk : {[(1, 3), 0], [(3, 5), 10]}Iterasi 4 :Jalur terpendek : 1-2-4-5Kapasitas maksimum: 0Kapasitas rusuk : {[(1, 2), 0], [(2, 4), 5], [(4, 5), 0]}

ALGORITMA PELABELAN TERMODIFIKASIIterasi 5 :Jalur terpendek : 1-3-4-5Kapasitas maksimum: 0Kapasitas rusuk : {[(1, 3), 0], [(3, 4), 15], [(4, 5), 0]}

Kapasitas aliran maksimum seluruh jalur = 20 + 15 + 10 + 0 + 0 = 45