BILANGAN RAINBOW CONNECTION BERDASARKAN DERAJAT MINIMUM PADA GRAF

Abstract

Graf 𝐺𝐺=(𝑉𝑉,𝐸𝐸) terdiri dari 2 himpunan yaitu himpunan tak kosong 𝑉𝑉 dan himpunan 𝐸𝐸 yang mana elemen 𝑉𝑉 disebut titik dan elemen 𝐸𝐸 disebut sisi. Banyaknya sisi yang berhubungan dengan titik 𝑉𝑉 disebut derajat dan minimum dari banyaknya sisi yang berhubungan dengan titik 𝑉𝑉 pada graf 𝐺𝐺 disebut derajat minimum (𝛿𝛿(𝐺𝐺)). Salah satu topik yang dipelajari dalam pewarnaan pada graf adalah rainbow connection. Pewarnaan sisi di 𝐺𝐺 dikatakan rainbow connected jika setiap dua titik yang berbeda dihubungkan oleh lintasan rainbow. Bilangan rainbow connection dari graf terhubung 𝐺𝐺 ditulis 𝑟𝑟𝑟𝑟(𝐺𝐺) yaitu minimum dari banyaknya warna yang diperlukan untuk membuat 𝐺𝐺 bersifat rainbow connected. Tujuan dari penelitian ini adalah untuk menentukan bilangan rainbow connection dalam graf berdasarkan derajat minimumnya. Penelitian dilakukan dengan cara mencari bilangan rainbow connected untuk graf 2-terhubung. Langkah berikutnya dicari juga untuk kasus graf 2-terhubung yang tidak memuat jembatan. Tahap terakhir dari dua dua graf tersebut dilakukan pencarian bilangan rainbow connected untuk graf dengan derajat minimum 3. Hasil dari penelitian ini adalah untuk graf terhubung 𝐺𝐺, jika memiliki 𝛿𝛿≥3 maka memiliki bilangan rainbow connection lebih dari 5𝑛𝑛/6.
Kata Kunci :graf, derajat, bilangan rainbow connection.