04
Bipartite Graph Check Demos
Chapter 4 • Intermediate
75 min
Bipartite Graph Check Demos
What is a Bipartite Graph?
A graph is bipartite if its vertices can be divided into two disjoint sets such that:
- Every edge connects a vertex from one set to a vertex in the other set
- No edge connects vertices within the same set
Key Properties
- No odd-length cycles: Bipartite graphs contain no cycles of odd length
- 2-colorable: Can be colored with 2 colors such that no adjacent vertices have same color
- All trees are bipartite
Applications
- Matching problems: Job assignment, stable marriage
- Network flow: Modeling flow problems
- Scheduling: Resource allocation
- Social networks: Modeling relationships
Algorithm: BFS-based Coloring
Approach
- Color vertices using BFS
- Assign alternating colors to adjacent vertices
- If conflict found (adjacent vertices have same color), graph is not bipartite
Implementation
python.js
from collections import deque
def is_bipartite_bfs(graph):
"""
Check if graph is bipartite using BFS.
Time: O(V + E), Space: O(V)
"""
n = len(graph)
color = [-1] * n # -1: uncolored, 0: color1, 1: color2
for i in range(n):
if color[i] == -1: # Unvisited component
queue = deque([i])
color[i] = 0
while queue:
u = queue.popleft()
for v in graph[u]:
if color[v] == -1:
# Color with opposite color
color[v] = 1 - color[u]
queue.append(v)
elif color[v] == color[u]:
# Same color adjacent vertices
return False
return True
Algorithm: DFS-based Coloring
python.js
def is_bipartite_dfs(graph):
"""
Check if graph is bipartite using DFS.
Time: O(V + E), Space: O(V)
"""
n = len(graph)
color = [-1] * n
def dfs(u, c):
color[u] = c
for v in graph[u]:
if color[v] == -1:
if not dfs(v, 1 - c):
return False
elif color[v] == c:
return False
return True
for i in range(n):
if color[i] == -1:
if not dfs(i, 0):
return False
return True
Finding Bipartite Sets
python.js
def get_bipartite_sets(graph):
"""
Get the two sets if graph is bipartite.
Returns (set1, set2) or None if not bipartite
"""
n = len(graph)
color = [-1] * n
def dfs(u, c):
color[u] = c
for v in graph[u]:
if color[v] == -1:
if not dfs(v, 1 - c):
return False
elif color[v] == c:
return False
return True
for i in range(n):
if color[i] == -1:
if not dfs(i, 0):
return None
set1 = [i for i in range(n) if color[i] == 0]
set2 = [i for i in range(n) if color[i] == 1]
return (set1, set2)
Why Odd Cycles Prevent Bipartiteness
In a cycle of odd length (3, 5, 7, ...):
- Start with color 0
- After odd number of edges, end with color 1
- But start and end are adjacent, requiring same color
- Contradiction!
Example
python.js
# Bipartite graph (even cycle)
graph1 = [
[1, 3], # 0 connects to 1, 3
[0, 2], # 1 connects to 0, 2
[1, 3], # 2 connects to 1, 3
[0, 2] # 3 connects to 0, 2
]
# Sets: {0, 2} and {1, 3}
print(is_bipartite_bfs(graph1)) # True
# Non-bipartite graph (odd cycle - triangle)
graph2 = [
[1, 2], # 0 connects to 1, 2
[0, 2], # 1 connects to 0, 2
[0, 1] # 2 connects to 0, 1
]
print(is_bipartite_bfs(graph2)) # False
Complete Bipartite Graph
A complete bipartite graph K_{m,n} has:
- Two sets of sizes m and n
- Every vertex in first set connected to every vertex in second set
- Total edges: m × n
Practice Problems
- Check if graph is bipartite
- Find bipartite sets if graph is bipartite
- Count number of bipartite components
- Check if tree is bipartite (all trees are!)
- Maximum bipartite matching
- Convert graph to bipartite by removing minimum edges