内容发布更新时间 : 2024/11/8 18:10:47星期一 下面是文章的全部内容请认真阅读。

第九章 特 殊 图

9.1 二分图

内容提要

9.1.1 二分图的基本概念

定义9.1 无向图G = 称为二分图（bipartite graph），如果有非空集合X，Y使X∪Y = V，X∩Y = ?，且对每一e?E，?(e) = (x, y)，x?X，y?Y。此时常用表示二分图G。若对X中任一x及Y中任一y恰有一边e?E，使?(e) = (x, y), 则称G为完全二分图（complete bipartite graph）。当?X? = m，?Y? = n时，完全二分图G记为Km,n。

定理9.1 无向图G为二分图的充分必要条件是，G至少有两个顶点,且其所有回路的长度均为偶数。

9.1.2 匹配

定义9.2 设G = 为二分图，M?E。称M为G的一个匹配（matching），如果M中任何两条边都没有公共端点。G的所有匹配中边数最多的匹配称为最大匹配（maximal matching）。如果X(Y)中任一顶点均为匹配M中边的端点，那么称M为X(Y)-完全匹配(perfect matching)。若M既是X-完全匹配又是Y-完全匹配，则称M为G的完全匹配。 定义9.3 设G = ，M为G的一个匹配。

（1）M中边的端点称为M-顶点，其它顶点称为非M-顶点。

（2）G中vk到vl的通路P称为交替链，如果P的起点vk和终点vl为非M-顶点，而其边的序列中非匹配边与匹配边交替出现（从而首尾两边必为非匹配边，除顶点vk，vl以外各

''

顶点均为M-顶点）。特别地，当一边（v, v）两端点均为非M-顶点，通路（v, v）亦称为交替链。

以下算法可把G中任一匹配M扩充为最大匹配，此算法是Edmonds于1965年提出的，被称为匈牙利算法，其步骤如下：

（1）首先用（*）标记X中所有的非M-顶点，然后交替进行步骤（2），（3）。

（2）选取一个刚标记（用（*）或在步骤（3）中用（yi）标记）过的X中顶点，例如顶点xi，然后用（xi）去标记Y中顶点y，如果xi与y为同一非匹配边的两端点，且在本步骤中y尚未被标记过。重复步骤（2），直至对刚标记过的X中顶点全部完成一遍上述过程。 （3）选取一个刚标记（在步骤（2）中用（xi）标记）过的Y中结点，例如yi，用（yi）去标记X中结点x，如果yi与x为同一匹配边的两端点，且在本步骤中x尚未被标记过。重复步骤（3），直至对刚标记过的Y中结点全部完成一遍上述过程。

（2），（3）交替执行，直到下述情况之一出现为止：

（Ⅰ）标记到一个Y中顶点y，它不是M-顶点。这时从y出发循标记回溯，直到（*）标记的X中顶点x，我们求得一条交替链。设其长度为2k+1，显然其中k条是匹配边，k+1条是非匹配边。

（Ⅱ）步骤（2）或（3）找不到可标记结点，而又不是情况（Ⅰ）。 （4） 当 （2），（3）步骤中断于情况（Ⅰ），则将交替链中非匹配边改为匹配边，原匹配边改为非匹配边（从而得到一个比原匹配多一条边的新匹配），回到步骤（1），同时消除一切现有标记。

（5）对一切可能，（2）和（3）步骤均中断于情况（Ⅱ），或步骤（1）无可标记结点，算法终止（算法找不到交替链）。

1

定理9.2 设图G = 。G有X-完全匹配的充分必要条件是：对每一S?X有

?N(S)?≥? S ?

习题解答

练习9.1

1、判别下列各图（图9.8）是否为二分图，是否为完全二分图。

图9.8

解 （1）是二分图，但不是完全二分图。

（2）是完全二分图。

（3）不是二分图。

2、假定G是二分图。如何安排G中顶点的次序可使G的邻接矩阵呈(

0B)形，其中B，C0C为矩阵，0为零矩阵。

解 因为 G是二分图，故可把G中所有顶点分为X、Y两个集合，使得 ?e(e?E→?(e)=(x, y)∧x?X∧y?Y) 只要按顺序先排X中的顶点，再排Y中的顶点，就可形成(0B)形的邻接矩阵 C03、六名间谍a，b，c，d，e，f被我捕获，他们分别懂得的语言是{汉语，法语，日语}，{德语，日语，俄语}，{英语，法语}，{汉语，西班牙语}，{英语，德语}，{俄语，西班牙语}，问至少用几个房间监禁他们，才能使同一房间的人不能互相直接对话。 解 如下图所示，顶点表示间谍，边表示间谍间能够直接对话 aefdbc 由于此图是二分图，因此只需要两个房间，分别监禁{a, e, f}和{b, c, d}，就可包证同一房间的人不能互相直接对话。 n24、设（n, m）图G为二分图，证明m≤。 4证 由于（n, m）图G是简单二分图，因此可将G中顶点分为X、Y两个集合，G中任一边均关联X、Y的各一个顶点，且 |X| ≥ 1， |Y| ≥ 1，|X| + |Y| = n 2 设 |X| = n1，则 |Y| = n－n1，那么边数m满足

n2n2n2?(n1?)≤ m ≤ |X|?|Y| = n1(n?n1)?

442n2故 m≤ 4 5、作一个二分图G = ，使它恰有4！个X-完全匹配 。 解 如下图所示，完全二分图K4, 4共有4！个X-完全匹配（Y-完全匹配） x1x2x3x4y1y2y3y4 6、用匈牙利算法求图9.9中二分图的最大匹配。 x3 x4 x6 x5 x1 x2 y3 y1 y2 y4 y5 y6 图9.9

解 （1）置M=?，对x1~x6标记（*）

（2）找到交替链(x1, y3)，置M={(x1, y3)}

（3）找到交替链(x2, y1)，置M={(x1, y3)，(x2, y1)}

（4）找到交替链(x3, y2)，置M={(x1, y3)，(x2, y1)，(x3, y2)}

（5）找到交替链(x5, y4)，置M={(x1, y3)，(x2, y1)，(x3, y2)，(x5, y4)} （6）找不到新的交替链，算法终止。匹配

M={(x1, y3)，(x2, y1)，(x3, y2)，(x5, y4)} 即为最大匹配，如下图所示 x3 x4 x6 x1 x2 x5

y3 y1 y2 y4 y5 y6

7、某单位有7个岗位空缺，它们是p1，p2,…,p7 。应聘的10人m1，m2,…,m10所适合的岗位分别是{p1，p5，p6}，{p2，p6，p7}，{p3，p4}，{p1，p5}，{p6，p7}，{p3}，{p2, p3}，

3