图论之二部图图形解析.doc

331 *7.5 二部图及匹配 7.5.1 二部图 在许多实际问题中常用到二部图，本节先介绍二部图的基本概念和主要结论，然后介绍它 的一个重要应用—匹配。 定义 7.5.1 若无向图 的顶点集 能分成两个子集 和 ，满足 , G V E  V 1 V 2 V （1） ， ； 1 2 V V V   1 2 V V    （2） ，均有 ， 。 ( , ) e u v E    1 u V  2 v V  则称 为二部图或偶图(Bipartite Graph 或 Bigraph) ， 和 称为互补顶点子集，常记为 G 1 V 2 V 。如果 中每个顶点都与 中所有顶点邻接，则称 为完全二部图或完全偶 1 2 , , G V V E  1 V 2 V G 图(Complete Bipartite Graph) ，并记为 ，其中 。 , r s K 1 2 , r V s V   由定义可知，二部图是无自回路的图。 图 7-55 中， 都是二部图，其中 是完全二部图 ( ),( ),( ),( ),( ) a b c d e ( ),( ),( ),( ) b c d e 。 1,3 2,3 2,4 3,3 , , , K K K K 图 7-55 二部图示例 显然，在完全二部图中 中，顶点数 ，边数 。 , r s K n r s   m rs  一个无向图如果能画成上面的样式，很容易判定它是二部图。有些图虽然表面上不是上面 的样式，但经过改画就能成为上面的样式，仍可判定它是一个二部图，如图 7-56 中 可改画 ( ) a 成图 ，图 可改画成图 。可以看出，它们仍是二部图。 ( ) b ( ) c ( ) d 图 7-56 二部图示例332 定理 7.5.1 无向图 为二部图的充分必要条件为 中所有回路的长度均为偶数。 , G V E  G 证明 先证必要性。 设 是具有互补节点子集 和 的二部图。 是 中任一长度为 的回 G 1 V 2 V 1 2 1 ( , , , , ) k v v v v  G k 路，不妨设 ，则 ， ，所以 必为偶数，不然，不存在边 。 1 1 v V  2 1 1 m v V   2 2 m v V  k 1 ( , ) k v v 再证充分性。 设 是连通图，否则对 的每个连通分支进行证明。设 只含有长度为偶数的 G G , G V E  回路，定义互补节点子集 和 如下：任取一个顶点 ，令 1 V 2 V 0 v V  1 0 { ( ) ( , ) } V v v V d v v    为偶数 2 1 V V V   现在证明 中任意两节点间无边存在。 1 V 假若存在一条边 ，且 ，则由 到 间的最短路（长度为偶数） ， 边 ( , ) i j v v E  1 , i j v v V  0 v i v 和 到 间的最短路（长度为偶数）所组成的回路的长度为奇数，与假设矛盾。 ( , ) i j v v j v 0 v同理可证 中任意两节点间无边存在。 2 V故 中的每条边必具有形式 ，其中 ， ， 即 是具有互补节点子集 G ( , ) i j v v 1 i v V  2 j v V  G 和 的一个二部图。 1 V 2 V利用定理 7.5.1 可以很快地判断出图 7-57 中的 、 是二部图，而 则不是二部图。 ( ) a ( ) c ( ) b 图 7-57 例 7.5.1 六名间谍 被擒，已知 懂汉语、法语和日语， 懂德语、俄语和日 , , , , , a b c d e f a b 语， 懂英语和法语， 懂西班牙语， 懂英语和德语， 懂俄语和西班牙语，问至少用几个 c d e f 房间监禁他们，能使在一个房间里的人不能直接对话。 解 以六人 为顶点，在懂共同语言的人的顶点间连边得图 （如图 7-58 , , , , , a b c d e f G 所示） ，因为 中没有奇圈，所以 是二部图（如图 7-58 所示） ，故至少应有两间房间 ( ) a G G ( ) b 即可。 333 图 7-58 7.5.2 匹配 二部图的主要应用是匹配， “匹配”是图论中的一个重要内容，它在所谓“人员分配问题” 和“最优分配问题”等运筹学中的问题上有重要的应用。 首先看实际中常碰见的问题：给 个工作人员安排 项任务， 个人用 n m n 表示。并不是每个工作人员均能胜任所有的任务，一个人只能胜任其中 1 2 { , , , } n V x x x   个任务，那么如何安排才能做到最大限度地使每项任务都有人做，并使尽可能多的人 ( 1) k k  有工作做？ 例如，现有 五个人， 五项工作。已知 能胜任 和 ， 1 2 3 4 5 , , , , x x x x x 1 2 3 4 5 , , , , y y y y y 1 x 1 y 2 y 能胜任 和 ， 能胜任 和 ， 能胜任 和 ， 能胜任 、 和 。如何安 2 x 2 y 3 y 3 x 2 y 5 y 4 x 1 y 3 y 5 x 3 y 4 y 5 y 排才能使每个人都有工作做，且每项工作都有人做？ 显然，我们只需构造这样的数学模型：以 和 （i ，j=1，2，3，4，5）为顶点，在 i x j y 与其胜任的工作 之间连边，得二部图 ，如图 7-59 所示，然后在 中找一个边的子集， i x j y G G 使得每个顶点只与一条边关联（图中粗线） ，问题便得以解决了。这就是所谓匹配问题，下面 给出匹配的基本概念和术语。 图 7-59 匹配问题示意图 定义 7.5.2 设无向图 ， 中有边集 ，且在 中任意两条边都没有公 , G V E  G M  E M 共的端点，称边集 为图 的一个匹配(Matching)。 中一条边的两个端点，叫做在 下 M G M M 是配对的。如果 中不存在匹配 ，使得 ，则称 为最大匹配(Maximum G 1 M 1 M M  M Matching)。 对于 的一个匹配 ，若节点 与 中的边关联，则称 是 饱和的(Saturated)，否则 G M v M v M 称 是 不饱和的。 v M 定义 7.5.3 设二部图 ， 是 的一个匹配。若 ， 均是 饱和的， 1 2 , , G V V E  M G 1 v V   v M 则称 是 对 的完全匹配（简称 ―完全匹配） ；若 ， 均是 饱和的，则称 M 1 V 2 V 1 V 2 v V   v M 是 对 的完全匹配（简称 —完全匹配） 。若 既是 ―完全匹配，又是 ―完全匹 M 2 V 1 V 2 V M 1 V 2 V 配（即图 的每个顶点都是饱和的） ，则称 是完全匹配(Complete Matching) 。 G M 显然，完全匹配是最大匹配，但反之不然。 例 7.5.2（1）在图 7-59 中，边集 是一个匹 1 1 2 2 3 5 4 3 5 4 {( , ),( , ),( , ),( , ),( , )} M x y x y x y x y x y  配，而且是是一个最大和完全匹配。