Graph coloring using backtracking

presentation of Graph coloring Technique using backtracking

1. GRAPH COLORING USING BACKTRACKING BY: P. Shashidhar 18E11A05B7

2. What is graph coloring?

3. T he objective is to minimize the number of colors while coloring a graph.  The smallest number of colors required to color a graph G is called its chromatic number of that graph. Graph coloring problem is a NP Complete problem . No efficient algorithm is available to implement graph coloring mainly we use Greedy and Backtracking algorithm.

4. Method to Color a Graph Arrange the vertices of graph in the same order. Choose the first vertex and color it with the first color. Then choose next vertex and color it with the lowest numbered color that has not been colored on any vertices which is adjacent to it. If all the adjacent vertices are colored with the color, assign the new color to it. Repeat the same process until all the vertices are colored. If any complication occurs backtrack before step and repeat the process.

5. Algorithm:  Create a recursive function that takes current index, number of vertices and output color array. If the current index is equal to number of vertices. Check if the output color configuration is safe, i.e check if the adjacent vertices do not have same color. If the conditions are met, print the configuration and break. Assign a color to a vertex (1 to m). For every assigned color recursively call the function with next index and number of vertices If any recursive function returns true break the loop and returns true.

6. GraphColor (int k){ for(int c=1;c<= m;c ++); if( isSafe ( k,c )){ X[k]=c; if((k+1)<n) GraphColor (k+1); else print x[];return; } } isSafe (int k,int c){ for(int i =0;i< n;i ++){ if(G[k][ i ]=2 && c==x[ i ]){ return false; } } return true; }

7. Applications: Making schedule or Time table. Sudoku. Register allocation. Map coloring. Job allocation in CPU.

8. THANK YOU