Genetic Algorithms for Graph Theoretic Problems

The graph vertex colouring problem calls for colouring the vertices with k colours on graph G, which has n vertices and m edges. There are kn distinct colour combinations when there are n vertices and k colours. If two neighbouring vertices in a given k-colouring do not share the same colour, the colouring is said to be perfect. The chromatic number of the graph is the minor integer k, for which G has a perfect k-colouring. It is an NP-complete problem to determine the chromatic number. The construction of solutions using Genetic Algorithms is quite comparable to the development of biological things in genetics. Father and Mother, two potential solution states, are united to create offspring, which is a better solution state than Father and Mother. The vertex colouring problem was examined in this research, and the functions perfect colouring coefficient of vertex (PCCV) and perfect colouring coefficient of the graph (PCCG) were introduced. The functions PCCV(v) and PCCG(C) are used as Fitness Functions in searching for solutions using the approach of Genetic Algorithms. We have defined a few mutation functions and crossover functions. The mutations and crossover defined in this chapter are proven to improve the fitness function value in every generation. We prove that the Genetic Algorithm presented in this chapter moves in the right direction toward an optimal solution.