Kajian tentang graf perfect

INDONESIA:

Pewarnaan titik pada graf G adalah pemberian warna untuk setiap titik pada graf G, sehingga tidak ada dua titik yang terhubung langsung mendapatkan warna yang sama. Banyaknya warna terkecil yang diberikan pada titik-titik di graf G sedemikian hingga untuk setiap dua titik yang terhubung langsung mendapatkan warna yang berbeda disebut dengan bilangan khromatik. Banyaknya titik yang dimiliki oleh graf G disebut dengan order dari G. Order maksimum dari subgraf komplit yang dapat dibentuk dari suatu graf G disebut dengan bilangan clique.

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.

Adapun langkah-langkah menentukan graf perfect adalah sebagai berikut:
1. Menentukan subgraf komplit maksimum yang dapat dibentuk dari graf G
2. Menentukan bilangan clique(G) dan menentukan bilangan khromatik (G) pada beberapa kasus untuk menentukan pola.
3. Pola yang diperoleh dinyatakan dengan teorema.
4. Membuktikan teorema.
Berdasarkan pembahasan dalam skripsi ini diperoleh bahwa graf kosong, graf komplit, graf bipartisi komplit, graf sikel genap, dan graf lintasan adalah graf perfect, karena masing-masing graf tersebut memiliki bilangan clique dan bilangan khromatik yang sama