二部图及匹配.doc

*7.5 二部图及匹配 7.5.1二部图 在许多实际问题中常用到二部图，本节先介绍二部图的基本概念和主要结论，然后介绍它的一个重要应用匹配。 定义7.5.1 若无向图的顶点集能分成两个子集和，满足 （1），； （2），均有，。 则称为二部图或偶图，和称为互补顶点子集，常记为。如果中每个顶点都与中所有顶点邻接，则称为完全二部图或完全偶图，并记为，其中。 由定义可知，二部图是无自回路的图。 图7-55中，都是二部图，其中是完全二部图。 图7-55二部图显然，在完全二部图中中，顶点数，边数。 一个无向图如果能画成上面的样式，很容易判定它是二部图。有些图虽然表面上不是上面的样式，但经过改画就能成为上面的样式，仍可判定它是一个二图，如图756中可改画成图，图可改画成图。可以看出，它们仍是二图。 图7-56二部图 定理7.5.1 无向图为二部图的充分必要条件为中所有回路的长度均为偶数。 证先证必要性。 设是具有互补节点子集和的二部图。是中任一长度为的回路，不妨设，则，，所以必为偶数，不然，不存在边。 再证充分性。 设是连通图，否则对的每个连通分支进行证明。设只含有长度为偶数的回路，定义互补节点子集和如下：任取一个顶点，令 现在证明中任意两节点间无边存在。 假若存在一条边，且，则由到间的最短路（长度为偶数）， 边和到间的最短路（长度为偶数）所组成的回路的长度为奇数，与假设矛盾。 同理可证中任意两节点间无边存在。 故中的每条边必具有形式，其中，， 即是具有互补节点子集和的一个二部图。 利用定理7.5.1可以很快地判断出图757中的、是二部图，而则不是二部图。 图7-57 例7.5.1 六名间谍被擒，已知懂汉语、法语和日语，懂德语、俄语和日语，懂英语和法语，懂西班牙语，懂英语和德语，懂俄语和西班牙语，问至少用几个房间监禁他们，能使在一个房间里的人不能直接对话。 解 以六人为顶点，在懂共同语言的人的顶点间连边得图（如图7-58所示），因为中没有奇圈，所以是二部图（如图7-58所示），故至少应有两间房间即可。 图7-58 7.5.2 匹配 二部图的主要应用是匹配，匹配是图论中的一个重要内容，它在所谓人员分配问题和最优分配问题等运筹学中的问题上有重要的应用。 首先看实际中常碰见的问题：给个工作人员安排项任务，个人用表示。并不是每个工作人员均能胜任所有的任务，一个人只能胜任其中个任务，那么如何安排才能做到最大限度地使每项任务都有人做，并使尽可能多的人有工作做？ 例如，现有五个人，五项工作。已知能胜任和，能胜任和，能胜任和，能胜任和，能胜任、和。如何安排才能使每个人都有工作做，且每项工作都有人做？ 显然，我们只需构造这样的数学模型：以和（i，j=1，2，3，4，5）为顶点，在与其胜任的工作之间连边，得二部图，如图7-59所示，然后在中找一个边的子集，使得每个顶点只与一条边关联（图中粗线），问题便得以解决了。这就是所谓匹配问题，下面给出匹配的基本概念和术语。 图7-59匹配问题 定义7.5.2 设无向图，中有边集，且在中任意两条边都没有公共的端点，称边集为图的一个匹配。中一条边的两个端点，叫做在下是配对的。如果中不存在匹配，使得，则称为最大匹配。 对于的一个匹配，若节点与中的边关联，则称是饱和的，否则称是不饱和的。 定义7.5.3 设二部图，是的一个匹配。若，均是饱和的，则称是对的完全匹配（简称―完全匹配）；若，均是饱和的，则称是对的完全匹配（简称—完全匹配）。若既是―完全匹配，又是―完全匹配（即图的每个顶点都饱和的），则称是完全匹配。 显然，完全匹配是最大匹配，但反之不然。 例7.5.2（1）在图7-59中，边集是一个匹配，而且是是一个最大和完全匹配。 （2）在图7-60中，边集和，都是图的最大匹配，也是―完全匹配，但不是完全匹配。在图7-60中，边集是完全匹配。 图7-60 为了寻求二部图的最大匹配，下面交替路和可扩路两个概念。 定义7.5. 设是一个二部图，是图的一个匹配，是中的一条路，如果是由属于和不属于的边交替出现组成，则称为的交替路。如果交替路的始点和终点都是不饱和点，则称为的可扩路—Extensible Path)。 例如，在图7-60中，对于匹配，路，，，都是交替路，其中的始点和终点都是不饱和点，所以这两条路是可扩路。 可扩路具有如下性质：可扩路的长度必为奇数，且属于的边比不属于的边1条。 如果在一条可扩路中把属于中的边从匹配中去掉，把不属于中的边添入到匹配中， 则得到新的匹配，的边数比多１。例如，在图7-60中，对于匹配，是可扩路，将中属于中的边，，从匹配中去掉， 把不属于中的边添入到匹配中，则得到新的匹配，中的边数由中的3条增至4条。如果图中还存在可扩路， 再按上面的步骤做， 所得到的匹配的边数