Determine Whether A Given Undirected Graph is Two-Colorable in Python
What does Two-Colorable mean for a graph?
A two-colorable graph is a graph in which each vertex can be assigned a color (out of any two given colors, here we will assume these colors to be BLACK and WHITE) and none of its adjacent vertices have the same color.
The problem that we are going to solve is to check whether a given undirected graph is two-colorable or not.
Examples:
The simplest example of a two-colorable graph is a graph with 2 vertices and a single edge. One of the edges would be colored white and the other would be black.
An example of a graph that is NOT two-colorable is a 3 vertex cycle. In fact, any graph which contains an odd cycle is NOT two-colorable.
How to check a two-colorable graph?
For two coloring a graph, the main point to focus upon is that once we pick a color for a particular vertex, all its adjacent vertices must have the opposite color. So deciding on a color for a particular vertex means that the colors of all its adjacent vertices can’t be decided by us. Also, the choice of color for the first vertex (whether it is white or black) does not matter, as swapping from one to the other will simply change the color of all other vertices.
With this logic in our mind, we can now take the greedy approach. We perform a depth-first search on the graph and check each vertex: if it hasn’t been colored yet, then we choose a color for that vertex and color its adjacent vertices with the opposite color. At any point, if a vertex has any of its adjacent vertices with the same color, then we can recognize the graph being NOT two-colorable.
Pseudocode for the solution
- function TWO_COLOUR(G = (V, E))
- Set colour[1..n] = null
- for each vertex u = 1 to n do
- if colour[u] = null then
- if DFS(u, BLACK) = False then
- return False
- return True
- end function
- // Returns true if the component was successfully coloured
- function DFS(u, c)
- colour[u] = c
- for each vertex v adjacent to u do
- if colour[v] = c then // A neighbour has the same colour as us!
- return False
- else if colour[v] = null and DFS(v, opposite(c)) = False then
- return False
- return True
- end function
NOTE: Here, opposite(c) is a function that returns WHITE or BLACK if c is BLACK or WHITE respectively
Complexity Analysis
k-colorable graph problems all belong to a certain class of problems called NP-complete except when k=0,1,2. This simply means that k-colorable graph problems (other than when k =0,1,2) can not be solved in a polynomial time complexity( i.e. O(n^k)).
Thus, checking for a two-colorable graph is the maximum number of colors (i.e. ‘k’ = 2) for which a polynomial-time algorithm can be given to solve the k-colorable graph problem. In fact, it can be solved with an algorithm of linear time complexity., i.e., O(n) where n is the size of the input graph.
In our solution, the time complexity for the solution is O(V+E) where V = number of vertices and E = number of edges in the graph.
Implementing the Python code
Below is the Python code to determine whether a given undirected graph is two-colorable or not:
def two_colour(adj_list): """ Input: a graph in the form of an adjacency list Output: True if the given graph is 2 colorable, False if it is not Complxity: O(V+E), where V= number of vertices and E= number of edges of the input graph """ n = len(adj_list) # number of vertices colour_list = [0]*n # 0 represents no colour for u in range(n): # iterating through all the vertices if colour_list[u] == 0: if DFS(u, 'BLACK', colour_list, adj_list) == False: return False return True # function for checking whether a vertex # was successsfully coloured def DFS(u, c, colour_list, adj_list): colour_list[u] = c for v in adj_list[u]: if colour_list[v] == c: return False elif colour_list[v] == 0 and DFS(v, opposite(c), colour_list, adj_list) == False: return False return True # returns the opposite colour def opposite(c): if c =='BLACK': return 'WHITE' elif c =='WHITE': return 'BLACK'
Example 1:
This is a 3 vertex cycle graph
two_colour([[1,2],[0,2],[0,1]])
Output:
False
Example 2:
This is a simple graph with 4 vertices connected in the following manner:
0–1–2–3
Where 0,1,2,3 represent vertices and — represents an undirected edge.
two_colour([[1],[0,2],[1,3],[2]])
Output:
True
Thank you for sparing your valuable time to read this article. You can check out other articles as well:
Leave a Reply