Bagi NextGeners yang senang mempelajari matematika ataupun ilmu komputer pasti tidak asing dengan salah satu ilmu teori graf. Teori yang dikenal juga dengan teori grafik ini adalah cabang kajian yang mempelajari sifat-sifat grafik. Teori graf ini digambarkan dengan simpul-simpul yang disebut vertex(simpul) atau node yang dihubungkan melalui sisi (edge) atau busur(arc). Mudahnya penggambaran teori graf ini seperti jejaring media sosial facebook, dimana simpul adalah pengguna facebook dan terdapat busur yang menghubungkan jika antar pengguna tersebut berteman.
Bentuk umum teori Graf
Di dalam teori graf tersebut terdapat juga pewarnaan graf, apa lagi itu ya pewarnaan graf? Pewarnaan graf merupakan pewarnaan elemen sebuah graf yang terdiri dari pewarnaan elemen sebuah graf yang terdiri dari pewarnaan vertex(simpul), sisi (edge), dan wilayah (region) dengan label tertentu (warna) sehingga tidak ada dua simpul bertetangga yang memiliki warna sama. Warna yang digunakan untuk mewarnai objek juga diusahakan seminimal mungkin. Jumlah wana minumum yang dapat digunakan untuk mewarnai simpul disebut dengan bilangan kromatik.
Algortima yang terdapat dalam pewarnaan graf ini cukup banyak, misalnya ada algoritma Welch-Powell, algoritma Recursive Largest First, algoritma Backtracking, algoritma Welsh dan Powell.
Kalau begitu adakah contoh yang dapat diterapkan di kehidupan nyata dengan menggunakan algoritma dari pewarnaan graf tersebut? pastinya ada dong NextGeners, salah satunya bagi kalian yang suka berkendara di jalan raya, pasti kalian sering melihat lampu lalu lintas (traffic light) bila di dipersimpangan jalan, nah pengaturan lampu tersebut menggunakan salah satu algoritma dari pewarnaan graf.
Algoritma Welch-Powell merupakan salah satu algoritma yang digunakan dalam pengaturan lampu lalu lintas. Algoritma ini digunakan untuk mewarnai simpul suatu graf berdasarkan derajat tertinggi dari simpul-simpulnya. Selain sebagai pengatur lampu lalu lintas di jalanan teori graph dalam pewarnaan juga dapat diaplikasikan untuk penjadwalan, baik untuk jadwal kuliah maupun jadwal lainnya, agar seseorang tidak mengalami tabrakan jadwal nantinya dan seseorang tersebut dapat menjalankan jadwal nya dengan sesuai.
Bagaimana NextGeners jadi lebih seru jika kita bisa tahu pengaplikasian dari matematika di kehidupan sehari-hari bukan? Seperti yang sekarang kita tahu, ternyata untuk menyelesaikan permasalahan lalu lintas di persimpangan adalah menggunakan pewarnaan graf dengan salah satu algoritma Welch-Powell.
Apakah NextGeners tertarik dengan dunia matematika? Jika sangat menyukai dunia matematika dan ingin memberikan inovasi-inovasi di kehidupan sehari-hari menggunakan matematika maka Kita tunggu NextGeners untuk berinovasi di bidang Business Mathematics.
*Berikut STEM-Z lampirkan contoh penggunaan pewarnaan graf untuk lampu lalu lintas jalan, yang dilansir dari herlawati.com
Contoh Persimpangan Jalan yang diubah Menjadi Pewarnaan Graf
Contoh Persimpangan Jalan dengan jumlah lima simpang, dimana tiap jalan memiliki Jalan A, B, C, D, E.
Dari gambar jalur diatas kita dapat mengambil kesimpulan jalur yang boleh melintas dari A ke B, A ke C, A ke D dan seterusnya, sehingga dapat dikelompokan seperti gambar disamping (menjadi simpul).
Menentukan ruas untuk menghubungkan 2 simpul yang saling melintas atau bersebrangan, pada gambar 1 diatas terlihat bahwa jalur AB, dan BD, saling berseberangan, maka kita hubungkan simpul AB dam BD dengan garis yang disebut ruas, dan kita akan memberikan ruas pada semua jalur yang bersebrangan.
Selanjutnya kita memberikan warna pada tiap simpul dengan cara seperti berikut:
- Gunakan Warna seminimal mungkin
- Simpul yang berdampingan atau /Terhubung langsung dengan ruas, tidak boleh berwarna sama
- Berikan warna yang sama pada simpul yang tidak terhubung secara langsung
- Simpul yang tidak terhubung dengan ruas atau simpul bebas, berarti lintasan tersebut boleh berlaku lampu hijau terus.
- Awal pewarnaan Bebas
kemudian kita mengelompokan warna tersebut:
Merah => AC, AD
Coklat => BD, EB
Kuning => EC
Hijau => ED, AB, BC
dari warna tersebut kita mendapatkan 3 fase pola lampu lalu lintas sebagai berikut
| Hijau | AC, AD, ED, AB, BC |
| Merah | BD, EB, EC |
| Hijau | BD, EB, ED, AB, BC |
| Merah | AC,AD, EC |
| Hijau | EC, ED, AB, BC |
| Merah | AC,AD, BD, EB |
Sumber Referensi:
https://www.scribd.com/doc/146038570/Soal-Pewarnaan-Graph
https://herlawati.com/2014/12/23/pewarnaan-coloring-pengaturan-warna-pada-lampu-lalu-lintas/
Sumber Gambar:
https://computerabode.files.wordpress.com/2015/05/screen-shot-2015-05-03-at-3-03-19-pm.png
https://id.wikipedia.org/wiki/Teori_graf
(Featured Image) https://www.pinterest.com/pin/568649890422149977/
[…] NextGeners masih ingat dengan pembahasan STEM-Z minggu lalu mengenai pemanfaatan teori graf? Kali ini STEM-Z akan membahas mengenai Social Network Analysis(SNA) yang masih berhubungan dengan […]