二分图

在图论中，二分图（bipartite graph）是一类特殊的图，又称为二部图、偶图、双分图。二分图的顶点可以分成两个互斥的独立集 U 和 V 的图，使得所有边都是连结一个 U 中的点和一个 V 中的点。顶点集 U、V 被称为是图的两个部分。等价的，二分图可以被定义成图中所有的环都有偶数个顶点。

可以将 ${\displaystyle U}$，与分别是两个独立集。X能被Y匹配当且仅当${\displaystyle |N(S)|\ge <!--\; \ge \; -->|S|}$是的任意子集。

霍尔定理给出了一种证明完美匹配是否存在的方式，该定理也常常被用于求解SDR问题（system of distinct representatives，不同代表问题）。

在SDR问题中，你拥有个不同的集合，你需要为每个集合找到一个独特的代表元素。一个集合集拥有SDR当且仅当任意个集合的并包含个不同的元素。

霍尔定理有时也被称作霍尔婚姻定理（Hall's Marriage Theorem），用以解决男女的婚姻匹配问题。

给定一个图，使用深度优先搜寻法，可以在线性时间内判断它是否为二分图，并输出一个二着色 (若答案为是)，或是一个奇环 (若答案为否)。方法是先用深度优先搜寻法找出图的一个深度优先搜寻森林 (各连通部分取一个深度优先搜寻树)，这是图的一个生成森林。接着运用树的搜寻将森林二着色，也就是依序各顶点着和它的父节点相异的颜色。现在检查原图中深度优先搜寻森林以外的其他边，如果所有边的两端点都不同颜色，则这也是原图的一个二着色，并且输出它；如果有一个边 e 的两端点相同颜色，则此两端点在同一个连通部分，也就是在森林的同一棵树上，找出在森林中，连接两端点的路径 P，因为 P 上的顶点的颜色是交错出现的，因此 P 有偶数个顶点，加上 e 就形成一个奇环，并且输出它。

事实上，在上述的算法中，深度优先搜寻森林只是作为一个生成森林，让我们来着色。因此，用不同的方式获得的别的生成森林仍然可以使算法可以运作，例如，可以用广度优先搜寻取出广度优先搜寻森林。

如果原图是线段，或其他二维空间的物件，的交集图（英语：intersection graph），并且有 n 个顶点，则可以在 ${\displaystyle O(n\log <!--\; \; -->n)}$时间内输出一个二着色或奇环，纵使它的边树可能会高达 ${\displaystyle O(n^2)}$。

奇环代表系问题是一个NP完全问题，问给一个图 G(V,E) 和一个正整数 k，是否可以删掉 k 个顶点使得 G 变成一个二分图。这个问题是可定变数决定的 (FTP（英语：Parameterized complexity#FTP）)，更精确地说，存在一个算法所花费时间不超过一个 k 的函数乘上一个 n 的多项式，其中 n 是G 的顶点数。奇环代表系这个名字是来自二分图的一个等价特性：不存在奇环作为子图。因此，要删掉点使得 G 变成二分图其实是在破坏所有的奇环，或者说找出所有奇环的代表系。在右图的中，所有的奇环都包含一个蓝色的顶点 (最下面那排的)，因此删掉那两个蓝色顶点会把图变成二分图。

删边二分性问题则是问给定一个图，至少要删除几个边才能让该图变成二分图，这和奇环代表系问题都是重要的图修改算法问题，而且也都是可定变数决定的。事实上，删边二分性问题可以在 ${\displaystyle O(2^k{m}^2)}$被解决，其中 m 是原图中的边数。

一个图的匹配是这个图中一些边所形成的集合，满足任意集合中的两条边都没有公共的顶点。许多关于匹配的问题都有可以被多项式时间的算法解决，例如最大匹配问题 (寻找一个匹配包含最多的边)，极大加权匹配问题（英语：Maximum weight matching），和稳定婚姻问题。在大部分的情况，如果已知原图是二分图，匹配问题会变得单纯很多，而且许多算法只能处理二分图上的情况，例如专门用来计算最大匹配的边数的霍普克洛夫特－卡普算法。

举个简单的例子，假设有一些人想要找寻工作，他们形成集合 P，此外还有一些职缺，它们形成集合 J，并不是所有人都适合所有的工作，但一个人只能做一份工作。这个案例可以被建模成一个二分图${\displaystyle (P,J,E)}$，如果一个人可以做某项工作则将二者连边。一个完美匹配是一个工作的指派使得所有人都有工作做而且每个职缺都有人做。霍尔婚配定理给出一个二分图有完美匹配的刻画。

杜尔马基-孟德尔索分解（英语：Dulmage–Mendelsohn decomposition）将图依据其结构分解成多块，经常用于找寻图的最大匹配。

二分图广泛应用于编码理论中，尤其常应用在收到从通道传来的讯息之后解码过程中。常见的例子有坦纳图和因子图。坦纳图是一个二分图，其中一个独立集搜集所有的一个码字里可以放数码的位置，另一个独立集则包含一些可以放数码的位置的组合，其中每个组合代表一个码字所该符合的限制──那些位置的数码加起来总和是 0，而连边就代表了属于。因子图则与低密度奇偶检查码及涡轮码的几率解码中所用到的贝氏网络密切相关。

在计算机科学中，佩特里网是一个数学工具用来分析及模拟并行计算，它将系统模拟成一个有向二分图，其中一部分的顶点被称为“位置”节点，包含一些资源，另一部分的顶点被称为“事件”节点，消耗或生产资源，节点和边之间的关系还有一些限制，这些限制来自系统本身的限制。佩特里网借由有向二分图的性质让系统的行为可以用数学来证明，并且让系统的模拟容易被执行。

在射影几何中，列维图（英语：Levi graph）是一个二分图，描述几何构形（英语：Configuration (geometry)）中点跟边的关系。顶点的两部分分别对应到构形的点跟边，图中两顶点之间连边当且仅当构形中的边通过点，因为两条边顶多交于一点，或者说，两点决定唯一一条边，所以列维图中不存在长度为 4 的环作为子图，换言之，列维图的围长大于等于 6。