Sabtu, 30 Juni 2007

Pewarnaan Graph

Ada tiga macam persoalan pewarnaan graph (graph colouring), yaitu pewarnaan simpul, pewarnaan sisi dan pewarnaan wilayah (region). Pembahasan kali ini hanya dibatasi pada pewarnaan simpul saja.

Pewarnaan simpul adalah memberi warna pada simpul-simpul di dalam graph sedemikian sehingga setiap dua simpul bertetanga mempunyai warna yang berbeda. Salah satu terapan penting pewarnaan graph adalah mewarnai peta (colouring of map). Di dalam persoalan pewarnaan graph, tidak hanya sekedar mewarnai simpul-simpul dengan warna berbeda dari warna simpul tetangganya saja, namun juga menginginkan jumlah macam warna yang digunakan sesedikit mungkin.

Jumlah warna minimum yang dapat digunakan untuk mewarnai simpul disebut bilangan kromatik graph G.

Graph

Secara geometri graph digambarkan sebagai sekumpulan noktah (simpul) di dalam bidang dua dimensi yang dihubungkan dengan sekumpulan garis (sisi). Graph dapat digunakan untuk merepresentasikan objek-objek diskrit dan hubungan antara objek-objek tersebut. Representasi visual dari graph adalah dengan menyatakan objek sebagai noktah, bulatan atau titik, sedangkan hubungan antara objek dinyatakan dengan garis. Sebagai contoh, peta jaringan jalan kereta api yang menghubungkan sejumlah kota di pulau Jawa. Sesungguhnya peta tersebut adalah sebuah graph, yang dalam ini kota dinyatakan sebagai bulatan sedangkan jalan dinyatakan sebagai garis. Dengan diberikannya peta tersebut, maka dapat diketahui apakah ada lintasan jalan antara dua buah kota. Selain itu, bila panjang jalan kereta api antara dua buah kota bertetangga diketahui, maka juga dapat ditentukan rute perjalanan tersingkat dari kota A ke kota B.

Dalam pemrograman komputer, graph dapat direpresentasikan dengan menggunakan beberapa macam representasi graph, antara lain adjacency matrix, incidency matrix dan adjacency list. Namun, saya merekomendasikan untuk menggunakan adjacency list karena lebih efisien dan efektif dalam pengkodean dan lebih menghemat memori.

Contoh Program Tugas Akhir Teknik Informatika

Hello, teman mahasiswa sekalian, perkenalkan nama saya Hanry Susanto. Saya berprofesi sebagai programmer di salah satu software house di Surabaya.

Akhir-akhir ini, saya sering mendapat banyak keluhan dari teman-teman satu kampus terutama adik-adik kelas saya pada jurusan Teknik Informatika bahwa mereka sering menghadapi kendala pembuatan tugas akhir (skripsi) mereka.

Oleh karena itu, saya bermaksud untuk membantu mahasiswa/i yang mengalami masalah dalam penyusunan tugas akhir Teknik Informatika dengan menyediakan contoh-contoh program yang dapat dijadikan referensi dalam pembuatan tugas akhir (skripsi) Teknik Informatika.

Pada blog ini, anda dapat menuliskan pertanyaan anda dengan memberikan comment terhadap posting ini dan mengisi tempat pengisian yang berada di bagian bawah dari blog ini (isikan nama dan alamat email anda), untuk mendapatkan contoh program executable (berekstensi *.exe) yang akan diberikan secara GRATIS.