M-Color Problem - Graph Theory

In the late centuries, mathematics has been essential in many scientific fields. In this article, we see one of the famous mathematical problems: Graph Coloring.

Introduction

Graph theory is a branch of Mathematics. It studies the relationship between objects, given a set of nodes (vertices) connected by edges; this network is called a graph.

This theory is used in many fields, like Physics, Biologie, information, and social systems.

Problem Statement

The famous problem states that in an undirected graph (no oriented edges) with a number 'n' of nodes, and using at most 'm' of colors, is it possible to color the set of nodes considering that each pair of adjacent nodes cannot have the same color?

Problem Break Down

We can approach this situation using two methods :

Naive Approach

The idea is to test out all of the possible configurations of colors in respect of the indicated constraint. After every generated configuration, we check out the eligibility of the suggested solution.

The number of possible color configurations is m^v (m: number of colors, v: number of vertices); if one configuration meets the conditions, we print it out and break the loop.

Backtracking Approach

The idea is to assign colors one by one to each node, starting from a node that we call vertex 0. There are two conditions to consider in this method:

1. Before the color assignment, we need a check for safety considering already assigned colors to adjacent vertices. If there is no violation, we mark the color assignment as part of the solution; otherwise, we cancel it.
2. If no color assignment is possible, then the solution is considered complete.

Algorithm

M-Color Graph Algorithm

Implementation

Source : https://www.geeksforgeeks.org/m-coloring-problem-backtracking-5/

 

Fields Of Use

We can use Graph Coloring in many fields and situations, such as:

sudoku

This game is an interesting example and a variation of the Graph Coloring problem. We can solve it by considering every cell as a vertex (node). Every two cells are linked if they are in the same row, same column, same block. 

Scheduling

Scheduling is a vast space where we can use Graph Coloring to model scheduling like creating timetables, assigning jobs or tasks, Aircraft Scheduling. 

register allocation

Register Allocation is the technique of compiler optimization, and it is the improvement of the execution time of the resulting code.

GSM Mobile Phone Networks (Groups Special Mobile)

This type of network works using geographical partitioning according to the distribution of communication towers. These towers are used to connect cell phones. To help create quality and fast communication channels, we can use Graph Coloring solutions.

Conclusion

There are many applications to mathematical problems that help handle complicated situations. Graph Coloring solutions provide a crystal clear example for such applications.