Check if Graph is Bipartite 🎯

Welcome to today's lesson where we're going to explore one of the fundamental concepts in Graph Theory - Bipartite Graphs! By the end of this lesson, you'll be able to identify and verify whether a given graph is bipartite or not. Let's dive in!

What is a Bipartite Graph? 📝

Before we jump into the algorithm, let's first understand what a Bipartite Graph is. A graph is said to be bipartite if its vertices can be divided into two disjoint sets V1 and V2 such that each edge connects a vertex from V1 to a vertex from V2.

Here's a simple example of a bipartite graph:

  A --- B
 /     | \
C --- D

In this example, vertices A, B, C, and D are divided into two disjoint sets: V1 = {A, C} and V2 = {B, D}.

Why is it Important? 💡

Bipartite graphs have several practical applications, such as in network design, data modeling, and computer graphics. Understanding and identifying bipartite graphs can help optimize the performance of these applications.

Checking for Bipartiteness 📝

Now that we understand what a bipartite graph is, let's discuss the algorithm to check if a graph is bipartite or not. We'll use Depth-First Search (DFS) for this purpose.

Depth-First Search (DFS) 💡

DFS is a popular graph traversal algorithm used to explore and reach all vertices in a graph. It's a recursive algorithm that helps us in checking the bipartiteness of a graph.

Algorithm for Bipartite Check 📝

Assign a color (either 'Red' or 'Blue') to each vertex initially.
Iterate through each vertex in the graph. For each vertex v, perform DFS.
During DFS, mark the visited vertex and check its neighbors. If a neighbor is already visited and has a different color, return False (graph is not bipartite).
If no such situation arises during the DFS, the graph is bipartite.

DFS with Color Assignment 💡

Here's a complete DFS implementation with color assignment for checking bipartiteness:

python

def is_bipartite(graph):
    visited, color = set(), {'R': 1, 'B': -1}

    def dfs(node, color_val):
        if node in visited:
            return False
        visited.add(node)
        for neighbor in graph[node]:
            if (color[neighbor] == color_val) or (dfs(neighbor, -color_val) == False):
                return False
        visited.remove(node)
        return True

    for node in graph:
        if dfs(node, color['R']) is False:
            return False
    return True

Practical Example 🎯

Let's test our function on a graph:

python

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'D'],
    'D': ['B', 'C']
}

print(is_bipartite(graph))  # True

Quiz 📝

Question: What is the time complexity of the above bipartite checking algorithm? A: O(V + E) B: O(V^2) C: O(E^2) Correct: A Explanation: The time complexity of the algorithm is O(V + E) due to the DFS traversal and coloring process.

That's it for today's lesson! With this new knowledge, you can now check if a graph is bipartite or not. Happy coding! 🚀