Open AccessImplementation of the greedy algorithm on graph coloring
Author(s) -
Tetty Natalia Sipayung,
Saib Suwilo,
P Gultom,
Mardiningsih
Publication year - 2022
Publication title -
journal of physics. conference series
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.21
H-Index - 85
eISSN - 1742-6596
pISSN - 1742-6588
DOI - 10.1088/1742-6596/2157/1/012003
Subject(s) - greedy coloring , fractional coloring , graph coloring , colored , greedy algorithm , list coloring , graph , computer science , edge coloring , algorithm , python (programming language) , graph power , mathematics , combinatorics , line graph , materials science , composite material , operating system
Graph theory is part of the field of mathematics that can be applied in various other fields of science to solve problems. One of them is the problem of determining the color on the map. The map that will be colored here is a map of the Deli Serdang regency which consists of 22 sub-districts. The coloring of the map is done by first modeling it in the form of a graph. One way to determine the minimum color of a graph is to use a greedy algorithm. From the map, we get a dual graph with 22 vertices and 41 edges. Based on the greedy algorithm that has been applied, the minimum number of colors is obtained as many as four colors, namely blue, green, red, and yellow with each district directly bordering having a different color. The results of map coloring by applying the greedy algorithm are also obtained with the help of the python 3.7 programming language.