matematika diskrit

Posted January 12th, 2010 by MUHAMMADTAQWA

o Matematika Diskrit

A. Latar Belakang

Matematika merupakan salah satu alat yang dapat membantu mempermudah pemecahan permasalahan

kehidupan sehari-hari. Salah satu cabang Matematika yang bermanfaat membantu memecahkan

permasalahan adalah Teori Graf. Teori graf merupakan salah satu bidang Matematika, yang diperkenalkan

pertama kali oleh ahli Matematika asal Swiss, Leonardo Euler pada tahun 1736. Ide besarnya muncul

sebagai upaya menyelesaikan masalah jembatan Königsberg. Dari permasalahan itu, akhirnya Euler

mengembangkan beberapa konsep mengenai teori graf.

Kemudian seiring dengan perkembangan bidang komputasi serta dalam hal ini berkembangnya perangkat

lunak maupun perangkat keras komputer, teori graf banyak dijadikan model dalam memecahkan masalah

yang ada dalam kehidupan kita sehari-hari. Salah satu topik menarik dalam teori graf adalah lintasan dan

sirkuit Hamilton. Dalam makalah ini akan dibahas bagaimana graf dapat membantu mengatasi

permasalahan transportasi dengan menggunakan aplikasi lintasan Hamilton.

Penyedia jasa pengantar dapat menggunakan metode lintasan terpendek dan persoalan pedagang keliling

dalam penghematan bahan bakar dan waktu dalam pengantaran. Kedua metode akan sangat membantu

dalam merencanakan lintasan yang akan diambil oleh pengantar .

Pertama kita akan mengambil metode persoalan pedagang keliling untuk mengambil beberapa macam

lintasan yang dilewati untuk menyederhanakan persoalan. Hal ini agar kemungkinan lintasan yang akan

didapat berkurang, sehingga memudahkan mengambil keputusan dalam pemilihan lintasan. Kedua

dengan mengambil metode lintasan terpendek, kita mencoba mengurangi waktu tempuh dan bahan bakar

yang digunakan. Hal ini mempertimbangkan aspek banyaknya simpul dan jumlah lintasan yang diambil.

Dengan demikian kita bisa menentukan lintasan mana yang akan menghasilkan jarak tempuh terpendek.

Dalam hal ini kita akan banyak menggunakan lintasan Hamilton dalam pembahasan kedua metode yang

digunakan. Hal ini karena lintasan Hamilton dianggap lebih cocok untuk mengatasi permasalahan ini.

Sebab pada sirkuit Hamilton simpul harus dilalui tepat satu kali. Sesuai dengan apa yang diinginkan oleh

layanan jasa pengantar. Dengan menggunakan kedua metode tersebut, kita mendapatkan lintasan yang

hanya dilewati sekali dan jarak yang terpendek. Sedangkan daerah lintasan penelitian berada dalam batas

jalan lingkar, dan pencarian rute perjalanan tidak memperhitungkan, lebar jalan, rambu-rambu dan lampu-

lampu lalu lintas, serta kondisi jalan, dan tidak memungkinkan adanya penentuan satu arah atau dua arah,

http://one.indoskripsi.com/category/mata-kuliah/matematika-diskrit

serta penutupan jalan. Jadi, metode di atas sangat berguna untuk mengurangi pengeluaran bahan bakar,

jarak dan waktu tempuh di bidang transportasi khususnya untuk para jasa pengantar.

B. TEORI GRAF

Teori Graf merupakan pokok bahasan yang sudah tua usianya namun memiliki banyak terapan dalam

kehidupan sehari-hari sampai saat ini. Graf digunakan untuk merepresentasikan objek-objek diskrit dan

hubungan antara objek-objek tersebut. Banyak persoalan pada dunia nyata yang sebenarnya merupakan

representasi visual dari graf. Contoh salah satu representasi visual dari graf adalah peta. Banyak hal yang

dapat digali dari representasi tersebut, diantaranya adalah menentukan jalur terpendek dari satu tempat

ke tempat lain, menggambarkan 2 kota yang bertetangga dengan warna yang berbeda pada peta,

menentukan tata letak jalur transportasi, pengaturan jaringan komunikasi atau jaringan internet dan

masih banyak lagi. Selain peta, masih banyak hal lain dalam dunia nyata yang merupakan representasi

visual dari graf.

Gambar 1 Graf yang menggambarkan peta beberapa negara bagian di Amerika Serikat

A. Definisi Graf

Secara matematis, graf didefinisikan sebagai berikut:

Graf G didefinisikan sebagai pasangan himpunan (V,E) yang dalam hal ini :

V = himpunan tidak kosong dari simpul - simpul (vertices atau node): {v1,v2,…,vn}

E = himpunan sisi (edges atau arcs) yang menghubungkan sepasang simpul: {e1,e2,…,en}

atau dapat ditulis singkat notasi G = (V, E)

B. Jenis-Jenis Graf

Berdasarkan ada tidaknya gelang atau sisi ganda pada suatu graf, maka secara umum graf digolongkan

menjadi dua jenis:

1. Graf sederhana (simple graph) adalah graf yang tidak mengandung gelang maupun sisi-ganda

dinamakan graf sederhana.

2. Graf tak-sederhana (unsimple-graph) adalah graf yang mengandung sisi ganda atau gelang dinamakan

graf tak-sederhana (unsimple graph).

Berdasarkan jumlah simpul pada suatu graf, maka secara umum graf dapat digolongkan menjadi dua

jenis:

1. Graf berhingga (limited graph) adalah graf berhingga adalah graf yang jumlah simpulnya, n, berhingga.

2. Graf tak-berhingga (unlimited graph) adalah graf yang jumlah simpulnya, n, tidak berhingga banyaknya

disebut graf tak-berhingga.

Berdasarkan orientasi arah pada sisi, maka secara umum graf dibedakan atas 2 jenis:

1. Graf tak-berarah (undirected graph) adalah graf yang sisinya tidak mempunyai orientasi arah disebut

graf tak-berarah.

2. Graf berarah (directed graph atau digraph) adalah graf yang setiap sisinya diberikan orientasi arah

disebut sebagai graf berarah.

C. Terminologi Dasar

Terdapat beberapa istilah penting yang berkaitan dengan graf. Berikut ini didefinisikan beberapa

terminologi yang sering digunakan:

G1 G2 G3

Gambar 2 Graf yang digunakan untuk menjelaskan terminologi pada graf

1. Ketetanggaan (Adjacent)

Dua buah simpul dikatakan bertetangga bila keduanya terhubung langsung.

Tinjau graf G1 : simpul 1 bertetangga dengan simpul 2 dan 3,

simpul 1 tidak bertetangga dengan simpul 4.

2. Bersisian (Incidency)

Untuk sembarang sisi e = (vj, vk) dikatakan e bersisian dengan simpul vj , atau e bersisian dengan simpul

vk

Tinjau graf G1: 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.

3. Simpul Terpencil (Isolated Vertex)

Simpul terpencil ialah simpul yang tidak mempunyai sisi yang bersisian dengannya.

Tinjau graf G1: simpul 5 adalah simpul terpencil.

4. Graf Kosong (null graph atau empty graph)

Graf yang himpunan sisinya merupakan himpunan kosong (Nn).

Graf N5 :

5. Derajat (Degree)

Derajat suatu simpul adalah jumlah sisi yang bersisian dengan simpul tersebut.

Notasi: d(v)

Tinjau graf G1:

d(1) = d(4) = 2

d(2) = d(3) = 3

Tinjau graf G3: d(5) = 0 ? simpul terpencil

d(4) = 1 ? simpul anting-anting (pendant vertex)

Tinjau graf G2: d(1) = 3 ? bersisian dengan sisi ganda

d(2) = 4 ? bersisian dengan sisi gelang (loop)

Pada graf berarah,

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

d(v) = din(v) + dout(v)

G4 G5

Tinjau graf G4:

din(1) = 1; dout(1) = 1

din(2) = 1; dout(2) = 3

din(3) = 1; dout(3) = 1

din(4) = 2; dout(3) = 0

6. Lintasan (Path)

Lintasan yang panjangnya n dari simpul awal v0 ke simpul tujuan vn di dalam graf G ialah barisan

berselang-seling simpul-simpul dan sisi-sisi yang berbentuk v0, e1, v1, e2, v2,... , vn –1, en, vn sedemikian

sehingga e1 = (v0, v1), e2 = (v1, v2), ... , en = (vn-1, vn) adalah sisi-sisi dari graf G.

Tinjau graf G1: lintasan 1, 2, 4, 3 adalah lintasan dengan barisan sisi (1,2), (2,4), (4,3).

Panjang lintasan adalah jumlah sisi dalam lintasan tersebut. Lintasan 1, 2, 4, 3 pada G1 memiliki panjang

3.

7. Siklus (Cycle) atau Sirkuit (Circuit)

Lintasan yang berawal dan berakhir pada simpul yang sama disebut sirkuit atau siklus.

Tinjau graf G1: 1, 2, 3, 1 adalah sebuah sirkuit.

Panjang sirkuit adalah jumlah sisi dalam sirkuit tersebut. Sirkuit 1, 2, 3, 1 pada G1 memiliki panjang 3.

8. Terhubung (Connected)

Dua buah simpul v1 dan simpul v2 disebut terhubung jika terdapat lintasan dari v1 ke v2. G disebut graf

terhubung (connected graph) jika untuk setiap pasang simpul vi dan vj dalam himpunan V terdapat

lintasan dari vi ke vj. Jika tidak, maka G disebut graf tak-terhubung (disconnected graph).

Contoh graf tak-terhubung:

Graf berarah G dikatakan terhubung jika graf tidak berarahnya terhubung (graf tidak berarah dari G

diperoleh dengan menghilangkan arahnya). Dua simpul, u dan v, pada graf berarah G disebut terhubung

kuat (strongly connected) jika terdapat lintasan berarah dari u ke v dan juga lintasan berarah dari v ke u.

Jika u dan v tidak terhubung kuat tetapi terhubung pada graf tidak berarahnya, maka u dan v dikatakan

terhubung lemah (weakly coonected). Graf berarah G disebut graf terhubung kuat (strongly connected

graph) apabila untuk setiap pasang simpul sembarang u dan v di G, terhubung kuat. Kalau tidak, G disebut

graf terhubung lemah.

graf berarah terhubung lemah graf berarah terhubung kuat

9. Upagraf (Subgraph) 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 graf G adalah graf G2 = (V2, E2) sedemikian sehingga E2 = E - E1

dan V2 adalah himpunan simpul yang anggota-anggota E2 bersisian dengannya.

(a) Graf G1 (b) Sebuah upagraf (c) komplemen dari upagraf (b)

Komponen graf (connected component) adalah jumlah maksimum upagraf terhubung dalam graf G.

Graf G di bawah ini mempunyai 4 buah komponen.

Pada graf berarah, komponen terhubung kuat (strongly connected component) adalah jumlah maksimum

upagraf yang terhubung kuat.

Graf di bawah ini mempunyai 2 buah komponen terhubung kuat:

10. Upagraf Rentang (Spanning Subgraph)

Upagraf G1 = (V1, E1) dari G = (V, E) dikatakan upagraf rentang jika V1 =V (yaitu G1 mengandung semua

simpul dari G).

(a) graf G, (b) upagraf rentang dari G, (c) bukan upagraf rentang dari G

?

11. Cut-Set

Cut-set dari graf terhubung G adalah himpunan sisi yang bila dibuang dari G menyebabkan G tidak

terhubung. Jadi, cut-set selalu menghasilkan dua buah komponen.

12. Graf Berbobot (Weighted Graph)

Graf berbobot adalah graf yang setiap sisinya diberi sebuah harga (bobot).

D. Beberapa Graf Khusus

1. Graf Lengkap (Complete Graph)

Graf lengkap ialah graf sederhana yang setiap simpulnya mempunyai sisi ke semua simpul lainnya. Graf

lengkap dengan n buah simpul dilambangkan dengan Kn. Jumlah sisi pada graf lengkap yang terdiri dari n

buah simpul adalah n(n – 1)/2.

K1 K2 K3 K4 K5 K6

2. Graf Lingkaran

Graf lingkaran adalah graf sederhana yang setiap simpulnya berderajat dua. Graf lingkaran dengan n

simpul dilambangkan dengan Cn.

3. Graf Teratur (Regular Graphs)

Graf yang setiap simpulnya mempunyai derajat yang sama disebut graf teratur. Apabila derajat setiap

simpul adalah r, maka graf tersebut disebut sebagai graf teratur derajat r. Jumlah sisi pada graf teratur

adalah nr/2.

4. Graf Bipartite (Bipartite Graph)

Graf G yang himpunan simpulnya dapat dipisah menjadi dua himpunan bagian V1 dan V2, sedemikian

sehingga setiap sisi pada G menghubungkan sebuah simpul di V1 ke sebuah simpul di V2 disebut graf

bipartit dan dinyatakan sebagai G(V1, V2).

E. Lintasan Terpendek (Shortest Path)

Lintasan terperndek adalah lintasan minimum yang diperlukan untuk mencapai suatu tempat dari tempat

tertentu. Lintasan minimum yang dimaksud dapat dicari dengan menggunakan graf. Graf yang digunakan

adalah graf yang berbobot, yaitu graf yang setiap sisinya diberikan suatu nilai atau bobot. Dalam kasus ini,

bobot yang dimaksud berupa jarak dan waktu kemacetan terjadi.

Ada beberapa macam persoalan terpendek, antara lain :

a. Lintasan terpendek antara dua buah simpul tertentu.

b. Lintasan terpendek antara semua pasangan simpul.

c. Lintasan terpendek dari simpul tertentu ke semua simpul yang lain.

d. Lintasan terpendek antara dua buah simpul yang melalui beberapa simpul tertentu.

Aplikasi persoalan penentuan lintasan terpendek ini banyak sekali kita jumpai dalam kehidupan sehari-hari

:

a. Menentukan rute atau jalur terbaik yang harus ditempuh dari suatu kota untuk menuju ke kota lain.

b. Menentukan jalur komunikasi dua buah terminal komputer.

c. Menentukan jalur penerbangan dunia yang paling efektif untuk dilakukan.

d. Menentukan jarak terpendek/waktu tempuh tersingkat/ongkos termurah antara dua buah kota

e. Menentukan waktu tersingkat pengiriman pesan (message) antara dua buah terminal pada jaringan

komputer.

Algoritma Lintasan Terpendek

Algoritma Dijkstra ditemukan oleh Edger Wybe Dijkstra. Algoritma ini merupakan algoritma yang paling

terkenal untuk mencari lintasan terpendek. Algoritma Dijkstra diterapkan pada graf berarah, tetapi selalu

benar untuk graf tak-berarah.

Algoritma Dijkstra untuk mencari panjang lintasan terpendek dari vertek a ke vertek z di sebuah graf

berbobot G = (V, E, W).

1. Pertama-tama misalkan S = {a} dan B = V - {a}. Untuk setiap verteks t di B tentukan, L(t) = W(a,t),

(W(a,t) = ? bila (a,t) ? E).

2. Pilih verteks x di B yeng memiliki label terkecil terhadap S.

3. Jika x adalah verteks yang ingin dicapai, yaitu z, maka stop. Jika tidak, bentuk S’ = S ? {x} dan B’ = B -

{x}.

Untuk setiap verteks t di B’ tentukan labelnya terhadap S’ dengan rumus

L’(t) = min [L(t), L(x) + W(x,t)]

4. Ulangi langkah 2) dan 3) dengan memakai S’ sebagai S dan B’ sebagai B.

F. Lintasan dan Sirkuit Hamilton

Dalam teori graf, siklus yang menggunakan semua titik dan kembali ke titik semula dikenal dengan siklus

Hamilton (Hamilton Cycle). Sedangkan jika semua titik dilewati tepat satu kali tetapi tidak kembali ke titik

semula disebut Lintasan Hamilton (Hamilton Path). Graf yang memiliki lintasan atau siklus Hamilton

disebut Graf Hamilton sebagaimana disampaikan oleh Sir William Rowan Hamilton pada tahun 1856.

Sedangkan graf yang hanya memiliki lintasan Hamilton disebut graf semi-Hamilton.

(a) (b) (c)

Gambar : (a) graf yang memiliki lintasan Hamilton (misal: 3, 2, 1, 4)

(b) graf yang memiliki lintasan Hamilton (1, 2, 3, 4, 1)

(c) graf yang tidak memiliki lintasan maupun sirkuit Hamilton

Teorema Dasar

Teorema 1

Syarat cukup (jadi bukan syarat perlu) supaya graf sederhana G dengan n (? 3) buah simpul adalah graf

Hamilton ialah bila derajat tiap simpul paling sedikit n/2 (yaitu, d(v) ? n/2 untuk setiap simpul v di G).

Teorema 2

Setiap graf lengkap adalah graf Hamilton.

Teorema 3

Di dalam graf lengkap G dengan n buah simpul (n ? 3), terdapat (n - 1)!/2 buah sirkuit Hamilton.

Teorema 4

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). Jika n genap dan n ? 4, maka di dalam G terdapat (n - 2)/2

buah sirkuit Hamilton yang saling lepas.

Contoh :

Untuk graf G = (V,E) dalam Gambar 10.1, carilah sebuah siklus Hamilton.

Penyelesaian :

Sebuah siklus Hamilton untuk graf G adalah siklus (a, b, c, d, e, f, g, a).

Masalah Perjalanan Wiraniaga

Soal perjalanan wiraniaga berkaitan dengan masalah pencarian siklus Hamilton dengan panjang minimum

dalam sebuah graf berbobot G. Jika kita menganggap verteks-verteks dalam graf berbobot sebagai kota

dan bobot rusuk sebagai jarak, masalah perjalanan wiraniaga adalah mencari sebuah rute terpendek

sehingga wiraniaga tersebut dapat mengunjungi setiap kota satu kali, berawal dan berakhir pada kota

yang sama.

Persoalan Perjalanan Pedagang (Travelling Salesperson Problem - TSP)

Diberikan sejumlah kota dan jarak antar kota. Tentukan sirkuit terpendek yang harus dilalui oleh seorang

pedagang bila pedagang itu berangkat dari sebuah kota asal dan menyinggahi setiap kota tepat satu kali

dan kembali lagi ke kota asal keberangkatan (menentukan sirkuit Hamilton yang memiliki bobot

minimum).

Aplikasi TSP:

1. Pak Pos mengambil surat di kotak pos yang tersebar pada n buah lokasi di berbagai sudut kota.

2. Lengan robot mengencangkan n buah mur pada beberapa buah peralatan mesin dalam sebuah jalur

perakitan.

3. Produksi n komoditi berbeda dalam sebuah siklus.

Jumlah sirkuit Hamilton di dalam graf lengkap dengan n simpul: (n - 1)!/2.

Graf di atas memiliki (4 – 1)!/2 = 3 sirkuit Hamilton, yaitu:

I1 = (a, b, c, d, a) atau (a, d, c, b, a) ==> panjang = 10 + 12 + 8 + 15 = 45

I2 = (a, c, d, b, a) atau (a, b, d, c, a) ==> panjang = 12 + 5 + 9 + 15 = 41

I3 = (a, c, b, d, a) atau (a, d, b, c, a) ==> panjang = 10 + 5 + 9 + 8 = 32

Jadi, sirkuit Hamilton terpendek adalah I3 = (a, c, b, d, a) atau (a, d, b, c, a) dengan panjang sirkuit = 10 +

5 + 9 + 8 = 32.

Jika jumlah simpul n = 20 akan terdapat (19!)/2 sirkuit Hamilton atau sekitar 6 ? 1016 penyelesaian.

C. APLIKASI TEORI GRAF

a. Metode Pedagang Keliling

Metode ini diambil dari persoalan pedagang keliling yang harus mendatangi setiap kota tepat satu kali.

Kota akan kita anggap sebagai tempat tujuan pengantaran, selanjutnya akan kita sebut sebagai simpul.

Sedangkan jalan yang bisa dilewati akan kita sebut sebagai sisi. Sisi memiliki jarak tempuh yang kita sebut

sebagai bobot. Persoalannya tidak lain adalah menentukan lintasan Hamilton yang memiliki bobot

minimum pada graf yang kita dapatkan.

Menurut teori graf, persoalan semacam ini , jika setiap simpul memiliki sisi ke simpul lainnya maka graf ini

disebut graf lengkap dengan N buah simpul, maka Sirkuit Hamilton yang kita dapatkan mempunyai rumus:

Rumus ini dihasilkan karena (n-1) untuk simpul pertama, (n-2) untuk simpul kedua, dan seterusnya untuk

simpul berikutnya. Dan perlu dibagi dua karena lintasan Hamilton yang terjadi terhitung 2 kali.

A B

D C

Misal pada gambar di atas, jarak A ke B 10, jarak A ke C 12, jarak A ke D 6, Jarak B ke C 5, jarak B ke D 11,

jarak C ke D 9. A adalah kantor jasa pengantar, B, C, D adalah tempat tujuan. Lintasan Hamilton ada = 3

sirkuit. Artinya kita mendapatkan 3 lintasan.

Lintasan pertama (A-B-C-D-A) atau (A-D-C-D-A)

A B

D C

Lintasan kedua (A-C-B-D-A) atau (A-D-B-C-A)

A B

D C

Lintasan ketiga (A-C-D-B-A) atau (A-B-D-C-A)

A B

D C

Dari ketiga lintasan yang ada akan menjadi referensi bagi metode selanjutnya.

b. Metode Jarak Terpendek

Pada metode ini yang akan kita gunakan adalah bobot yang ada pada graf tersebut. Kita akan

menggunakan algoritma Dijkstra. Algoritma ini juga sudah terkenal diantara teori lintasan terpendek.

Dengan pendekatan greedy kita dapat mendapatkan lintasan terpendek dengan membandingkan seluruh

lintasan yang kita miliki. Yang perlu diketahui kita menggunakan istilah lintasan untuk mewakili sirkuit

Hamilton yang didapat melalui metode sebelumnya.

Dengan melihat gambar lintasan pertama (A-B-C-D-A) atau (A-D-C-D-A)

A 10 B

6 5

D 9 C

Lintasan pertama yaitu (A-B-C-D-A) memiliki jarak tempuh sebesar 10+5+9+6=30

Lintasan kedua (A-C-B-D-A) atau (A-D-B-C-A)

A B

12 11

6 5

D C

Lintasan kedua yaitu (A-C-B-D-A) memiliki jarak tempuh sebesar 12+5+11+6=34

Lintasan ketiga (A-C-D-B-A) atau (A-B-D-C-A)

10

A B

12 11

D C

9

Lintasan ketiga yaitu (A-C-D-B-A) memiliki jarak tempuh sebesar 12+9+11+10=42

Dari ketiga lintasan pilih lintasan (A-B-C-D-A) karena memiliki jarak terpendek dari ketiga lintasasan.

B. Kasus

a. Graf Lengkap

Misalkan ada sebuah perusahaan pengantar bernama PT Antar. Perusahaan tersebut mengantar 4 buah

paket ke berbagai tempat. Tempat pertama adalah sebuah rumah di kawasan Pondok Indah yang berjarak

12 dari tempat pengantaran. Tempat kedua adalah sebuah toko di jalan Menteng yang berjarak 15.

Tempat ketiga adalah sebuah rumah yang berjarak 24. Tempat keempat adalah rumah yang berjarak 17.

Dan setiap tempat memiliki jalan ke tempat lainnya. Jarak antara tempat satu dengan tempat lainnya

direpresentasikan dengan kilometer. Dengan representasi gambar didapat graf berbobot sebagai berikut:

A

E B

D C

Anggap kantor PT. Antar sebagai A dan Tempat tujuan sebagai B, C, D, E. Jarak direpresentasikan sebagai

sisi.

Dari gambar diketahui jarak dari A ke B adalah 12, dari A ke C adalah 15 dari A ke D adalah 24, dari A ke E

adalah 17.

Jarak masing-masing tempat: jarak B ke C adalah 6, jarak B ke D adalah 14, jarak B ke E adalah 13, Jarak C

ke D adalah 8, jarak C ke E adalah 11. Jarak D ke E adalah 9.

Dengan metode pertama kita mencari kemungkinan lintasan yang bisa diambil. Dengan rumus (n-1)!/2 =

(5-1)!/2 = 12. Jadi ada 12 lintasan. Dengan menggabungkan dengan metode kedua kita bisa mencari

jaraknya sekalian.

Dengan menggunakan metode yang sudah ada diatas kita akan mengambil tempat tujuan sebagai sebuah

simpul. Masing masing simpul diberi tanda Alfabet. Lalu ambil yang berupa lintasannya saja. Hilangkan sisi

yang tidak dilewati. Lalu hitung bobotnya.

Lintasan pertama adalah (A-B-C-D-E-A)

A

E B

D C

Lintasan ini mempunyai panjang 12 + 6 + 8 + 9 + 17 = 52

Lintasan kedua (A-B-C-E-D-A)

A

E B

D C


Lintasan ketiga (A-B-E-D-C-A)

A

E B

D C


Lintasan keempat (A-B-E-C-D-A)

A

E B

D C


Lintasan kelima (A-B-D-C-E-A)

A

E B

D C


Lintasan Keenam (A-B-D-E-C-A)

A

E B

D C


Lintasan ketujuh (A-C-B-D-E-A)

A

E B

D C

Lintasan ini mempunyai panjang 15+6+14+9+17=61

Lintasan kedelapan (A-C-B-E-D-A)

A

E B

D C


Lintasan kesembilan (A-C-D-B-E-A)

A

E B

D C


Lintasan kesepuluh (A-C-E-B-D-A)

A

E B

D C


Lintasan kesebelas (A-D-B-C-E-A)

A

E B

D C


Lintasan keduabelas (A-E-B-C-D-A)

A

E B

D C


Dengan mengambil lintasan A-B-C-D-E-A dengan panjang 52 kilometer, kita mendapatkan lintasan yang

terpendek

b. Graf Tak Lengkap

Jika graf tak lengkap, maka persoalan tidak bisa diselesaikan dengan rumus (n-1)!/2. Harus dicari sirkuit

Hamiltonnya dengan cara manual atau cara biasa. Setelah itu langkahnya tetap sama yaitu dengan

membandingkan sirkuit Hamiltonnya. Contoh graf tak lengkap misalnya, PT. Antar harus mengirim paket

ke 5 tempat dimana 2 tempat tidak bisa diakses langsung. 2 tempat tersebut hanya bisa diakses melewati

3 tempat lainnya dan antara kedua tempat tadi tidak mempunyai sisi.

Gambar graf dari graf tak lengkap di atas

B C

A D

F E

Jarak A ke B adalah 10, jarak A ke D adalah 20, jarak A ke F adalah 12, jarak B ke C adalah 7, jarak B ke E

adalah 15, jarak C ke D adalah 8, jarak C ke F adalah 14, jarak D ke E adalah 9, jarak E ke F adalah 6.

Sekarang kita anggap A sebagai tempat PT. Antar, sedangkan B-F adalah tempat tujuan. Cari sirkuit

Hamilton yang ada.

Sirkuit hamiltonnya:

? (A-B-C-D-E-F-A)

? (A-B-C-F-E-D-A)

? (A-B-E-F-C-D-A)

? (A-B-E-D-C-F-A)

? (A-F-E-B-C-D-A)

? (A-F-C-B-E-D-A)

Lalu setelah ada sirkuit Hamiltonnya maka dengan cara yang sama kita buat grafnya menurut sirkuit

Hamilton.

Lintasan pertama (A-B-C-D-E-F-A)

B C

A D

F E

Mempunyai panjang lintasan sebesar 10 + 7 + 8 + 9 + 6 + 12 = 52

Lintasan kedua (A-B-C-F-E-D-A)

B C

A D

F E


Lintasan ketiga (A-B-E-F-C-D-A)

B C

A D

F E


Lintasan keempat (A-B-E-D-C-F-A)

B C

A D

F E


Lintasan kelima (A-F-E-B-C-D-A)

B C

A D

F E


Lintasan keenam (A-F-C-B-E-D-A)

B C

A D

F E


Dengan mengambil lintasan A-B-C-D-E-F-A dengan panjang 52 kilometer, kita mendapatkan lintasan yang

terpendek.

Dengan memilih lintasan terpendek maka perusahaan jasa tersebut bisa mengurangi biaya pengeluaran

untuk transportasi. Dengan begitu bisa menekan pengeluaran, dari segi bahan bakar. Akan tetapi hal ini

masih di luar pertimbangan faktor-faktor yang menghambat perjalanan, seperti lebar jalan, rambu-rambu

dan lampu-lampu lalu lintas, serta kondisi jalan, dan tidak memungkinkan adanya penentuan satu arah

atau dua arah, serta penutupan jalan

Seperti yang kita ketahui metode pedagang keliling akan mudah dilakukan jika grafnya adalah graf

lengkap. Jika tidak lengkap, maka tidak bisa menggunakan rumus (n-1)!/2 untuk menentukan jumlah

lintasan. Akan tetapi mencari sirkuit Hamilton masih bisa.

Jika persoalan yang ditemui tidak terdapat sirkuit hamilton maka metode pertama tidak bisa digunakan.

Jadi pencarian harus lewat manual.

Aplikasi pada jumlah simpul yang banyak (lebih dari 5) akan membuat manusia sulit dalam

menghitungnya. Jadi sebaiknya serahkan penghitungan kepada program komputer.

Persoalan ini juga mengungkap permasalahan transportasi kita. Jika kita mengaplikasikan metode diatas

untuk cara kita bepergian, maka kita juga bisa mendapat keuntungan dari penghematan bahan bakar.

DAFTAR PUSTAKA

Anonim, 2008. Algoritma Dijkstra. http://id.wikipedia.org/wiki/. Diakses 5 Desember 2008 pukul 19. 00

Anonim, 2008. Theorygraph http://www.en.wikipedia.org/. Diakses 5 Desember 2008 pukul 19. 00

Munir, Rinaldi. 2006. Matematika Diskrit Edisi Keempat. Bandung. Informatika

Santoso, Judhi S. (1993). Catatan Kuliah Teori Graph dan Aplikasinya. Teknik Informatika, ITB.

BAB I

PENDAHULUAN

Konsep informasi memegang peranan penting dalam memahami, berkomunikasi dengan aspek-aspek

yang berhubungan dengan komputer. Konsep informasi ini menjadi lebih penting lagi jika dikaitkan dengan

komunikasi.

Tujuan proses komunikasi adalah menyampaikan atau mengirimkan informasi dari suatu sumber ke satu

atau lebih tujuan. Untuk berhasilnya suatu proses komunikasi diperlukan suatu bahasa untuk menyandikan

informasi terlebih dahulu sebelum informasi tersebut dikirm. Penyandian informasi ini mutlak diperlukan

agar para programmer yang akan menerima informasi mengetahui dengan pasti arti dan maksud dari

informasi yang dikirm.

Dengan demikian, dalam menulis suatu program, yang harus diperhatikan pertama kali adalah bagaimana

memahami persoalan yang dihadapi sehingga tidak salah menginterpretasikan suatu informasi ke dalam

bentuk yang mempunyai nilai logical validate untuk menyelesaikan suatu masalah.

BAB II

TEORI SINGKAT ALGORITMA

2.1 Pengertian Algoritma

Algoritma berasal dari kata algoris dan ritmis, yang pertama kali diungkapkan oleh Abu Ja’far Mohammed

Ibnu Musa al Khowarizmi (825 M) dalam buku AL-Jabr Wa-al Muqabala.

Sedangkan dalam bidang pemrograman, algortima didefinisikan sebagai suatu metode khusus yang tepat

dan terdiri dari serangkaian langkah yang terstruktur dan dituliskan secara sistematis yang akan

dikerjakan untuk menyelesaikan suatu masalah dengan bantuan komputer.

Hubungan antara algoritma, masalah dan solusi dapat digambarkan sebagai berikut :

http://www.en.wikipedia.org/

http://id.wikipedia.org/wiki/

MASALAH ALGORITMA SOLUSI

Proses dari masalah hingga terbentuk suatu algoritma disebut tahap pemecahan masalah, sedangkan

tahap dari algoritma hingga terbentuk suatu solusi disebut dengan tahap implementasi. Solusi yang

dimaksud adalah suatu program yang merupakan implementasi dari algoritma yang disusun.

Algoritma pemrograman yang baik memiliki ciri-ciri sebagai berikut :

Memiliki logika perhitungan / metode yang tepat dalam memecahkan masalah,

Menghasilkan output yang tepat dan benar dalam waktu yang singkat,

Ditulis dengan bahasa yang standar secara sistematis dan rapi sehingga tidak menimbulkan arti ganda,

Ditulis dengan format yang mudah dipahami dan diimplementasikan ke dalam bahasa pemrograman,

Semua operasi yang dibutuhkan terdefinisikan dengan jelas,

Semua proses harus selalu berakhir setelah sejumlah langkah dilakukan.

2.2 Penyajian Algoritma

Algoritma merupakan pola pikir yang terstruktur yang berisi tahap-tahap penyelesaian masalah, tahap-

tahap itu dapat disajikan dengan mengunakan dua teknik, yaitu teknik tulisan dan gambar.

Penyajian algoritma dalam bentuk tulisan biasanya menggunakan metode structure english dan

pseudocode, sedangkan penyajian algoritma dengan teknik gambar biasanya menggunakan metode

strucuture chart, hierarchy plus input- process-output, flowchart dan Nassi Schneiderman chart.

Strucuture English merupakan alat yang cukup efisien untuk menggambarkan suatu algoritma. Basis dari

structure English adalah bahasa Inggris, tetapi juga dapat digunakan dalam bahasa Indonesia. Oleh karena

bahasa manusia yang digunakan sebagai dasar penggambaran algoritma, maka strucuture English lebih

tepat untuk menggambarkan suatu algoritma yang akan dikomunikasikan kepada pemakai sistem.

Sedangkan pseudocode berarti kode yang mirip dengan kode pemrograman yang sebenarnya.

Pseudocode berasal dari kata pseudo yang berarti imitasi atau mirip atau menyerupai, dan code berarti

program. Pseudocode ditulis berbasis pada bahasa pemrograman seperti BASIC, PASCAL, atau C, sehingga

lebih tepat digunakan untuk menggambarkan algoritma yang akan dikomunikasikan pada programmer.

Pseudocode lebih rinci dari structure English, misalnya dalam menyatakan tipe data yang digunakan.

Dalam penulisan structure English dan Pseudocode juga mengenal struktur penulisan program seperti

sequence structure selection structure dan looping structure.

2.2.1 Struktur Urut pada Structure English dan Pseudocode

Struktur ini terdiri dari sebuah instruksi atau blok instruksi yang tidak mempunyai perulangan atau

keputusan di dalamnya. Contoh structure English (Indonesia) adalah sebagai berikut :

Inisiasi dan pemberian nilai awal variabel

Baca data panjang dan lebar empat persegi panjang

Hitung luas empat persegi panjang sama dengan panjang dikalikan dengan lebar

Tampilkan hasil perhitungan

Sedangkan bentuk Struktur Urut pada Pseudocode adalah sebagai berikut :

Program Hitung_Luas_Persegi_Panjang;

Var Panjang : Integer;

Lebar : Integer;

Luas : Integer;

Begin

Writeln("Panjang Persegi Panjang :");

Read(Panjang);

Writeln("Lebar Persegi Panjang :");

Read(Lebar);

Luas:= Panjang * Lebar;

Writeln("Luasnya", Luas);

End.

2.2.2 Struktur Keputusan pada Structure English dan Pseudocode

Selection structure merupakan struktur logika guna mengambil suatu keputusan. Pada struktur ini dapat

digunakan instruksi-instruksi seperti IF-THEN atau struktur CASE. Berikut ini contoh penulisan selection

strucuture pada structure English (Indonesia);

Inisiasi variabel,

Baca data nilai siswa,

Jika nilai siswa lebih besar dari 60 maka status sama dengan lulus, jika tidak maka status sama dengan

gagal,

Cetak status siswa.

2.2.3 Struktur Perulangan pada Structure English dan Pseudocode

Suatu perulangan diterapkan pada situasi dimana suatu instruksi atau grup dari instruksi diproses

berulang kali sampai kondisi yang diinginkan terpenuhi. Pada struktur perulangan ini dapat digunakan

instruksi FOR, REPEAT-UNTIL, DO-WHILE. Berikut ini contoh penulisan looping structure English (Indonesia);

Inisiasi variabel yang digunakan,

Tentukan nilai awal hitungan,

Bila sepuluh hitungan belum mencapai lebih besar dari sepuluh, maka ulangi blok instruksi berikut ini:

Cetak kata ‘ MERDEKA’

Þ Hitungan ditambah satu

Selesai.

Pada structure English terdapat beberapa gaya penulisan yang telah banyak digunakan. Gaya penulisan

tersebut antara lain :

Common Style (menggunakan huruf besar di awal dan selanjutnya huruf kecil semua);

Capitalized Common Style (menggunakan huruf besar semua);

Outline Common Style (dengan menggunakan nomor urut);

Narative Style (berbentuk uraian);

Gaya lain (tiap kata kunci ditulis dengan huruf besar semua).

Aturan Penulisan Pseudocode

Pada pseudocode terdapat beberapa aturan penulisan agar pseudocode mudah dipahami dan dimengerti

oleh para pemrogram. Aturan penulisan tersebut antara lain :

Tulis satu pseudocode suatu instruksi pada satu baris.

Pisahkan modul-modul atau kelompok pseudocode instruksi dengan memberikan spasi beberapa baris

untuk mempermudah pembacaan.

Bedakan bentuk huruf dalam penuluisan pseudocode dimana pseudocode instruksi ditulis dengan huruf

kapital, sedangkan komentar atau variabel dalam huruf kecil.

Berikanlah tabulasi yang berbeda untuk penulisan pseudocode instruksi-instruksi yang berada dalam

kalang (loop) atau struktur kondisional.

Lakukan pembatasan jumlah baris pseudocode instruksi setiap modulnya, misalnya 50-75 baris instruksi

per modul, sehingga terlalu panjang.

BAB III

ALGORITMA MATRIKS ZERO ONE

Matriks zero one adalah matriks yang hanya memiliki elemen-elemen bernilai 0 (false) atau 1 (true). Suatu

matriks zero one dapat memiliki sifat sebagai berikut :

reflektif

simetri

anti simetri

Kasus :

Membuat matriks zero one berordo n X n berdasarkan Input yang diberikan oleh user dan dicari sifat relasi

dari matriks tersebut.

Solusi :

Menerima masukan berupa jumlah titik relasi (n) dan mengalokasikan menjadi ordo dari matriks zero one

yang akan dibuat (n X n)

Menerima masukan berupa identitas relasi untuk setiap titik yaitu 0 jika false/salah dan 1 jika true/benar

Membuat matriks zero one n X n dengan nilai masing-masing titik sesuai dengan input yang diberikan

untuk setiap baris dan kolom

Memberikan keterangan tentang sifat dari matriks zero one tersebut

Matriks zero one tersebut akan memiliki sifat reflektif jika nilai pada semua baris - kolom yang berindeks

sama adalah true (1)

Matriks zero one tersebut akan memiliki sifat simetri jika nilai pada semua [baris, kolom] sama dengan

nilai pada [kolom, baris]; selain itu bersifat anti simetri

Representasi relasi dengan menggunakan matriks zero one ini dalam bahasa pemrograman Pascal adalah

sebagai berikut :

Program Representasi_Relasi_Matriks_Zero_One;{ iYAN --- Beta 0.10 Oct 10, 1998 on VisiTech Lab. This

computer program is protected by copyright law. Unathorized reproduction or distribution may result in

severe civil and criminal

penalties, and will be prosecuted to the maximum extent possible

under the law.

Visit "VisiTech" for updates this program. Get it now !

WorkShop : Kaliurang Street km 14.25 (Roda Jaya Group)

Thank`s for evaluate this beta version, you can get full version of

this program. }

Uses Crt;

Var i : byte; {indeks perulangan baris }

j : byte; {indeks perulangan kolom }

Jml_Ttk_Relasi : byte; {input jumlah titik relasi matriks

zero one yang akan dibentuk }

Identitas : array[1..100, 1..100] of boolean;

{array penyimpan nilai tiap titik dari

matriks zero one yang dimasukkan,

ukuran matriks yang dimasukkan

dibatasi hingga 100 X 100 }

Procedure Pendahuluan;

Begin

{ not available on this beta version, okay ! }

End;

Procedure Masukan;

Var ID : char; {kondisi identitas masukan}

Begin

Repeat

Write ('Jumlah titik relasi [1..150] : ');

Readln(Jml_Ttk_Relasi);

Until (Jml_Ttk_Relasi > 0) and (Jml_Ttk_Relasi < 151);

Writeln;

Writeln ('Masukkan identitas tiap titik pada matriks ',

Jml_Ttk_Relasi,' X ',Jml_Ttk_Relasi,' :');

For i := 1 to Jml_Ttk_Relasi do

For j := 1 to Jml_Ttk_Relasi do begin

Write(' Baris ',i,', Kolom ',j,' [Y/T] : ');

ID := Readkey;

If Upcase(ID) = 'Y' then

begin

Writeln(' 1 (True/Benar)');

Identitas[i, j] := True;

end

else

begin

Writeln(' 0 (False/Salah)');

Identitas[i, j] := False;

end;

end;

End;

Procedure Tampilan_Matriks;

Var Angka : byte;

Begin

Writeln;

For i := 1 to Jml_Ttk_Relasi do begin


If Identitas[i, j] then Angka := 1

else Angka := 0;

Write(' ', Angka);

end;

Writeln;

End;

End;

Procedure Proses;

Var Reflektif,

Simetri,

AntiSimetri : boolean;

R : byte; {indeks untuk cek reflektif }

Begin

Reflektif := False;

Simetri := True;

AntiSimetri := False;

i := 0;

j := 0;

R := 0;

{Cek apakah reflektif ?}

Repeat

Inc(i);

Inc(j);

If Identitas[i, j] = True then inc(R);

Until (i = Jml_Ttk_Relasi);

If R = Jml_Ttk_Relasi then Reflektif := True;

i := 0;

j := 0;

{Cek apakah simetri/antisimetri ?}

For i := 1 to Jml_Ttk_Relasi do


If (Identitas[i, j] <> Identitas[j, i]) and

not(AntiSimetri) then begin

AntiSimetri := True;

Simetri := False;

end;

end;

Writeln;

If Reflektif then Writeln('Matriks bersifat Reflektif');

If Simetri then Writeln('Matriks bersifat Simetri')

else Writeln('Matriks bersifat AntiSimetri');

End;

{Program Utama}

Begin

Clrscr;

Pendahuluan;

Masukan;

Tampilan_Matriks;

Proses;

Readln;

End.

{ Referensi : none! }

BAB IV

REFERENSI

Budi Sutedjo, S.Kom dan Michael AN, ALGORITMA dan TEKNIK PEMROGRAMAN, Andi Offset, 1997

P. Insap Santosa, M.Sc., Ir., DASAR-DASAR PEMROGRAMAN PASCAL TEORI dan PROGRAM TERAPAN, Andi

Offset, 1993.

matematika diskrit

Documents