Perpustakaan Digital ITB

Misalkan G adalah suatu graf terhubung sederhana berorde n dan didefinisikan suatu pewarnaan sisi-h c : E(G) ! f1; 2; : : : ; hg, h 2 N, sehingga dua sisi yang bertetangga boleh memiliki warna yang sama. Misalkan k adalah suatu bilangan bulat dengan k 2 f2; 3; : : : ; ng. Suatu pohon T di G disebut pohon pelangi jika tidak ada dua sisi di T yang memiliki warna sama. Misalkan S V (G) dengan jSj = k. Suatu pewarnaan sisi-h c pada G disebut pewarnaan sisi-h pelangi-k kuat jika untuk setiap himpunan S di G, terdapat suatu pohon pelangi berukuran minimum yang menghubungkan S. Indeks pelangi-k kuat graf G, dinotasikan dengan srxk(G), adalah h terkecil sehingga terdapat pewarnaan sisi-h pelangi-k kuat pada G. Indeks pelangi-k kuat memiliki aplikasi yang menarik dalam keamanan pertukaran informasi di suatu jaringan komunikasi. Sebagai contoh, apabila ingin dilakukan pertukaran informasi yang aman antara k orang, setiap jalur yang menghubungkan k orang tersebut harus diberikan kata kunci yang berbeda. Banyak kata kunci minimal yang dibutuhkan dalam suatu jaringan komunikasi sehingga setiap k orang dihubungkan oleh suatu jalur yang aman dan sependek mungkin direpresentasikan sebagai indeks pelangi-k kuat. Penentuan indeks pelangi-k kuat sebarang graf adalah NP-Complete. Oleh karena itu, pada disertasi ini difokuskan pada indeks pelangi-3 kuat. Pada disertasi ini, ditentukan karakterisasi graf dengan indeks pelangi-3 kuat sama dengan 2. Selain itu, ditentukan pula indeks pelangi-3 kuat beberapa kelas graf dan graf hasil operasi yang meliputi amalgamasi-sisi, hasil kali sisir-titik, hasil kali sisir-sisi, dan hasil kali korona. Operasi graf memiliki peranan penting dalam membentuk suatu jaringan komunikasi yang lebih besar dan kompleks.