[科普中国]-座位安排中体现的图论理论——匹配

在义务教育与高中阶段，几乎在每一学期初的时候，班主任都会重新安排全班同学的座位。一张桌子最多只能坐下一名同学，但也有可能出现空置的桌子。但由于受到现实条件（学生身高、个人意愿等）的影响，每个学生期望的座位位置是不同的，如何将每位学生都能安排在其期望的座位上成为一个值得探讨的问题。这是图论中匹配概念的一个原始模型，通常将有同学的桌子组成的这个集合称为匹配集合，将同学对应到桌子的过程就被称为匹配过程。

我们仍以座位安排为例做进一步的解释。将每位学生的期望座位列出一个表格，并且在表格的基础上作出二分图就是一种方法：

想要做到将每个学生都安排在其期望的座位上，需要每个学生都能匹配到互异的座位，即二分图中的线段（在匹配中称之为边）存在n个边，且这些边的端点互相不接触的情况。也就是说存在一个边集E使得集合中的任意两边不邻接，并且对每个结点bi而言，都能与集合E中边的左端点重合。这也就是所说的完全匹配，抽象为概念就是二分图G(V1,V2)的完全匹配，即存在单射f:V1→V2，使得任意v=V1，且v与f（v）相邻。其中V1表示的是二分图左边的结点，而V2表示的是二分图右边的结点。通俗而言，对于排座问题，完全匹配需要任意n个同学至少需要期望n个座位位置。

那么如果在很难达到完全匹配的实际情况中，如何分配能够使最多的学生都满意自己的座位呢？这里就要引出最大匹配的概念了。匹配指的是对于无环图G来说，M∈E(G)，且M≠∅，如果M中任意两条边在G中均不相连，就称M为G的一个匹配。也就是说匹配是将学生与座位能够一一对应的集合。匹配相对于完全匹配而言，不同的条件在于不要求对每一个结点都有一个匹配关系，也就是说匹配不同于完全匹配，有的学生在限定期望条件的前提下不会有分配的座位。那么最大匹配的意思是，最大匹配Mmax的元素数量要大于其他任意匹配集的元素数。这个元素数也被叫做匹配数。

与匹配路径M有关的概念也有两种，一种是交替路径，指的是对于E(G)来说，每一条边交替地属于匹配路径M或者不属于M，比如第1、第3等奇数条路径属于M而第2、第4等偶数路径不属于M；另一种是增广路径，指的是从M中没有的起点开始到M中没有的终点结束，结合上文可以看出，当增广路径为空集时，M将成为完全匹配。

日常生活中也存在更能凸显匹配概念的事例，譬如工作分配问题，即将现有的个人与份工作进行匹配，使得每个人都能够得到自己擅长工作的匹配过程；譬如运输问题，即将m座不同的矿山与使用矿山的n个工厂进行匹配，使得每个工厂都能够得到自己需要材料的矿山供货的过程等等。

本作品为“科普中国-科学原理一点通”原创，转载时务请注明出处。