Perpustakaan Digital ITB

Misalkan ???? adalah suatu graf sederhana, terhubung, dan berhingga berorde ?????3 dan ???? memiliki suatu pewarnaan sisi. Suatu lintasan ???? di ???? disebut lintasan pelangi jika setiap sisi di ???? memiliki warna yang berbeda. Untuk ?????????(????), lintasan Steiner dari ???? adalah lintasan terpendek yang mengandung titik-titik di himpunan ????. Pewarnaan pelangi-3 kaku adalah suatu pewarnaan sisi graf ???? dengan properti untuk setiap himpunan ?????????(????) dengan |????|=3, terdapat suatu lintasan Steiner pelangi dari ????. Graf ???? dikatakan terhubung pelangi-3 kaku jika pada ???? dapat didefinisikan suatu pewarnaan pelangi-3 kaku. Minimum banyaknya warna yang dibutuhkan untuk membuat ???? memiliki pewarnaan pelangi-3 kaku disebut sebagai indeks pewarnaan pelangi-3 kaku dari ???? dan dinotasikan degan sebagai ????????????????3(????). Jelas bahwa tidak semua graf dapat memiliki pewarnaan pelangi-3 kaku. Oleh karena itu, pada Tugas Akhir ini ditentukan karakteristik dari graf yang terhubung pelangi-3 kaku dan dikaji batas atas dan batas bawah dari indeks pewarnaan pelangi-3 kaku dari graf, serta ditentukan ????????????????3(????) untuk beberapa kelas graf sederhana ????. Selain itu, juga dikaji ????????????????3 graf hasil operasi sisir sisi lintasan ???????? dengan suatu graf terhubung ????, dinotasikan dengan ?????????????????? ????. Diberikan pula syarat-syarat dari graf ???? agar graf ?????????????????? ???? terhubung pelangi-3 kaku. Kemudian dikaji batas atas dan batas bawah untuk ????????????????3(?????????????????? ????). Pada Tugas Akhir ini juga diberikan nilai ????????????????3(?????????????????? ????) untuk graf ???? berupa graf kipas ???????? berorde ????+1 dan graf siklik ???????? berorde ????.