M. Salman A.N.
Penggunaan alat komunikasi tanpa kabel (wireless communication), seperti mobile phone, meningkat cepat pada beberapa tahun terakhir dan diperkirakan pada tahun-tahun mendatang akan tetap terjadi peningkatan bahkan akan sangat tinggi. Selain itu, sekarang ini sangat dimungkinkan terjadinya komunikasi yang melibatkan lebih dari 2 orang sekaligus. Untuk itu, diperlukan kemampuan yang baik dan ekonomis dalam manajemen penetapan frekuensi (frequency assignment). ‘Baik’ diartikan tidak terjadi interferensi. Ada pun tingkat dari interferensi bergantung kepada beberapa hal, antara lain jarak antara satu pemancar (transmitter) dengan pemancar yang lain, posisi geografi dari pemancar, kekuatan dari signal, dan kondisi cuaca. Sedangkan ‘ekonomis’ diartikan bahwa selang frekuensi yang digunakan harus seminimal mungkin. Banyak masalah penetapan frekuensi dimodelkan dalam teori graf sebagai variasi dari masalah pewarnaan graf (graph coloring). Kebanyakan dari variasi ini sangatlah sulit untuk diselesaikan (NP-hard problem). Karena itu, salah satu pendekatan yang dilakukan adalah mengembangkan heuristic algorithms untuk mendapatkan solusi yang ‘cukup baik’ secara efisien (yakni dalam polinomial time). Pendekatan lain adalah pegembangan teori untuk mendapatkan pengetahuan yang lebih dalam yang dapat dimanfaatkan untuk menyelesaikan masalah penetapan frekuensi. Pendekatan ketiga yang dilakukan adalah penentuan kelas-kelas khusus dari masalah umum sehingga solusi dari masalah tersebut pada kelas-kelas yang ditentukan dapat diselesaikan secara polinomial. Tujuan dari penelitian yang diusulkan ini adalah untuk dapat berkontribusi pada pendekatan ketiga di atas. Konsep tentang bilangan indeks k-pelangi muncul salah satunya karena termotivasi dari interpretasinya yang menarik dalam suatu jaringan komunikasi. Sebagai contoh, misalkan G diinterpretasikan sebagai suatu jaringan komunikasi. Akan disampaikan rute panggilan antara dua titik atau lebih banyak titik dalam suatu jalur dengan syarat masing-masing sambungan dalam rute yang menghubungkan semua titik tersebut diberikan suatu frekuensi yang berbeda. Ingin diminimalkan selang frekuensi yang digunakan pada jaringan tersebut. Ini memunculkan gagasan tentang definisi bilangan indeks k-pelangi dari suatu graf. Secara umum, pewarnaan m-sisi dari suatu graf G = (V;E ) adalah suatu fungsi yang mengkaitkan setiap sisi graf dengan suatu bilangan pada {1,2,...,m}. Selanjutnya, graf G dengan pewarnaan m-sisi dikatakan terindeks k-pelangi jika untuk setiap k titik dari G terdapat pohon dengan semua sisinya memperoleh warna berbeda yang menghubungkan k titik tersebut. Bilangan indeks k-pelangi dari G yang dinotasikan dengan rx (G) adalah m terkecil sehingga graf G terindeks k-pelangi. Dalam hal k = 2, bilangan ini dikenal juga dengan bilangan terhubung pelangi. Dengan demikian, konsep ini merupaka perumuman dari konsep bilangan terhubung pelangi. Penelitian ini akan memanfaatkan dan mengembangkan pengetahuan tentang pewarnaan graf dalam menyelesaikan masalah penetapan frekuensi, khususnya dalam pewarnaan terhubung pelangi yang telah mulai dilakukan tahun ini. Dalam penelitian ini, kami akan fokus pada permasalahan bilangan indeks k- pelangi pada beberapa kelas graf, serta pada graf yang dihasilkan dari operasi-operasi biner graf, antara lain operasi korona, perkalian silang, strong product, dan comb product. Operasi graf diperlukan antara lain untuk mendapatkan graf dengan struktur yang lebih kompleks. Hasil dari penelitian yang diusulkan ini akan disampaikan pada suatu konferensi internasional dan dipublikasikan pada empat jurnal internasional. Karena itu, hasil-hasil penelitian ini akan memberikan kontribusi keilmuan yang signifikan dalam bidang matematika diskrit, khususnya pada perkembangan pewarnaan graf, serta akan meningkatkan kerjasama penelitian dengan beberapa kolega dari luar negeri.