|
Bipartite graphs are a special type of graph where the nodes can be divided into two distinct sets, with no edges connecting nodes within the same set. Every edge connects a node from the first set to a node in the second set.
A graph where the nodes can be divided into two sets, V1 and V2, such that no edges connect nodes within the same set.
Every edge connects a node from V1 to a node in V2.
Formally: A graph G = (V, E) is bipartite if we can partition the vertex set V into two subsets V1 and V2 such that:
Every edge e ∈ E connects a vertex in V1 to a vertex in V2.
Example:
- Consider two sets of nodes: V1 = {1, 3, 5} and V2 = {2, 4, 6}.
- If the edges are {(1, 2), (3, 4), (5, 6)}, this forms a bipartite graph.
Properties of Bipartite Graphs:- Two-Colorability: Bipartite graphs can be colored using two colors such that no two adjacent nodes have the same color.
- No Odd Cycles: A graph is bipartite if and only if it contains no odd-length cycles.
- Matching and Covering: Bipartite graphs are central to the theory of matching and covering in graph theory, which has applications in resource allocation and scheduling.
Implementation of Bipartite Graphs in Python:- Class Definition: Define the
BipartiteGraph class. - Graph Initialization: Initialize the graph with two sets of vertices and an adjacency list.
- Add Edges: Method to add edges between vertices of the two sets.
- Check Bipartiteness: Method to check if a graph is bipartite.
- Display: Method to display the graph.
Let’s break this down step by step:
Step 1: Class Definition and Initialization
Python
class BipartiteGraph:
def __init__(self):
"""
Initialize the bipartite graph with two sets of vertices and an adjacency list.
"""
self.U = set() # First set of vertices
self.V = set() # Second set of vertices
self.adj_list = {} # Adjacency list to store edges
Step 2: Adding Edges
Python
def add_edge(self, u, v):
if (u in self.U and v in self.V) or (u in self.V and v in self.U):
self.adj_list[u].append(v)
self.adj_list[v].append(u)
else:
raise ValueError("Edge must connect vertices from different sets")
Step 3: Check BipartitenessTo check if a graph is bipartite, we can use a BFS-based two-coloring algorithm. If we can color the graph using two colors such that no two adjacent vertices have the same color, then the graph is bipartite.
Python
def is_bipartite(self):
color = {}
for vertex in list(self.U) + list(self.V):
if vertex not in color:
if not self._bfs_check(vertex, color):
return False
return True
def _bfs_check(self, start, color):
from collections import deque
queue = deque([start])
color[start] = 0 # Start coloring with color 0
while queue:
vertex = queue.popleft()
current_color = color[vertex]
for neighbor in self.adj_list[vertex]:
if neighbor not in color:
color[neighbor] = 1 - current_color # Alternate color
queue.append(neighbor)
elif color[neighbor] == current_color:
return False
return True
Step 4: Display the Graph
Python
def display(self):
print("Set U:", self.U)
print("Set V:", self.V)
print("Adjacency List:")
for vertex, neighbors in self.adj_list.items():
print(f"{vertex}: {neighbors}")
Complete Implementation of Bipartite Graph in Python:Putting it all together, here is the complete code for the Bipartite Graph:
Python
class BipartiteGraph:
def __init__(self):
self.U = set() # First set of vertices
self.V = set() # Second set of vertices
self.adj_list = {} # Adjacency list to store edges
def add_vertex(self, vertex, set_type):
if set_type == 'U':
self.U.add(vertex)
elif set_type == 'V':
self.V.add(vertex)
else:
raise ValueError("set_type must be either 'U' or 'V'")
# Initialize the adjacency list for the new vertex
self.adj_list[vertex] = []
def add_edge(self, u, v):
if (u in self.U and v in self.V) or (u in self.V and v in self.U):
self.adj_list[u].append(v) # Add v to the adjacency list of u
self.adj_list[v].append(u) # Add u to the adjacency list of v
else:
raise ValueError("Edge must connect vertices from different sets")
def is_bipartite(self):
color = {} # Dictionary to store the color of each vertex
for vertex in list(self.U) + list(self.V):
if vertex not in color: # If the vertex has not been colored
if not self._bfs_check(vertex, color):
return False # If BFS finds the graph is not bipartite
return True # All vertices are colored successfully in two colors
def _bfs_check(self, start, color):
from collections import deque
queue = deque([start]) # Initialize the queue with the starting vertex
color[start] = 0 # Start coloring with color 0
while queue:
vertex = queue.popleft()
current_color = color[vertex]
for neighbor in self.adj_list[vertex]:
if neighbor not in color:
color[neighbor] = 1 - current_color # Alternate color
queue.append(neighbor)
elif color[neighbor] == current_color:
return False # If the neighbor has the same color, the graph is not bipartite
return True # All vertices are successfully colored
def display(self):
print("Set U:", self.U)
print("Set V:", self.V)
print("Adjacency List:")
for vertex, neighbors in self.adj_list.items():
print(f"{vertex}: {neighbors}")
# Example usage:
graph = BipartiteGraph()
graph.add_vertex('A', 'U')
graph.add_vertex('B', 'U')
graph.add_vertex('1', 'V')
graph.add_vertex('2', 'V')
graph.add_edge('A', '1')
graph.add_edge('A', '2')
graph.add_edge('B', '1')
graph.display()
if graph.is_bipartite():
print("The graph is bipartite.")
else:
print("The graph is not bipartite.")
OutputSet U: {'A', 'B'}
Set V: {'1', '2'}
Adjacency List:
A: ['1', '2']
B: ['1']
1: ['A', 'B']
2: ['A']
The graph is bipartite.
Time Complexity: O(V + E) for the is_bipartite() and display() methods.
Auxiliary Space: O(V) for the is_bipartite() method, where V is the number of vertices.
|
Kahn's Algorithm in Python