ANALISA KONEKSI PELANGI DAN KONEKSI PELANGI KUAT PADA TOPOLOGI GRAF HASIL OPERASI

Abstract

Matematika diskrit adalah bagian dari matematika yang membahas segala sesuatu yang bersifat diskrit. Salah satu bagian dari matematika diskrit adalah teori graf yang saat ini banyak dikembangkan. Teori graf pertama kali muncul ketika Leonhard Euler yang berasal dari Swiss mencoba menyelesaikan permasala- han yang berkaitan dengan jembatan Konigsberg pada tahun 1736. Salah satu teori yang dikembangkan dalam teori graf adalah Koneksi Pelangi (Rainbow Connection). Koneksi Pelangi adalah pemberian warna pada sisi graf dengan syarat dua sisi yang bertetangga boleh diberi warna yang sama. Namun sisi yang masuk dalam lintasan pelangi tidak boleh ada dua sisi atau lebih yang memiliki warna sama, dimana lintasan pelangi (rainbow path) adalah sebuah lin- tasan yang terdapat dalam graf tersebut. Pewarnaan minimal dalam suatu graf disebut koneksi pelangi dilambangkan dengan rc. Sedangkan koneksi pelangi kuat merupakan pewarnaan pada lintasan u ¡ v terpendek dilambangkan dengan src.