Matematika Diskrit : Aplikasi Graf

Travelling Salesperson Problem (TSP)

Diberikan sejumlah kota dan diketahui jarak antar kota. Tentukan tur 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.

Penyelesaian:

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) โ†’ bobot = 10 + 12 + 8 + 15 = 45

I2 = (a, c, d, b, a) โ†’ bobot = 12 + 5 + 9 + 15 = 41

I3 = (a, c, b, d, a) โ†’ bobot = 10 + 5 + 9 + 8 = 32

Sirkuit Hamilton terpendek: I3 = (a, c, b, d, a) dengan bobot = 10 + 5 + 9 + 8 = 32

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

Chinese Postman Problem

Seorang tukang pos akan mengantar surat ke alamat-alamat sepanjang jalan di suatu daerah. Bagaimana ia merencanakan rute perjalanannya supaya ia melewati setiap jalan tepat sekali dan kembali lagi ke tempat awal keberangkatan?

โ†’ Menentukan sirkuit euler di dalam graf

Lintasan yang dilalui tukang pos: A, B, C, D, E, F, C, E, B, F, A.Jika graf yang merepresentasikan persoalan adalah graf Euler, maka sirkuit Eulernya mudah ditemukan.

Jika grafnya bukan graf Euler, maka beberapa sisi di dalam graf harus dilalui lebih dari sekali.

Jadi, pak pos harus menemukan sirkuit yang mengunjungi setiap jalan paling sedikit sekali dan mempunyai jarak terpendek

Persoalan tukang pos Cina menjadi:

Seorang tukang pos akan mengantar surat ke alamat-alamat sepanjang jalan di suatu daerah. Bagaimana ia merencanakan rute perjalanannya yang mempunyai jarak terpendek supaya ia melewati setiap jalan paling sedikit sekali dan kembali lagi ke tempat awal keberangkatan?


Pewarnaan Graf

Ada dua macam: pewarnaan simpul dan pewarnaan sisi.

Pewarnaan simpul: memberi warna pada simpul-simpul graf sedemikian sehingga dua simpul bertetangga mempunyai warna berbeda.

Aplikasi pewarnaan graf: mewarnai peta. Peta terdiri atas sejumlah wilayah. Wilayah dapat menyatakan kecamatan, kabupaten, provinsi, atau negara.

Peta diwarnai sedemikian sehingga dua wilayah bertetangga mempunyai warna berbeda.

Nyatakan wilayah sebagai simpul dan batas antar dua wilayah bertetangga sebagai sisi.

Mewarnai wilayah pada peta berarti mewarnai simpul pada graf yang berkoresponden.

Setiap wilayah bertetangga harus mempunyai warna berbeda โž” warna setiap simpul harus berbeda.

Keterangan:

(a) Peta
(b) Peta dan graf yang merepresentasikannya,
(c) Graf yang merepresentasikan peta,
(d) Pewarnaan simpul, setiap simpul mempunai warna berbeda,
(e) Empat warna sudah cukup untuk mewarnai 8 simpul


Bilangan Kromatik

Bilangan kromatik adalah jumlah minimum warna yang dibutuhkan untuk mewarnai peta.

Suatu graf G yang mempunyai bilangan kromatis k dilambangkan dengan X(G) = k.


Lintasan Terpendek

Bobot yang berhubungan dengan suatu garis pada graf juga dapat diaplikasikan pada graf berarah.

Prinsip dan arti bobot pada graf berarah sama dengan bobot pada graf tak bearah, yaitu menyatakan seberapa kuat hubungan antara 2 titik yang arahnya ditunjukkan dengan arah garis.

Salah satu aplikasi graf berarah berlabel yang sering dipakai adalah mencari path terpendek diantara 2 titik.

Sebagai contoh, terdapat banyak jalan yang menghubungkan kota Yogya ke Jakarta. Pertanyaan yang sering muncul adalah : โ€œjalur mana yang paling dekat?โ€œ

Algoritma Warshall

W = W0

Untuk k = 1 hingga n, lakukan :

untuk i = 1 hingga n, lakukan :

untuk j = 1 hingga n lakukan :

jika W[i,j] > W[i,k] + W[k,j] maka

tukar W[i,j] dengan W[i,k] + W[k,j]

W* = W

W0 adalah matriks hubung graf berarah berlabel mula-mula.

W* adalah matriks hubung minimal dengan wij* = path terpendek dari titik vi ke vj.


Algoritma Dijkstraa

L = { };

V = {V2, V3, …, Vn}

Untuk i = 2, …, n, lakukan D(i) = W(1,i)

Selama Vn โˆ‰ L lakukan :

a. Pilih titik Vk โˆˆ V-L dengan D(k) terkecil.

L = L โˆช {Vk}

b. Untuk setiap Vj V-L lakukan :

Jika D(j) > D(k) + W(k,j) maka ganti D(j) dengan D(k) + W(k,j)

Untuk setiap Vj โˆˆ V, w*(1,j) = D(j)

Keterangan:

V(G) = {V2, V3, …, Vn }

L = Himpunan titik-titik ฯต V(G) yang sudah terpilih dalam jalur path terpendek

D(j) = Jumlah bobot path terkecil dari v1 ke vj

w(i,j) = Bobot garis dari titik vi ke titik vj

w*(1,j) = Jumlah bobot path terkecil dari v1 ke titik vj


Sumber : Buku Matematika Diskrit (Rinaldi Munir)


Materi Lengkap

Silakan baca juga beberapa artikel menarik kami tentang Graf, daftar lengkapnya adalah sebagai berikut.


Tonton juga video pilihan dari kami berikut ini


Bagikan ke teman-teman Anda

Contact Us

How to whitelist website on AdBlocker?

How to whitelist website on AdBlocker?

  1. 1 Click on the AdBlock Plus icon on the top right corner of your browser
  2. 2 Click on "Enabled on this site" from the AdBlock Plus option
  3. 3 Refresh the page and start browsing the site
error: Content is protected !!
Up