WIKIOI
wiki(I:)
比赛相关
工具软件
语言基础
算法基础
搜索
动态规划
字符串
数学
数据结构
图论
计算几何
杂项
专题
图论部分简介
图论相关概念
图的存储
DFS(图论)
BFS(图论)
树基础
树的直径
最近公共祖先
树的重心
树链剖分
树上启发式合并
虚树
树分治
动态树分治
AHU算法
树哈希
矩阵树定理
有向无环图
拓扑排序
最小生成树
斯坦纳树
最小树形图
最小直径生成树
最短路
拆点
差分约束
k 短路
同余最短路
强连通分量
双连通分量
割点和桥
2-SAT
欧拉图
哈密顿图
二分图
最小环
平面图
图的着色
网络流简介
最大流
最小割
费用流
上下界网络流
Prufer 序列
LGV 引理
弦图
46 objects
本站非官方,所收集资源均来源于网络。
二分图 - 图论
## 定义 二分图,又称二部图,英文名叫 Bipartite graph。 二分图是什么?节点由两个集合组成,且两个集合内部没有边的图。 换言之,存在一种方案,将节点划分成满足以上性质的两个集合。 ![](../images/bi-graph.png) (图源 [英文维基](https://en.wikipedia.org/wiki/Bipartite_graph) ) ## 性质 - 如果两个集合中的点分别染成黑色和白色,可以发现二分图中的每一条边都一定是连接一个黑色点和一个白色点。 - ### question "二分图不存在长度为奇数的环" 因为每一条边都是从一个集合走到另一个集合,只有走偶数次才可能回到同一个集合。 ## 判定 如何判定一个图是不是二分图呢? 换言之,我们需要知道是否可以将图中的顶点分成两个满足条件的集合。 显然,直接枚举答案集合的话实在是太慢了,我们需要更高效的方法。 考虑上文提到的性质,我们可以使用 [DFS(图论)](#) 或者 [BFS](#) 来遍历这张图。如果发现了奇环,那么就不是二分图,否则是。 ## 应用 ### 二分图匹配 #### 二分图最大匹配 详见 [二分图最大匹配](/topic/graph-matching/bigraph-match/) 页面。 #### 二分图最大权匹配 详见 [二分图最大权匹配](/topic/graph-matching/bigraph-weight-match/) 页面。 ### 一般图匹配 详见 [一般图匹配](/topic/graph-matching/general-match/) 页面。