Sifat-sifat Pewarnaan Graf dan Pewarnaan Peta Provinsi Jawa Barat
Date
2022Author
Ramadi, Dandy
Siswandi, Siswandi
Mas'oed, Teduh Wulandari
Metadata
Show full item recordAbstract
Pewarnaan simpul pada graf adalah mewarnai simpul pada suatu graf dimana simpul yang saling adjacent diwarnai dengan warna yang berbeda. Pewarnaan simpul pada graf dapat diaplikasikan pada proses pewarnaan peta. Pada karya ilmiah ini dibahas sifat-sifat pewarnaan graf berdasarkan beberapa teorema yang salah satunya dikenal sebagai teorema Brooks. Untuk suatu ilustrasi, teorema Brooks juga diterapkan pada proses pewarnaan peta provinsi Jawa Barat berdasarkan algoritma Greedy. Dari kajian ini menunjukan bahwa graf hasil konversi peta provinsi Jawa Barat merupakan graf terhubung yang tak lengkap dan memiliki derajat simpul maksimal bernilai 7 (tujuh). Selanjutnya, peta provinsi Jawa Barat dapat diwarnai dengan empat warna, sesuai dengan teorema brooks bahwa wilayah yang bertetangga pada peta diwarnai dengan warna yang berbeda. The coloring of the vertices of a graph is coloring the vertices of the graph where adjacent vertices are colored using different colors. The coloring of vertices of a graph can be applied to the map coloring process. In this manuscript, properties of graph coloring are discussed based on theorems which one of those called as Brooks theorem. For an illustration, Brooks theorem is also applied to the map coloring of West Java province using the Greedy algorithm. This study shows that the resulting graph from the map conversion of West Java province is an incomplete connected graph and has a maximum vertex degree of 7 (seven). Furthermore, The map of West Java province can be colored with four colors, comply to Brooks theorem where neighboring regions on the map are colored in different colors.
Collections
- UT - Mathematics [1365]