二分图是一种图,其顶点可以分为两个独立的集合 U 和 V,使得每条边 (u, v) 要么连接从 U 到 V 的顶点,要么连接从 V 到 U 的顶点。换句话说,对于每个边 (u, v),要么 u 属于 U,v 属于 V,要么 u 属于 V,v 属于 U。我们也可以说,不存在连接同一集合的顶点的边。
如果图着色可以使用两种颜色使得集合中的顶点使用相同颜色着色,则二分图是可能的。
请注意,可以使用两种颜色对具有偶数循环的循环图进行着色。例如,请参见下图。
不可能使用两种颜色对具有奇数循环的循环图进行着色。
检查图是否为二分图的算法:
一种方法是使用 回溯算法 m 着色问题来检查图是否为 2-colorable 。
以下是一个使用广度优先搜索 (BFS) 来确定给定图是否为二分图的简单算法。
# Python 程序查找 给定图形是否为二方图
class Graph():
def __init__(self, V):
self.V = V
self.graph = [[0 for column in range(V)] \
for row in range(V)]
# 如果图 G[V][V] 返回 true,则此函数返回 true。
# 是二方图,否则返回 false
def isBipartite(self, src):
colorArr = [-1] * self.V
# 将第一种颜色指定给源
colorArr[src] = 1
# 创建一个顶点编号的队列(先进先出),
# 将源顶点入队以进行BFS遍历。
queue = []
queue.append(src)
# 在队列中有顶点时运行 (类似于 BFS)
while queue:
u = queue.pop()
# 如果存在自循环,则返回 false
if self.graph[u][u] == 1:
return False;
for v in range(self.V):
# An edge from u to v exists and destination
# v is not colored
if self.graph[u][v] == 1 and colorArr[v] == -1:
# Assign alternate color to this
# adjacent v of u
colorArr[v] = 1 - colorArr[u]
queue.append(v)
# An edge from u to v exists and destination
# v is colored with same color as u
elif self.graph[u][v] == 1 and colorArr[v] == colorArr[u]:
return False
# If we reach here, then all adjacent
# vertices can be colored with alternate
# color
return True
# Driver program to test above function
g = Graph(4)
g.graph = [[0, 1, 0, 1],
[1, 0, 1, 0],
[0, 1, 0, 1],
[1, 0, 1, 0]
]
print ("Yes" if g.isBipartite(0) else "No")
是的
时间复杂度:O(V*V) 作为邻接矩阵用于图,但可以通过使用邻接列表将其变为 O(V+E) 辅助空间:由于队列和颜色向量,O(V)。
上述算法仅在 图是连通的情况下才有效。在上面的代码中,我们总是从源 0 开始,并假设从源 0 访问顶点。一个重要的观察是,没有边的图也是二分图。请注意,二分条件表示所有边都应从一组到另一组。
我们可以扩展上面的代码来处理图未连接的情况。对于所有尚未访问的顶点,重复调用上述方法。
# Python3 程序来找出 给定图形是否为二方图
class Graph():
def __init__(self, V):
self.V = V
self.graph = [[0 for column in range(V)]
for row in range(V)]
self.colorArr = [-1 for i in range(self.V)]
# 如果图 G[V][V] 返回 true,则此函数返回 true。 是二方图,否则返回 false
def isBipartiteUtil(self, src):
# 创建顶点编号队列(先进先出)并
# 为 BFS 遍历登记源顶点
queue = []
queue.append(src)
# 在队列中有顶点时运行 (类似于 BFS)
while queue:
u = queue.pop()
# 如果存在自循环,则返回 false
if self.graph[u][u] == 1:
return False
for v in range(self.V):
# 存在一条从 u 到 v 的边,并且目的地 v 没有着色
if (self.graph[u][v] == 1 and
self.colorArr[v] == -1):
# 为 u 的相邻 v
self.colorArr[v] = 1 - self.colorArr[u]
queue.append(v)
# 存在一条从 u 到 v 的边,且目的地 v 的颜色与 u 相同
elif (self.graph[u][v] == 1 and
self.colorArr[v] == self.colorArr[u]):
return False
return True
def isBipartite(self):
self.colorArr = [-1 for i in range(self.V)]
for i in range(self.V):
if self.colorArr[i] == -1:
if not self.isBipartiteUtil(i):
return False
return True
g = Graph(4)
g.graph = [[0, 1, 0, 1],
[1, 0, 1, 0],
[0, 1, 0, 1],
[1, 0, 1, 0]]
print ("Yes" if g.isBipartite() else "No")
输出
是的
时间复杂度:O(V+E)。 辅助空间:O(V),因为我们有一个 V 大小的数组。
如果使用邻接表来表示图,时间复杂度将为 O(V+E)。
适用于连接图和断开图。