ANALISIS GRAF DALAM MENENTUKAN GRAF PERFECT

Salah satu aplikasi dari bilangan clique dan bilangan khromatik suatu graf G adalah pada graf perfect. Graf perfect adalah suatu graf yang memiliki bilangan clique dan bilangan khromatik yang sama. Bilangan clique ω(G) didefinisikan sebagai order maksimum dari subgraf komplit pada graf G. Bilangan Kromatik χ(G) adalah banyaknya warna minimum yang diperlukan untuk mewarnai titik-titik pada graf G sedemikian sehingga setiap titik-titik yang terhubung langsung mendapatkan warna yang berbeda. Penelitian ini bertujuan untuk menganalisis suatu graf yang memuat sirkuit Euler atau sirkuit Hamilton merupakan graf perfect atau bukan. Sirkuit Euler adalah sirkuit yang melewati masing-masing sisi tepat satu kali dan sirkuit Hamilton adalah sirkuit yang melalui tiap titik di dalam graf tepat satu kali.Berdasarkan pembahasan dalam skripsi ini diperoleh bahwa graf yang memuat sirkuit Euler adalah graf perfect sedangkan graf yang memuat sirkuit Hamilton bukan merupakan graf perfect.