下面的表述主要以严谨的图论表述为主:
将阐述以下四点:
- 二分图的定义
- 标记法判别连通图
- 染色法-二分图判别算法(使用深度优先算法 DFS)
一、二分图定义
二分图是图论中的一种特殊模型:
若能将无向图 G=(V,E) 的顶点 V 划分为两个交集为空的顶点集,并且任意边的两个端点都分属于两个集合,则称图 G 为一个为二分图
也就是说:它可以被划分为两个部分,每个部分内的点互不相连。
二、标记法判别连通图
这里补充一个连通图的判别方法,或者说是判断一个图 G=(V,E)能够划分为连通图的最少数量
- 给定一个有 V 个顶点的图(邻接矩阵)
- int k=1
- A 操作={任取一个点标记为 k,将所有与标记 k 相连的点都标记为 k,直到检查到与 k 相连的点都标记为 k,记录已经标记的点总数 X}
- if(X==V) return k
- else k=k+1 重复 A 操作
def dfs(graph, visited, v):
visited[v] = True
count = 1 # 计数当前连通分量的点数
for i in range(len(graph)):
if graph[v][i] == 1 and not visited[i]:
count += dfs(graph, visited, i) # 递归DFS,计数
return count
def find_k(graph):
V = len(graph)
k = 1
while k <= V:
visited = [False] * V
total_count = 0
for v in range(V): # 遍历每个顶点
if not visited[v]:
count = dfs(graph, visited, v) # 深度优先遍历,计数
total_count += count
if total_count == V:
return k
k += 1
# 示例
graph = [
[0, 1, 0, 0],
[1, 0, 1, 1],
[0, 1, 0, 0],
[0, 1, 0, 0]
]
result = find_k(graph)
print(result)
判别连通图的方法下面判别二分图需要用到
三、染色法判别二分图
我们想象二分图也就是把一个图划分,划分内部不相连,也就是我们可以把相连表示仇视关系,利用敌人的敌人是朋友的思想,我就产生了递归染色法的想法:
- 设置一个起始点染色为红色,相连的均染为蓝色,连接蓝色的点检查是否染色,如果没有染色则染为红色,以此遍历整个**连通图,直到染色点数==连通图点数 V_i
- 我们注意到这只能在连通图内进行,所以我们才要用上面引出连通图的算法,所以我们应该在第 1 块、第 2 块……第 k 块都设置一个起始点,这样就可以保证染色到整个图
- 最后,我们检查每一条边是否出现连接的点是同色,如果存在则该图不是二分图,反之成立
Code-hxw
def dfs_connected(graph, visited, v):
visited[v] = True
for i in range(len(graph)):
if graph[v][i] == 1 and not visited[i]: # 如果有边且未访问
dfs_connected(graph, visited, i)
def count_connected_components(graph):
V = len(graph)
visited = [False] * V
count = 0
for v in range(V):
if not visited[v]: # 若未访问,意味着找到一个新连通分量
dfs_connected(graph, visited, v)
count += 1
return count
def is_bipartite_with_groups(graph):
V = len(graph)
color = [-1] * V # -1 表示未染色
groups = {0: [], 1: []} # 用于存储两个组的顶点
def dfs_bipartite(v, c):
color[v] = c
groups[c].append(v) # 将顶点添加到相应的组
for i in range(V):
if graph[v][i] == 1: # 检查相连的边
if color[i] == -1: # 若未染色
if not dfs_bipartite(i, 1 - c): # 递归染色(反色)
return False
elif color[i] == c:
return False
return True
for start in range(V):
if color[start] == -1: # 若未染色,开始染色
groups = {0: [], 1: []}
if not dfs_bipartite(start, 0):
return False, {}
return True, groups
# 示例邻接矩阵
graph = [
[0, 1, 0, 0, 1],
[1, 0, 1, 0, 0],
[0, 1, 0, 1, 0],
[0, 0, 1, 0, 1],
[1, 0, 0, 1, 0]
]
connected_components = count_connected_components(graph)
print(f"Connected components: {connected_components}")
is_bipartite_graph, bipartite_groups = is_bipartite_with_groups(graph)
if is_bipartite_graph:
print("True")
print(f"Bipartite groups: {bipartite_groups[0]} and {bipartite_groups[1]}")
else:
print("False")
参考文献:无
欢迎来到这里!
我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。
注册 关于