Sifat Pewarnaan Simpul Graf dan Aplikasinya pada Peta Curah Hujan di Kecamatan Bandung Barat Menggunakan Algoritma Greedy

Abstract

Tulisan ini membahas beberapa sifat pada pewarnaan simpul (vertex) graf yang berkaitan dengan penentuan bilangan kromatik dan implementasinya untuk memantau distribusi curah hujan pada beberapa daerah kecamatan Bandung Barat menggunakan algoritma Greedy. Hasil penelitian ini menunjukkan bahwa graf hasil representasi peta kecamatan Bandung Barat memiliki bilangan kromatik sebesar ??(??) = 4 karena grafnya bisa diwarnai dengan 4 warna sehingga ? (??) = 4, dengan derajat maksimum graf adalah ? (??) = 8, Sehingga diperoleh 4 = 8. Hasil tersebut menunjukkan bahwa algoritma Greedy mampu menghasilkan pewarnaan graf yang sesuai.

This paper discusses several properties of graph vertex coloring related to the determination of the chromatic number and its implementation for monitoring rainfall distribution in several subdistricts of West Bandung using the Greedy algorithm. The results of this study show that the graph representing the map of subdistricts in West Bandung has a chromatic number of ??(??) = 4 because the graph can be colored with 4 colors, resulting in ??(??) = 4, with the maximum degree of the graph being ??(??) = 8. Thus, 4 = 8 is obtained. These results indicate that the Greedy algorithm is capable of producing an appropriate graph coloring.