Perpustakaan Digital ITB

Misalkan G adalah suatu graf terhubung yang diberi pewarnaan sisi, dengan aturan bahwa sisi-sisi yang bertetangga dapat memiliki warna yang sama. Suatu lintasan di G disebut lintasan pelangi jika tidak ada dua sisi yang berwarna sama pada lintasan tersebut. Bilangan terhubung pelangi dari G, dinotasikan dengan rc(G), adalah minimum banyaknya warna yang dibutuhkan untuk mewarnai sisi-sisi G sehingga setiap dua titik yang berbeda di G terhubung oleh suatu lintasan pelangi. Bilangan terhubung pelangi suatu graf dapat digunakan untuk memodelkan pengamanan komunikasi rahasia antar agen dalam jaringan komunikasi yang direpresentasikan oleh graf tersebut. Dalam setiap lintasan komunikasi antar dua agen bisa terdapat beberapa agen perantara. Untuk menjamin keamanan pengiriman informasi, diperlukan sandi yang berbeda untuk setiap hubungan langsung antar dua agen di lintasan tersebut. Sandi-sandi yang berbeda ini direpresentasikan sebagai warna-warna sisi graf. Untuk keperluan efisiensi penyimpanan data, banyaknya sandi yang digunakan harus minimum namun masih tetap dapat menjamin kerahasiaan komunikasi. Selain untuk memodelkan pengamanan pengiriman informasi dalam suatu jaringan komunikasi, beberapa hasil penelitian telah menunjukkan bahwa bilangan terhubung pelangi memiliki kaitan dengan sifat-sifat aljabar suatu grup hingga. Kaitan antara bilangan terhubung pelangi dengan sifat-sifar aljabar suatu grup hingga dikaji dalam penelitian-penelitian tentang bilangan terhubung pelangi grafgraf dari grup hingga. Dalam beberapa tahun terakhir, beberapa peneliti telah meneliti bilangan terhubung pelangi beberapa graf dari grup hingga, di antaranya adalah graf Cayley, graf non-commuting, graf pangkat tak berarah (undirected power graph), dan graf pangkat yang ditingkatkan (enhanced power graph). Namun semua penelitian yang telah dilakukan tersebut belum mengkaji hubungan antara bilangan terhubung pelangi suatu graf dari suatu grup hingga dengan elemenelemen noninvolusi, subgrup-subgrup Abel maksimal, dan subgrup-subgrup siklik di graf tersebut. Pada disertasi ini, dikaji bilangan terhubung pelangi tiga graf lainnya dari grup hingga, yaitu graf commuting, graf invers, dan graf pangkat tereduksi dari suatu grup hingga, serta hubungan bilangan terhubung pelangi ketiga graf tersebut dengan sifat-sifat aljabar grup hingga. Bilangan terhubung pelangi graf invers dari suatu grup hingga berkaitan dengan elemen-elemen noninvolusi selain elemen identitas di grup tersebut. Bilangan terhubung pelangi graf commuting dari suatu grup hingga berkaitan dengan subgrup-subgrup Abel maksimal di grup tersebut. Sedangkan bilangan terhubung pelangi graf pangkat tereduksi dari suatu grup hingga berkaitan dengan subgrup-subgrup siklik di grup tersebut. Elemen-elemen noninvolusi (jika ada), subgrup-subgrup Abel, dan subgrup-subgrup siklik merupakan bagian penting dari suatu grup hingga. Peneltian ini telah memperoleh beberapa hasil. Jika graf invers dari suatu grup hingga ? adalah suatu graf terhubung, maka ? memiliki himpunan pembangkit minimal yang seluruh anggotanya adalah elemen-elemen noninvolusi selain elemen identitas. Jika bilangan terhubung pelangi graf invers dari suatu grup hingga ? sama dengan k, dengan k ? 2, maka setiap elemen di ? merupakan hasil kali dari r elemen noninvolusi selain elemen identitas, dengan r ? k. Jika grup ? memiliki subgrup Abel maksimal berorde 2, bilangan terhubung pelangi graf commuting dari ? berkaitan erat dengan banyaknya subgrup Abel maksimal berorde 2 di ?. Jika grup ? tidak memiliki subgrup Abel maksimal berorde 2, bilangan terhubung pelangi graf commuting dari ? berkaitan erat dengan banyaknya subgrup Abel maksimal di ?. Selain itu, diperoleh bahwa bilangan terhubung pelangi graf pangkat tereduksi dari suatu grup hingga ? berkaitan erat dengan banyaknya elemen ? yang membangkitkan subgrup siklik berorde prima.