graph coloring back tracking and applications in realA time.pptx

This PPt Describes importance of graph coloring. Real time applications of graph coloring. How it is implemented using ack tracking strategy. Time complexity of algorithm. State space tree for the implementation of graph coloring.Not only one solution ,More than one feasible solutions are evaluated. This problem comes under the category of Decision making category, due to consideration of include or exclude weights in each and every stage of problem solving till we get required sum.

1. Graph Coloring Using Backtracking

2. Graph Coloring is a process of assigning colors to the vertices of a graph. It ensures that no two adjacent vertices of the graph are colored with the same color. Chromatic Number is the minimum number of colors required to properly color any graph.

3. The Chromatic Number: The chromatic number of a graph is the smallest number of colors needed to properly color its vertices. Finding the chromatic number for a given graph is a challenging problem, and it falls into the NP-complete category.

4. Graph Coloring Algorithm:   There exists no efficient algorithm for coloring a graph with minimum number of colors. Graph Coloring is a NP complete problem.

5. Backtracking Algorithm for Graph Coloring Here’s how the backtracking algorithm works for graph coloring: Start with an empty coloring for the graph. Choose an uncolored vertex. Try assigning a color to that vertex.

6. 4. Check if the assignment is valid (i.e., no adjacent vertices have the same color). 5. If valid, move on to the next uncolored vertex. 6. If not valid, backtrack and try a different color for the previous vertex. 7. Repeat steps 3-6 until all vertices are colored or until no valid color assignment is possible.

7. Graph coloring has practical applications : Scheduling : Assigning time slots to tasks without conflicts. Sudoku : Solving Sudoku puzzles involves graph coloring. Map Coloring : Ensuring that adjacent regions on a map have different colors.

8. Map coloring :

9. StudentA- C 1, C 3 StudentB- C 1, C 4, C 5 StudentC- C 2, C 6S StudentD- C 2, C 3, C 6 StudentE- C 3, C 4 StudentF- C 3, C 5 StudentG- C 5, C 6 Scheduling courses

10. Example of graph coloring

11. Algorithm: Algorithm mColoring (k) { // g(1:n, 1:n) boolean adjacency matrix. // k index (node) of the next vertex to color . Repeat { nextvalue (k); // assign to x[k] a legal color . if(x[k]==0) then return; // no new color possible if(k=n) then print(x[1: n]); else mcoloring (k+1); } until(false)

12. Algorithm NextValue (k) { //x[1],x[2],---x[k-1] have been assigned integer values //in the range [1, m] repeat { x[k]=(x[k]+1)mod (m+1); //next highest color if(x[k]=0) then return; // all colors have been used. for j=1 to n do { if ((g[ k,j ]≠0) and (x[k]=x[j]))then //To check whether //the same color used break; } if(j=n+1) then return; //new color found } until(false)

13. Complexity Analysis : In this method each vertex has  M  different choices of colors. So the total  time complexity  is M V  , where  M  is the number of colours and  V  is the number of vertices.