二分图

二分划分给每条边规定了一种“跨界”结构。它适合描述两类对象之间的关系，例如任务与机器、作者与论文、变量与约束；同一类内部若也需要连边，就已经超出这份划分的表达范围。

沿路径每走一步，所在侧都会翻转。偶数步回到原侧，奇数步到达另一侧；奇圈要求走奇数步后既回到起点又落到另一侧，于是构成恰到好处的矛盾证书。一个全局分组问题因此可以由局部可检查的圈来判定。

集合族的关联图可把“元素”放在左侧、“集合”放在右侧，并在元素属于集合时连边。这样的图保留了隶属关系的两类角色；若把两侧混成一类顶点，边的端点语义会丢失，匹配所表示的“为每个集合选择不同代表元”也不再清楚。

每棵树公理库树Tree连通且无圈的有限简单无向图，也就是任意两点之间只有一条简单路径的图。都是二分图。任选一个根，按根距离的奇偶分侧，树边总连接相邻层。偶圈也可沿圈交替分侧；三角形则是最小奇圈，第三条边会连接两个已经同色的顶点。

$d$ 维超立方体的顶点是长度为 $d$ 的二进制串，相差一个比特的串相邻。按串中 $1$ 的个数奇偶分侧，每次翻转一个比特都会换侧，所以超立方体是二分图。这个划分来自结构不变量，而非试凑顶点标签。

二分性不等于稀疏。$K_{m,n}$ 有 $mn$ 条边；$K_{3,3}$ 已经足以成为平面性的基本障碍。它没有奇圈，却仍不可平面，说明“无奇圈”和“可无交叉嵌入”约束的是不同结构。

一个含边的连通二分图，其划分在交换 $L,R$ 的意义下唯一：指定一个顶点所在侧后，其余顶点由路径长度奇偶确定。不同连通分量可独立交换两侧，孤立点可放在任意一侧，所以不连通图通常有许多划分。

正常二染色公理库图染色Graph coloring · Vertex coloring为图的顶点赋予颜色并要求每条边的两个端点颜色不同的可行标记。提供线性时间识别算法。BFS 或 DFS 对每个分量交替赋色；若遇到一条同色边，搜索树路径与该边给出奇圈反证。算法输出因而不仅是“否”，还可携带一个可核验的障碍。

对有边二分图，色数公理库色数Chromatic number一张图存在正常顶点染色所需的最少颜色数。恰为二；无边非空图只需一种颜色。所有圈公理库路与圈Path and cycle in a graph用相邻顶点序列刻画图中的行走、简单路径与首尾闭合的简单圈。长度为偶数还会带来许多奇偶分层与交替路性质，但“没有圈”的森林只是二分图中的一个更小子类。

匹配公理库匹配Matching in a graph由彼此不共享端点的边组成、表达一对一配对约束的边集合。在二分图中表达一对一分配。Hall 定理公理库Hall 婚配定理Hall's marriage theorem有限二分图存在饱和一侧的匹配，当且仅当每个该侧顶点子集的邻集至少同样大。刻画何时能饱和指定一侧，Kőnig 定理公理库Kőnig 二分图定理Kőnig's theorem for bipartite graphs二分图中最大匹配大小等于最小顶点覆盖大小。证明最大匹配大小等于最小顶点覆盖大小，网络流归约公理库经由网络流的二分图匹配Bipartite matching via maximum flow把二分图匹配编码为单位容量流网络并由最大流恢复匹配。把这些配对约束变成整数容量流。

建模排班或推荐时，边必须表示一个具体可行配对。偏好顺序、容量、多对一分配或稳定性都需要额外数据；仅有二分图不能自动表达医院—住院医匹配中的名额与双方排序。