Matematika Diskrit : Aplikasi Graf

📋 Daftar Isi

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:

Pak Pos mengambil surat di kotak pos yang tersebar pada n buah lokasi di berbagai sudut kota.
Lengan robot mengencangkan n buah mur pada beberapa buah peralatan mesin dalam sebuah jalur perakitan.
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:

I₁ = (a, b, c, d, a) → bobot = 10 + 12 + 8 + 15 = 45

I₂ = (a, c, d, b, a) → bobot = 12 + 5 + 9 + 15 = 41

I₃ = (a, c, b, d, a) → bobot = 10 + 5 + 9 + 8 = 32

Sirkuit Hamilton terpendek: I₃ = (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 × 10¹⁶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?“