Adiwijaya, “Menariknya, Graf Berbasis Pewarnaan”

Ada hal menarik dari teori graf berbasis pewarnaan. Rupanya, pewarnaan pada suatu graf memiliki banyak aplikasi menarik dalam masalah penjadwalan seperti dalam kasus pengiriman file pada suatu jaringan komputer. Keunikan itu diungkapkan peneliti sekaligus dosen Pascasarjana Teknik Informatika Institut Teknologi Telkom (IT Telkom), Adiwijaya, Ssi, Msi, pada International Conference on Lattice path Combinatorics and Applications 2010 di Siena, Italy, Minggu-Rabu (4-7/7, dalam penelitian yang berjudul “Some Graphs in Cf2 based on f-coloring”.

Pada presentasi tersebut dijelaskan, setiap komputer direpresentasikan oleh titik v pada graf dan setiap proses transfer file yang sedang berlangsung antara dua komputer direpresentasikan oleh sisi e yang menghubungkan dua buah titik pada graf.Setiap komputer v memiliki port komunikasi yang terbatas sebesar f(v). Dengan asumsi bahwa waktu pengiriman setiap file adalah sama, penentuan waktu minimum yang diperlukan dalam proses pengiriman file secara simultan pada jaringan komputer tersebut identik dengan penentuan indeks f-kromatik graf G.

“Berdasarkan indeks f-kromatiknya, graf dapat dikelompokan dalam Cf1 atau Cf2, bergantung pada struktur graf dan fungsi f yang diberikan. Penentuan indeks f-kromatik suatu graf merupakan masalah NP-complete. Namun demikian, untuk beberapa kelas graf tertentu merupakan masalah polinomial. Seperti diketahui, bahwa banyak graf yang termasuk dalam Cf2 kelas lebih sedikit dibandingkan banyaknya graf yang termasuk dalam Cf1,” jelas Adiwijaya.

Pada penelitian ini dikaji syarat cukup agar suatu graf termasuk dalam Cf2. Dalam penelitian sebelumnya, peneliti dari China, Xia Zhang dan kawan-kawan (2008) memberikan syarat cukup bahwa graf teratur yang memiliki nilai f(v) ganjil untuk setiap titik memungkinkan graf tersebut termasuk dalam Cf2.

“Kami telah memperumum hasil penelitian tersebut, yaitu graf yang termasuk dalam Cf2 tidak perlu reguler dan nilai f(v) tidak perlu ganjil untuk seluruh titik melainkan sebagian saja. Teknik pembuktian dari teorema yang dihasilkan adalah kontradiksi,” kata Adiwijaya.

Menurut Adiwijaya, hasil penelitian ini merupakan kolaborasi peneliti dari tiga perguruan tinggi, yakni IT Telkom, ITB , dan UPC (Barcelona, Spain).

“Penelitian terhadap pewarnaan pada graf tidak hanya sampai di konfrensi ini saja. Namun kami akan membawa hasil penelitian ini ke International Journal,” ungkapnya.

Untuk mengikuti conference ini, Adiwijaya mendapatkan hibah bantuan seminar ke luar negeri dari Diten DIKTI Departemen Pendidikan Nasional. Ini merupakan hibah yang kedua, setelah pada tahun 2009 memperoleh hibah bantuan seminar ke Thailand untuk mengikuti international conference.

Sekilas Peneliti :

Adiwijaya, ayah dari tiga anak yang lahir di Majalengka 35 tahun yang lalu. Ia adalah dosen IT Telkom. Pengabdiannya sudah di mulai sejak tahun 2000. Kini ia tengah disibukan dengan mengajar pada program Pascasarjana S2 Teknik Informatika IT Telkom dan menyelesaikan penulisan disertasi pada program doktor di Institut Teknologi Bandung. Penulis pernah melakukan research visiting di Universitat Politecnica de Catalunya, Barcelona spanyol selama 3 bulan pada tahun 2009 atas biaya Ditjen DIKTI.