Perpustakaan Digital ITB

Konsep pewarnaan pelangi lokasi menggabungkan pewarnaan titik-pelangi dan partisi pembeda graf. Pewarnaan titik-pelangi memiliki aplikasi dalam keamanan jaringan data dan komunikasi, sedangkan partisi pembeda graf memungkinkan identifikasi unik setiap objek dalam jaringan. Dengan menggabungkan kedua konsep ini, pewarnaan pelangi lokasi dapat meningkatkan kualitas pengamanan jaringan. Graf yang dikaji dalam disertasi ini terbatas untuk graf terhubung, sederhana, berhingga, nontrivial, dan tak berarah. Misalkan ? merupakan bilangan bulat positif dan G=(V (G),E(G)) merupakan graf. Pewarnaan-? titik-pelangi merupakan pemetaan f:V (G)?{1, 2, . . . , ?} sehingga setiap dua titik berbeda u dan v di V (G) dihubungkan oleh lintasan yang seluruh titik internalnya berbeda warna. Lintasan ini disebut lintasan-titik pelangi. Misalkan Ri merupakan himpunan titik berwarna i dan ?={R1,R2, . . . ,R?} merupakan partisi terurut dari V (G). Jarak titik v ke Ri adalah d(v,Ri)= min{d(v, x)|x?Ri}. Kode pelangi titik v di V (G) terhadap ? didefinisikan sebagai tupel-? rc?(v)=(d(v,R1), d(v,R2), . . . , d(v,R?)). Jika semua titik di V (G) memiliki kode pelangi berbeda, maka ? disebut partisi-? pembeda pada V (G). Jika fungsi f merupakan pewarnaan-? titik-pelangi dan ? merupakan partisi-? pembeda, maka f disebut pewarnaan-? pelangi lokasi pada G. Nilai ? terkecil sehingga terbentuk pewarnaan-? pelangi lokasi pada G disebut bilangan terhubung pelangi lokasi pada G, dilambangkan dengan rvcl(G). Permasalahan yang dikaji dalam penelitian disertasi ini difokuskan pada penentuan batas atas dan bawah yang ketat untuk bilangan terhubung pelangi lokasi pada sembarang graf hasil operasi kali sisir-titik dan hasil operasi kali sisir-sisi. Selain itu, ditentukan pula bilangan terhubung pelangi lokasi untuk beberapa kelas graf hasil dari operasi tersebut yang beberapa diantaranya dibuktikan dengan menggunakan himpunan dan bilangan kembar.