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 w (G) dan menentukan bilangan
khromatikc (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.
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 w (G) dan menentukan bilangan
khromatikc (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.
No comments:
Post a Comment