二分图

在图论中，二分图是一类特殊的图，又称为双分图、二部图、偶图。二分图的顶点可以分成两个互斥的独立集 U 和 V 的图，使得所有边都是连结一个U 中的点和一个V 中的点。顶点集U、V 被称为是图的两个部分。等价的，二分图可以被定义成图中所有的环都有偶数个顶点。
可以将 和  当做一个着色： 中所有顶点为蓝色， 中所有顶点着绿色，每条边的两个端点的颜色不同，符合图着色问题的要求。相反的，非二分图无法被二着色，例如 (3 个顶点的完全图)，将其中一个顶点着蓝色并且另外一个着绿色后，第三个顶点与上述具有两个颜色的顶点相连，无法再对它着蓝色或绿色。
二分图的一种描述方式为：，包含了独立集 和 ，以及边 的资讯。假如不是连通图，可能有多种将所有顶点分成 和 的方式；在特定的应用场合中，将顶点的两部分、写出来是有必要的。如果，则  称为平衡二分图。如果二分图 以及 的顶点分别有相同的度数，则  被称为是双正则的。
给定一个二分图，在  的一个子图 中， 的边集中的任意两条边都没有共同的端点，则称 是一个匹配。

柯尼希定理

柯尼希定理于1931年，由匈牙利数学家德内斯·柯尼希提出：
一个图是二分图当且仅当它的最小顶点覆盖的顶点数等于最大匹配的边数。
该定理有一个等价形式，一个图是二分图当且仅当它的最大独立集的顶点数与最大匹配的边数之和，等于总顶点个数。再配合一个性质，一个没有孤立顶点的图会满足最小边覆盖的边数加上最大匹配的边数等于总顶点个数，我们有对任何没有孤立顶点的二分图，最小边覆盖的边数等于最大独立集的顶点数，以及最小边覆盖的边数加上最小顶点覆盖的顶点数等于总顶点数。

完美图

所有的二分图和二分图的线图，以及它们的补图都是完美图。很明显的，二分图是完美图，因为他的着色数和最大点团数皆为2，但另一方面，二分图的补图的完美性是相对难以证明的，该性质等价于前面小节的倒数第二个叙述。类似的，二分图的线图的补图的完美性等价于柯尼希定理的叙述，这也是会如此定义完美图的动机之一。而最后剩下的，是二分图的线图的完美性，而这个等价于柯尼希于早些年证明出的定理：二分图的边着色数等于最大度数。
强完美图定理给出完美图的等价条件：一个图是完美图当且仅当所有奇环和奇环的补图都不是它的导出子图。这个刻画可与二分图没有奇环作为子图类比，实际上，在强完美图定理的证明中，二分图、二分图的线图，以及它们的补图占了5 个基本类型中的4 个。

与超图及有向图的关系

一个两部分分别有m 和 n 个顶点二分图的双相邻矩阵是一个(0,1) 矩阵，满足如果两个顶点相邻，矩阵中的该行该列对应到的元素是1，反之如果两点不相邻则对应到0。双相邻矩阵可以用来描述二分图、超图和有向图的等价关系。
超图的定义如同简单图，由顶点和边组成，但是一个边可以有超过两个段点，因为一个边被重新定义做顶点集合的一个子集合。可以用二分图(U,V,E) 来描述超图，其中 U 是超图的顶点集合，V 是超图的边集合，U、V 中的两元素u, v 有连边当且仅当在超图中，u 是 v 的一个段点。在这个对应之下，二分图的双相邻矩阵等于它所对应到的超图的关联矩阵。特别的多重图 (可能会有不同边有相同的两个端点) 可以被视为是超图的特例，只是每个点都恰有两个边而已，根据上述，多重图对应到的二分图满足V 中的顶点度数皆为2。
类似的，所有有向图 (允许两端点相同的自环) 可以一对一对应到所有平衡二分图，方法是将有向图的n 个顶点复制两份，得到集合U、V，U 中的顶点u 有连边到V 中的顶点v 若且为唯若在原本有向图中，有一条边从u 出发指向v。此时，有向图的相邻矩阵可以是任意 阶 (0,1) 矩阵，而且会一对一对应到平衡二分图的双相邻矩阵。

二分性测试

给定一个图，使用深度优先搜寻法，可以在线性时间内判断它是否为二分图，并输出一个二着色(若答案为是)，或是一个奇环(若答案为否)。方法是先用深度优修搜寻法找出图的一个深度优先搜寻森林(各连通部分取一个深度优先搜寻树)，这是图的一个生成森林。接着运用树的搜寻将森林二着色，也就是依序各顶点着和它的父节点相异的颜色。现在检查原图中深度优先搜寻森林以外的其他边，如果所有边的两端点都不同颜色，则这也是原图的一个二着色，并且输出它；如果有一个边e 的两端点相同颜色，则此两端点在同一个连通部分，也就是在森林的同一棵树上，找出在森林中，连接两端点的路径P，因为 P 上的顶点的颜色是交错出现的，因此 P 有偶数个顶点，加上e 就形成一个奇环，并且输出它。
事实上，在上述的算法中，深度优先搜寻森林只是作为一个生成森林，让我们来着色。因此，用不同的方式获得的别的生成森林仍然可以使算法可以运作，例如，可以用广度优先搜寻取出广度优先搜寻森林。
如果原图是线段，或其他二维空间的物件，的交集图，并且有n 个顶点，则可以在时间内输出一个二着色或奇环，纵使它的边树可能会高达。

奇环代表系

奇环代表系问题是一个NP完全问题，问给一个图G(V,E) 和一个正整数k，是否可以删掉k 个顶点使得G 变成一个二分图。这个问题是可定变数决定的(FTP)，更精确地说，存在一个算法所花费时间不超过一个k 的函数乘上一个n 的多项式，其中 n 是G 的顶点数。奇环代表系这个名字是来自二分图的一个等价特性：不存在奇环作为子图。因此，要删掉点使得G 变成二分图其实是在破坏所有的奇环，或者说找出所有奇环的代表系。在右图的中，所有的奇环都包含一个蓝色的顶点(最下面那排的)，因此删掉那两个蓝色顶点会把图变成二分图。
删边二分性问题则是问给定一个图，至少要删除几个边才能让该图变成二分图，这和奇环代表系问题都是重要的图修改算法问题，而且也都是可定变数决定的。事实上，删边二分性问题可以在被解决，其中 m 是原图中的边数。

匹配

一个图的匹配是这个图中一些边所形成的集合，满足任意集合中的两条边都没有公共的顶点。许多关于匹配的问题都有可以被多项式时间的算法解决，例如最大匹配问题 (寻找一个匹配包含最多的边)，极大加权匹配问题，和稳定婚姻问题。在大部分的情况，如果已知原图是二分图，匹配问题会变得单纯很多，而且许多算法只能处理二分图上的情况，例如专门用来计算最大匹配的边数的霍普克洛夫特－卡普算法。
举个简单的例子，假设有一些人想要找寻工作，他们形成集合P，此外还有一些职缺，它们形成集合J，并不是所有人都适合所有的工作，但一个人只能做一份工作。这个案例可以被建模成一个二分图，如果一个人可以做某项工作则将二者连边。一个完美匹配是一个工作的指派使得所有人都有工作做而且每个职缺都有人做。赫尔婚姻定理给出一个二分图有完美匹配的刻画。
杜尔马基-孟德尔索分解将图依据其结构分解成多块，经常用于找寻图的最大匹配。

应用

二分图广泛应用于编码理论中，尤其常应用在收到从通道传来的讯息之后解码过程中。常见的例子有坦纳图和因子图。坦纳图是一个二分图，其中一个独立集搜集所有的一个码字里可以放数码的位置，另一个独立集则包含一些可以放数码的位置的组合，其中每个组合代表一个码字所该符合的限制──那些位置的数码加起来总和是0，而连边就代表了属于。因子图则与低密度奇偶检查码及涡轮码的几率解码中所用到的贝氏网络密切相关。
在计算机科学中，佩特里网是一个数学工具用来分析及模拟并行计算，它将系统模拟成一个有向二分图，其中一部分的顶点被称为“位置”节点，包含一些资源，另一部分的顶点被称为“事件”节点，消耗或生产资源，节点和边之间的关系还有一些限制，这些限制来自系统本身的限制。佩特里网借由有向二分图的性质让系统的行为可以用数学来证明，并且让系统的模拟容易被执行。
在射影几何中，列维图是一个二分图，描述几何构形中点跟边的关系。顶点的两部分分别对应到构形的点跟边，图中两顶点之间连边当且仅当构形中的边通过点，因为两条边顶多交于一点，或者说，两点决定唯一一条边，所以列维图中不存在长度为4 的环作为子图，换言之，列维图的围长大于等于6。