Perpustakaan Digital ITB

Konsep terhubung pelangi pertama kali diperkenalkan oleh Chartrand, dkk pada tahun 2009. Konsep ini muncul untuk meminimumkan penggunaan password dalam pengiriman jalur informasi rahasia antara agen-agen pemerintahan di Amerika Serikat. Misalkan G = (V (G);E(G)) graf hingga,tak berarah dan terhubung tak trivial, didefinisikan suatu pewarnaan sisi dari G; c : E(G) f1; 2; mg untuk suatu bilangan bulat m: Suatu lintasan P di G disebut sebagai lintasan pelangi jika setiap sisi pada lintasan P mempunyai warna yang berbeda. Misalkan setiap dua titik u; v 2 V (G) terhubung oleh lintasan pelangi, maka lintasan ini kita sebut sebagai lintasan pelangi uv: Suatu graf G disebut terhubung pelangi jika setiap dua titik u; v 2 V (G) terhubung oleh lintasan pelangi u v: Bilangan terhubung pelangi dari G; dinotasikan dengan rc(G) adalah minimum m sehingga graf G merupakan graf terhubung pelangi.