Penerapan Teori Graf dalam kehidupan sehari-hari

Penerapan Teori Graf dalam kehidupan sehari-hari

Penerapan Teori Graf dalam kehidupan sehari-hari - Teori graf sudah menjadi teori yang penting untuk dikuasai oleh pelajar. Namun seperti kata orang-orang bahwa teori akan menjadi suatu omong kosong belaka jika tidak dibarengi dengan penerapan dalam kehidupa.

Oleh karena itu, pada kesempatan kali ini mimin akan membagikan materi graf mengenai penerapan teori graf dalam kehidupan sehari-hari. Mimin yakin bahwa ini merupakan salah satu bagian materi yang sangat ditunggu-tunggu oleh sobat beautymatika karena pengetahuan pada dasarnya hanya dapat dirasakan jika sudah diterapkan dalam kehidupan. Penerapan ini menunjukan bahwa materi teori graf selama ini bukanlah materi yang abstrak. Bagi sobat beautymatika yang ketinggalan materi graf, sobat beautymatika dapat mempelajarinya disini.

Langsung saja mimin mengajak sobat beautymatika untuk mempelajari materi penerapan teori graf dalam kehidupan sehari-hari 😀

Daftar isi

1. Penerapan Teori Graf dalam Kehidupan
2. Persoalan Pedagang Keliling (TSP)
3. Persoalan Tukang Pos Cina (chinese postman problem)a
4. Pewarnaan graf
5. Penutup

Penerapan Teori Graf dalam Kehidupan

Secara umum penerapan teori graf sangatlah banyak dalam kehidupan. Dalam matematika, penerapan teori graf dibagi menjadi 3 bagian besar, yaitu persoalan pedagang keliling (TSP), persoalan tukang pos cina (Chinese postman problem), dan pewarnaan graf.

Persoalan Pedagang Keliling (TSP)

Persoalan pedagang keliling (TSP) merupakan penerapan teori graf yang umum dalam kehidupan. Persoalan pedagang keliling (TSP) adalah sebagai berikut :

“Diberikan sejumlah kota dan diketahui jarak antar kota. Tentukan tur terpondek yang harus dilalui oleh seorang pedagang bila pedagang tersebut berangkat dari kota asal dan menyinggahi setiap kota tepat satu kali dan kembali ke kota asal keberangkatan”

Beberapa hal penting yang perlu diperhatikan dari persoalan pedagang keliling (TSP) adalah :

1.     Tur terpendek memiliki arti sama dengan lintasan minimum yang ditempuh

2.     Setiap simpul (kota) hanya boleh dilalui sebanyak 1 kali saja

3.     Pedagang harus kembali ke titik asal

Berdasarkan 2 poin penting diatas, persoalan pedagang keliling (TSP) termasuk dalam penentuan sirkuit hamilton yang memiliki bobot minimum.

Contoh bentuk graf persoalan pedagang keliling (TSP)

Graf persoalan pedagang keliling

Aplikasi paling umum dari persoalan pedagang keliling (TSP) adalah pengambilan surat di kotak pos yang tersebar disuatu kota.

Persoalan Tukang Pos Cina (chinese postman problem)

Sobat beautymatika perlu memahami bahwa persoalan tukang pos cina memiliki perbedaan dengan persoalan pedaganng keliling (TSP). Persoalan tukang pos cini dirumuskan sebagai berikut :

“Seorang tukang pos cina akan mengantar surat ke alamat rumah disepanjang jalan disuatu daerah. Bagaiamana cara ia merencanakan rute perjalananmya yang mempunyai jarak terpendek dengan syarat melewati setiap jalan tepat satu kali dan kembali lagi ke tempat awal keberangkatan ?”

Terdapat 3 poin penting dari persoalan ini :

1.     Rute terpendek merupakan panjang lintasan/sisi minimum

2.     Setiap lintasan/siis hanya boleh dilewati satu kali

3.     Tukang pos harus kembali ke titik asal

Berdasarkan 3 poin penting diatas, maka persoalan tukang pos cina (chinese postman problem) merupakan penentuan sirkuit euler yang memiliki bobot minimum.

Contoh bentuk graf persoalan tukang pos cina (chinese postman problem)

Graf persoalan tukang pos cina

Aplikasi umum dari persoalan tukang pos cina (chinese postman problem) adalah pengambilan maupun pengantaran surat tukang pos ke rumah-rumah di suatu daerah.

Pewarnaan graf

Secara umum terdapat 2 macam pewarnaan graf, yaitu :

1.     Pewarnaan simpul

Merupakan pemberian warna pada simpul suatu graf

2.     Pewarnaan daerah

Merupakan pemberian warna pada sautu daerah graf

Syarat penting yang harus diketahui sobat beautymatika adalah baik pewarnaan simpul maupun pewarnaan daerah setiap daerah yang bertetangga harus memiliki warna yang berbeda. Selain itu sobat beautymatika juga dapat menentukan jumlah warna minimum yang dibutuhkan disuatu graf. Jumlah warna minimum yang dibutuhkan disuatu graf ini dinamakan bilangan kromatik. Simbol bilangan kromatik adalah x(G).

Contoh bilangan kromatik

x(G) = 3 (merah, hijau, kuning)

Khusus untuk pewarnaan simpul, terdapat beberapa teorema yang berlaku :

1.     Graf kosong memiliki x(G) = 1 warna

Ini disebabkan karena setiap simpul tidak terhubung

2.     Graf lengkap memiliki x(G) = n warna

Ini disebabkan karena semua simpul saling terhubung

3.     Graf bipartit memiliki x(G) = 2 warna

Ini disebabkan karena terdapat himpunan v1 dan v2 pada graf bipartite

4.     Graf lingkaran dengan n ganjil memiliki x(G) = 3, sedangkan jika n genap maka x(G) = 2

5.     Untuk sembarang pohon T memiliki x(G) = 2

Untuk bentuk graf lainnya tidak dapat dinyatakan secara pasti bilangan kromatiknya.

Contoh pewarnaan simpul dan pewarnaan daerah

x(G) = 2 (ungu dan pink)

x(G) = 3 (merah, hijau, kuning)

Penutup

Demkian materi penerapan teori graf dalam kehidupan sehari-hari yang dapat mimin bagikan untuk sobat beautymatika. Mimin yakin sobat beautymatika dapat memahami materi ini dengan baik. Tetap semangat belajar dan sampai jumpa di materi lainnya.

 

 

 

Bagikan Artikel ini