Pewarnaan titik pada graf G = (V (G), E(G)) adalah pemberian warna
untuk setiap titik pada graf sehingga tidak ada dua titik yang terhubung langsung
berwarna sama Suatu pewarnaan titik f dari graf G disebut pewarnaan
l - Backbone dari (G,H) jika memenuhi f (u) - f (v) ³ l . Bilangan terkecil k
dimana terdapat pewarnaan l - Backbone f :V ®{1,2,3,...,k } disebut bilangan
pewarnaan l - Backbone dan dilambangkan dengan BBCl (G,H) . Graf yang
digunakan dalam penelitian ini adalah graf split. Graf split adalah graf G yang
himpunan titiknya dapat dipartisi kedalam clique dan himpunan bebas. Bentuk
dari graf split merupakan sub bagian dari bagian graf perfect. Oleh karena itu graf
split memenuhic (G) =w (G) . Selanjutnya, pada pokok bahasan nanti penulis
akan menjelaskan tentang bagaimana menentukan bilangan pewarnaan l -
backbone pada graf split.
Tulisan ini menyajikan proses atau langkah-langkah untuk menentukan
bilangan pewarnaan l -backbone pada graf split. Adapun langkah-langkahnya
adalah sebagai berikut:
1. Menentukan graf split dan mengidentifikasi subgraf-subgraf komplit dan
bilangan khromatiknya.
2. Memberikan 1 contoh Spanning subgraph (Backbone) yang memuat subgraf
komplit maksimum dari graf split dan memuat lintasan Hamilton.
3. Memberikan pewarnaan titik pada backbone lintasan Hamilton dari graf split.
Untuk penulisan skripsi selanjutnya, penulis menyarankan untuk mengkaji
masalah penentuan bilangan pewarnaan l -backbone pada graf yang lain
misalnya graf kubus dengan menggunakan backbone yang lebih tinggi.
untuk setiap titik pada graf sehingga tidak ada dua titik yang terhubung langsung
berwarna sama Suatu pewarnaan titik f dari graf G disebut pewarnaan
l - Backbone dari (G,H) jika memenuhi f (u) - f (v) ³ l . Bilangan terkecil k
dimana terdapat pewarnaan l - Backbone f :V ®{1,2,3,...,k } disebut bilangan
pewarnaan l - Backbone dan dilambangkan dengan BBCl (G,H) . Graf yang
digunakan dalam penelitian ini adalah graf split. Graf split adalah graf G yang
himpunan titiknya dapat dipartisi kedalam clique dan himpunan bebas. Bentuk
dari graf split merupakan sub bagian dari bagian graf perfect. Oleh karena itu graf
split memenuhic (G) =w (G) . Selanjutnya, pada pokok bahasan nanti penulis
akan menjelaskan tentang bagaimana menentukan bilangan pewarnaan l -
backbone pada graf split.
Tulisan ini menyajikan proses atau langkah-langkah untuk menentukan
bilangan pewarnaan l -backbone pada graf split. Adapun langkah-langkahnya
adalah sebagai berikut:
1. Menentukan graf split dan mengidentifikasi subgraf-subgraf komplit dan
bilangan khromatiknya.
2. Memberikan 1 contoh Spanning subgraph (Backbone) yang memuat subgraf
komplit maksimum dari graf split dan memuat lintasan Hamilton.
3. Memberikan pewarnaan titik pada backbone lintasan Hamilton dari graf split.
Untuk penulisan skripsi selanjutnya, penulis menyarankan untuk mengkaji
masalah penentuan bilangan pewarnaan l -backbone pada graf yang lain
misalnya graf kubus dengan menggunakan backbone yang lebih tinggi.
No comments:
Post a Comment