Backtracking | Set 5 (m Coloring Problem) - GeeksforGeeks
Given an undirected graph and a number m, determine if the graph can be colored with at most m colors such that no two adjacent vertices of the graph are colored with same color. Here coloring of a graph means assignment of colors to all vertices.
https://www.dailycodingproblem.com/blog/graph-coloring/
The idea is to assign colors one by one to different vertices, starting from the vertex 0. Before assigning a color, we check for safety by considering already assigned colors to the adjacent vertices. If we find a color assignment which is safe, we mark the color assignment as part of solution. If we do not a find color due to clashes then we backtrack and return false.
https://www.youtube.com/watch?v=h9wxtqoa1jY
https://www.geeksforgeeks.org/coloring-a-cycle-graph/
Given an undirected graph and a number m, determine if the graph can be colored with at most m colors such that no two adjacent vertices of the graph are colored with same color. Here coloring of a graph means assignment of colors to all vertices.
https://www.dailycodingproblem.com/blog/graph-coloring/
We can use backtracking to solve this problem. More specifically, we start at vertex 0, try out every color from 0 to
k - 1, and then see if we can recursively paint the rest of the graph without any conflicting colors. We’ll create a helper function valid(graph, colors) that looks at the last colored vertex and all its neighbours to see if it conflicts with any of its neighbours (i.e. has the same color). We can skip over all uncolored vertices here.
To represent the colors, we can just keep a separate colors list that maps 1-to-1 with the vertices. You can also convert the graph into nodes and add a color property as well.
def valid(graph, colors): last_vertex, last_color = len(colors) - 1, colors[-1] colored_neighbors = [i for i, has_edge in enumerate(graph[last_vertex]) if has_edge and i < last_vertex] for neighbor in colored_neighbors: if colors[neighbor] == last_color: return False return True def colorable(graph, k, colors=[]): if len(colors) == len(graph): return True for i in range(k): colors.append(i) if valid(graph, colors): if colorable(graph, k, colors): return True colors.pop() return False |
This runs in O(k^N) time and O(k) space, where N is the number of vertices, since we’re iterating over k colors and we are backtracking over N vertices.
Naive Algorithm
Generate all possible configurations of colors and print a configuration that satisfies the given constraints.
Generate all possible configurations of colors and print a configuration that satisfies the given constraints.
while there are untried conflagrations
{
generate the next configuration
if no adjacent vertices are colored with same color
{
print this configuration;
}
}
There will be V^m configurations of colors.
Backtracking Algorithm
bool isSafe (int v, bool graph[V][V], int color[], int c){ for (int i = 0; i < V; i++) if (graph[v][i] && c == color[i]) return false; return true;}bool graphColoringUtil(bool graph[V][V], int m, int color[], int v){ /* base case: If all vertices are assigned a color then return true */ if (v == V) return true; /* Consider this vertex v and try different colors */ for (int c = 1; c <= m; c++) { /* Check if assignment of color c to v is fine*/ if (isSafe(v, graph, color, c)) { color[v] = c; /* recur to assign colors to rest of the vertices */ if (graphColoringUtil (graph, m, color, v+1) == true) return true; /* If assigning color c doesn't lead to a solution then remove it */ color[v] = 0; } } /* If no color can be assigned to this vertex then return false */ return false;}bool graphColoring(bool graph[V][V], int m){ // Initialize all color values as 0. This initialization is needed // correct functioning of isSafe() int *color = new int[V]; for (int i = 0; i < V; i++) color[i] = 0; // Call graphColoringUtil() for vertex 0 if (graphColoringUtil(graph, m, color, 0) == false) { printf("Solution does not exist"); return false; } // Print the solution printSolution(color); return true;}https://www.youtube.com/watch?v=h9wxtqoa1jY
https://www.geeksforgeeks.org/coloring-a-cycle-graph/
Cycle:- cycle is a path of edges and vertices wherein a vertex is reachable from itself. or in other words, it is a Closed walk.
Even Cycle:- In which Even number of vertices is present is known as Even Cycle.
Odd Cycle:- In which Odd number of Vertices is present is known as Odd Cycle.
Even Cycle:- In which Even number of vertices is present is known as Even Cycle.
Odd Cycle:- In which Odd number of Vertices is present is known as Odd Cycle.
Given the number of vertices in a Cyclic Graph. The task is to determine the Number of colors required to color the graph so that No two Adjacent vertices have the same color.
Approach:
Read full article from Backtracking | Set 5 (m Coloring Problem) - GeeksforGeeksIf the no. of vertices is Even then it is Even Cycle and to color such graph we require 2 colors.
If the no. of vertices is Odd then it is Odd Cycle and to color such graph we require 3 colors.
