PENGEMBANGAN METODE PEWARNAAN TITIK DAN BILANGAN KROMATIK PADA GRAF-GRAF TAK DETERMINISTIK

ISNAINI ROSYIDA, Prof. Dr. rer.nat. Widodo, MS, Prof. Dr. Ch. Rini Indrati, M.Si, Dr. Kiki Ariyanti Sugeng, M.Si

2016 | Disertasi | S3 Matematika

Permasalahan pewarnaan titik merupakan masalah pemasangan warna ke titik-titik sebuah graf sehingga dua buah titik yang bertetangga dipasangkan dengan warna yang berbeda. Bilangan yang menyatakan banyaknya warna minimal yang digunakan dalam pewarnaan titik graf disebut bilangan kromatik. Pewarnaan graf yang sudah dikaji para peneliti kebanyakan masih menggunakan graf tegas, dalam hal ini hubungan dua buah titik dinyatakan secara tegas sebagai bertetangga atau tidak. Pada kenyataannya hubungan antar obyek dalam sebuah jaringan tidak selalu dapat dinyatakan secara tegas, sehingga diperlukan konsep graf tak deterministik (non deterministic graph) dan pewarnaan graf tak deterministik untuk mengatasi fenomena-fenomena ketidakpastian dalam sebuah jaringan. Penelitian ini difokuskan pada graf fuzzy dan graf tak pasti (uncertain graph). Motivasi penelitian yang dituliskan dalam disertasi ini berawal dari beberapa hasil penelitian pendahulu tentang pewarnaan graf fuzzy maupun graf tak pasti. Perkembangan penelitian tentang pewarnaan titik pada graf tak deterministik dapat diklasifikasikan dalam dua pendekatan, yaitu tanpa proses transformasi ke pewarnaan klasik dan melalui proses transformasi ke pewarnaan klasik. Metode yang biasa digunakan untuk menyelesaikan suatu permasalahan pada jaringan tak deterministik adalah dengan mentransformasi ke permasalahan klasik yang terkait. Oleh karena itu, penelitian ini difokuskan pada pewarnaan titik graf tak deterministik dengan proses transformasi ke pewarnaan klasik. Pada penelitian ini diteliti dua tipe graf fuzzy, yaitu graf fuzzy dengan himpunan titik tegas dan himpunan sisi fuzzy (tipe I) dan graf fuzzy dengan himpunan titik fuzzy dan himpunan sisi fuzzy (tipe II). Terdapat beberapa penelitian pendahulu tentang metode pewarnaan titik pada graf fuzzy tipe I, di antaranya pewarnaan graf fuzzy tipe I melalui himpunan titik independen fuzzy maksimal dari Bershtein dan Bozhenuk (2001), pewarnaan titik graf fuzzy tipe I melalui potongan-alfa oleh Munoz dkk. (2005) dan pewarnaan titik graf fuzzy tipe I melalui himpunan titik independen fuzzy yang bergantung pada delta elemen [0,1] oleh Cioban (2007). Ditemukan beberapa fakta pada penelitian pendahulu tersebut, di antaranya metode pewarnaan dari Bershtein dan Bozhenuk tanpa melalui transformasi ke pewarnaan klasik, bilangan kromatik fuzzy yang dikonstruksi oleh Munoz dkk. bukan merupakan perumuman dari bilangan kromatik graf tegas, dan bilangan kromatik yang diperoleh dari metode Cioban masih berupa bilangan tegas. Termotivasi dari hasil pendahulu, pada penelitian ini dilakukan pengembangan metode untuk mengkonstruksi bilangan kromatik fuzzy pada graf fuzzy tipe I melalui himpunan titik independen fuzzy-delta. Penelitian pendahulu tentang metode pewarnaan titik pada graf fuzzy tipe II telah dikenalkan oleh Eslahchi dan Onagh (2005) serta Nair (2008). Kedua metode tersebut masih menghasilkan bilangan kromatik tegas dan tidak melalui transformasi ke pewarnaan klasik. Oleh karena itu, pada penelitian ini dilakukan pengembangan metode pewarnaan titik dan konstruksi bilangan kromatik fuzzy pada graf fuzzy tipe II melalui himpunan titik independen fuzzy-delta. Permasalahan pewarnaan titik pada graf tak pasti belum banyak dikaji. Sejauh penelusuran yang dilakukan, baru dikenalkan satu metode yaitu pewarnaan titik pada graf tak pasti melalui himpunan titik independen tak pasti oleh Chen dan Peng (2014). Metode ini tidak menggunakan proses transformasi ke pewarnaan klasik. Oleh karena itu, penelitian ini difokuskan pada pengembangan metode pewarnaan titik dan konstruksi himpunan kromatik pada graf tak pasti melalui potongan-alfa. Sejauh kajian yang telah penulis lakukan, belum pernah ada penelitian sebelumnya yang membahas tentang permasalahan-permasalahan di atas. Hasil pada bagian pertama berupa metode untuk menentukan bilangan kromatik fuzzy pada graf fuzzy tipe I melalui himpunan titik independen fuzzy-delta. Tahap-tahap yang dilakukan meliputi: konstruksi konsep himpunan kromatik fuzzy pada graf fuzzy tipe I, pembuktian bahwa himpunan kromatik fuzzy tersebut ekuivalen dengan himpunan kromatik fuzzy dari Bershtein dan Bozhenuk (2001), serta pembuktian bahwa himpunan kromatik fuzzy dalam disertasi ini merupakan bilangan fuzzy sehingga selanjutnya disebut bilangan kromatik fuzzy. Tahap akhir adalah konstruksi algoritma untuk menentukan bilangan kromatik fuzzy pada graf fuzzy tipe I. Hasil pada bagian kedua meliputi metode pewarnaan melalui himpunan titik independen fuzzy-delta dan konstruksi bilangan kromatik pada graf fuzzy tipe II. Tahap-tahap yang dikerjakan meliputi konstruksi konsep himpunan titik independen fuzzy-delta pada graf fuzzy tipe II, pengembangan konsep pewarnaan melalui himpunan titik independen fuzzy-delta pada graf fuzzy tipe II, konstruksi bilangan kromatik fuzzy pada graf fuzzy tipe II melalui himpunan titik independen fuzzy-delta beserta sifat-sifatnya, serta pengembangan algoritma untuk menentukan bilangan kromatik fuzzy pada graf fuzzy tipe II. Hasil pada bagian ketiga berupa metode pewarnaan titik graf tak pasti melalui pewarnaan pada potongan-alfa. Tahap-tahap yang dikerjakan meliputi: konstruksi konsep potongan-alfa dari graf tak pasti sisi dan graf tak pasti total serta sifat-sifat nya, penyelidikan sifat-sifat bilangan kromatik potongan-alfa dari graf tak pasti sisi dan graf tak pasti total, serta konstruksi himpunan kromatik tak pasti (uncertain chromatic set) pada graf tak pasti.

A vertex coloring problem is a problem of assigning a color to each vertex of a graph such that the colors of adjacent vertices are different and the number of colors used is minimized. The minimum number of colors used in the graph coloring is called chromatic number. The graph coloring problem has been studied by many researchers. However, they still focused on crisp graph, where adjacency between two vertices are known exactly. However, the system in real-life situations may be so complex such that adjacency between two vertices cannot be known exactly. Therefore, we need the concepts of nondeterministic graph and nondeterministic graph coloring to deal with these indeterminate phenomena. This research focus on nondeterministic graph based on fuzzy theory (fuzzy graph) and nondeterministic graph based on uncertainty theory (uncertain graph). %%coloring and uncertain graph coloring. There are two approaches in the method of vertex coloring on nondeterministic graphs. The first approach is transforming into corresponding classical coloring and the second approach is not transforming into classical coloring. Meanwhile, the method which is usually used to solve a problem on nondeterministic network is by simplifying it into corresponding classical problem. Hence, we focus on developing a method for vertex coloring on nondeterministic graphs by transforming into classical coloring. In this research, we investigate two types of fuzzy graphs that are fuzzy graph with crisp vertex set and fuzzy edge set (type I) and fuzzy graph with fuzzy vertex set and fuzzy edge set (type II). In the field of fuzzy graphs, there are several methods to color the type I fuzzy graph. The first method is coloring type I fuzzy graph through maximal fuzzy independent vertex set by Bershtein and Bozhenuk (2001). The next method is coloring type I fuzzy graph through alfa-cut which was introduced by Munoz et al. (2005). After that, Munoz et al. defined fuzzy chromatic number of fuzzy graph through alfa-cut coloring. The last method is coloring type I fuzzy graph through delta-fuzzy independent vertex sets (delta element [0,1]) which was introduced by Cioban (2007) and the chromatic number is called delta-chromatic number. We found that there are infirmities on the previous results. The first method did not transform the fuzzy graph coloring into the classical coloring. Next, The fuzzy chromatic number from Munoz et al. is not consistent with the chromatic number of crisp graph. Meanwhile the delta-chromatic number related to Cioban's method is still crisp graph. Therefore, we develop a method to construct fuzzy chromatic number of fuzzy graph based on delta-fuzzy independent vertex set. Further, there are two methods for coloring type II fuzzy graph. Firstly, Eslahchi and Onagh introduced a method to color type II fuzzy graph based on strong (weak) adjacency. Secondly, Nair (2008) introduced a method to color type II fuzzy graph based on precise independent vertex sets. Both of the two methods did not tranform the fuzzy graph coloring into the classical coloring and the related chromatic number was still crisp number. Based on these facts, we need to develop a method to color type II fuzzy graph and to construct fuzzy chromatic number of type II fuzzy graph based on delta-fuzzy independent vertex set. To the best of our knowledge, no one has investigated these problems before. Moreover, the research on vertex coloring of uncertain graph has not been studied intensively. There is only one method to color uncertain graph which was introduced by Chen and Peng (2014). They introduced a method to color uncertain graph through maximal uncertain independent vertex. However, this method did not transform the uncertain graph coloring into the classical coloring. Therefore, we develop a method to color uncertain graph and to construct uncertain chromatic set of uncertain graph through the alfa-cut. No one has investigated a method to color uncertain graph through its alfa-cut before. The first step, we construct a concept of fuzzy chromatic set of type I fuzzy graph through delta-fuzzy independent vertex set. After that, we prove that the fuzzy chromatic set is equivalent to fuzzy chromatic set which was introduced by Bershtein-Bozhenuk (2001). We also prove that the fuzzy chromatic set is a discrete fuzzy number and hence it is called fuzzy chromatic number. Finally, we construct an algorithm to determine fuzzy chromatic number of type I fuzzy graph. The second step, we develop the concept of delta-fuzzy independent vertex set for type II fuzzy graph. Further, we construct a concept of coloring type II fuzzy graph and delta-chromatic number of type II fuzzy graph based on delta-fuzzy independent vertex set. Furthermore, a fuzzy chromatic number of type II fuzzy graph is constructed via its delta-chromatic number. Finally, we develop an algorithm to determine fuzzy chromatic number of type II fuzzy graph. The third step, we develop a method to color an uncertain graph via its alfa-cut. The stages used as follows: constructing the concept of alfa-cut of edge uncertain graph and alfa-cut of total uncertain graph, investigating the properties of the alfa-cut, investigating the properties of alfa-cut chromatic number of edge uncertain graph and total uncertain graph. Finally, we construct uncertain chromatic set of uncertain graph based on alfa-cut chromatic number.

Kata Kunci : Pewarnaan titik, graf fuzzy, graf tak pasti (uncertain graph), himpunan titik independen fuzzy-delta, bilangan kromatik fuzzy, potongan-alfa, himpunan kromatik tak pasti (uncertain chromatic set)