二分图

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

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

先看四圈 $a-b-c-d-a$。把 $a$ 放左侧，边 $ab,ad$ 迫使 $b,d$ 放右侧，边 $bc$ 再迫使 $c$ 放左侧；最后检查 $cd$，两端异侧，划分成功。因此 $L=\{a,c\}$、$R=\{b,d\}$。若再加入对角线 $ac$，这条同侧边立即使划分失败，而且 $a,b,c,a$ 就是可直接核查的奇圈。

集合族的关联图则预先给出了两侧：一侧放带“元素”标签的对象，另一侧放带“集合”标签的对象，元素属于集合时连边。即使某个对象在原问题中兼有两种身份，也要在图中保留两个角色副本，才能让边始终表达元素到集合的隶属关系。

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

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

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

一个非空连通二分图，其划分在交换 $L,R$ 的意义下唯一：指定一个顶点所在侧后，其余顶点由路径长度奇偶确定；两条路径若给出不同奇偶，就会产生奇圈。单个孤立点也有“放左侧”与“放右侧”这两个选择。因此若二分图有 $c$ 个连通分量，区分左右名称时恰有 $2^c$ 个划分，包括空图的 $2^0=1$ 个划分。这里没有要求两侧等大，额外施加平衡条件会改变计数。

正常二染色提供线性时间识别算法。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用单位容量流求二分图匹配，并从终态搜索同时提取 Hall 障碍、等值割和最小顶点覆盖。把这些配对约束变成整数容量流。

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