《二部图.ppt》由会员分享，可在线阅读，更多相关《二部图.ppt（26页珍藏版）》请在三一文库上搜索。
1、第9章 一些特殊的图 9.1 二部图 9.2 欧拉图 9.3 哈密顿图 9.4 平面图 1 9.1 二部图 二部图 完全二部图 匹配 极大匹配 最大匹配 匹配数 完备匹配 2 二部图 定义 设无向图 G=, 若能将V 分成V1 和 V2 (V1V2=V, V1V2=), 使得G中的每条边的两个端 点都一个属于V1, 另一个属于V2, 则称G为二部图, 记为, 称V1和V2为互补顶点子集. 又若G 是简单图, 且V1中每个顶点均与V2中每个顶点都相 邻, 则称G为完全二部图, 记为Kr,s, 其中r=|V1|, s=|V2|. 注意: n 阶零图为二部图. 3 二部图的判别法 定理 无向图G=是
2、二部图当且仅当G中无奇圈 例 下述各图都是二部图 4 例 3个图的匹配数 依次为3, 3, 4. 匹配 设G=, 匹配(边独立集): 任2条边均不相邻的边子集 极大匹配: 添加任一条边后都不再是匹配的匹配 最大匹配: 边数最多的匹配 匹配数: 最大匹配中的边数, 记为1 5 匹配 (续) 设M为G中一个匹配 vi与vj被M匹配: (vi,vj)M v为M饱和点: M中有边与v关联 v为M非饱和点: M中没有边与v关联 M为完美匹配: G的每个顶点都是M饱和点 例 关于M1, a,b,e,d是饱和点 f,c是非饱和点 M1不是完美匹配 M2是完美匹配 M1M2 6 二部图中的匹配 定义 设G=为
3、二部图, |V1|V2|, M是G中最 大匹配, 若V1中顶点全是M饱和点, 则称M为G中V1 到V2的完备匹配. 当|V1|=|V2|时, 完备匹配变成完美 匹配. (1)(2)(3) 例 图中红边组成各图的一个匹配，(1)为完备的, 但不是完 美的; (2)不是完备的, 其实(2)中无完备匹配; (3) 是完美的. 7 Hall定理 定理(Hall定理) 设二部图G=中，|V1|V2|. G中存 在从V1到V2的完备匹配当且仅当V1中任意k 个顶点至少与 V2 中的k个顶点相邻(k=1,2,|V1|). 由Hall定理不难证明, 上一页图(2)没有完备匹配. 定理 设二部图G=中, 如果存
4、在t1, 使得V1中每个 顶点至少关联 t 条边, 而V2中每个顶点至多关联t条边，则G 中存在V1到V2的完备匹配. Hall定理中的条件称为“相异性条件”, 第二个定理中的条件 称为 t 条件. 满足 t 条件的二部图一定满足相异性条件. 8 一个应用实例 例 某课题组要从a, b, c, d, e 5人中派3人分别到上海、广州 、香港去开会. 已知a只想去上海，b只想去广州，c, d, e 都表示想去广州或香港. 问该课题组在满足个人要求的 条件下，共有几种派遣方案？ 解 令G=, 其中V1=s, g, x, V2=a, b, c, d, e, E=(u,v) | uV1, vV2, v
5、想去u, 其中s, g, x分别表示上海、广州和香港. G如图所示. G 满足相异性条件，因而可给 出派遣方案，共有9种派遣方案 (请给出这9种方案). 9 9.2 欧拉图 欧拉通路 欧拉回路 欧拉图 半欧拉图 10 哥尼斯堡七桥问题 欧拉图是能一笔画出的边不重复的回路. 11 欧拉图 欧拉通路: 图中行遍所有顶点且恰好经过每条边一次 的通路. 欧拉回路: 图中行遍所有顶点且恰好经过每条边一次 的回路. 欧拉图: 有欧拉回路的图. 半欧拉图: 有欧拉通路而无欧拉回路的图. 几点说明： 上述定义对无向图和有向图都适用. 规定平凡图为欧拉图. 欧拉通路是简单通路, 欧拉回路是简单回路. 环不影响图
6、的欧拉性. 12 欧拉图(续) 例 图中, (1), (4)为欧拉图; (2), (5)为半欧拉图; (3)，(6)既 不 是欧拉图, 也不是半欧拉图. 在(3), (6)中各至少加几条边才能成为欧拉图? 13 欧拉图的判别法 定理 无向图G为欧拉图当且仅当G连通且无奇度顶点. 无向图G是半欧拉图当且仅当G连通且恰有两个奇 度顶点. 定理 有向图D是欧拉图当且仅当D连通且每个顶点的 入度都等于出度. 有向图D具有欧拉通路当且仅当D连通且恰有两个 奇度顶点, 其中一个入度比出度大1, 另一个出度比 入度大1, 其余顶点的入度等于出度. 14 实例 例1 哥尼斯堡七桥问题 例2 下面两个图都是欧拉
7、图. 从A点出发, 如何一次成功地走出一条欧拉回路来？ 15 9.3 哈密顿图 哈密顿通路 哈密顿回路 哈密顿图 半哈密顿图 16 哈密顿周游世界问题 17 哈密顿图的定义 哈密顿通路: 经过图中所有顶点一次且仅一次的通路. 哈密顿回路: 经过图中所有顶点一次且仅一次的回路. 哈密顿图: 具有哈密顿回路的图. 半哈密顿图: 具有哈密顿通路而无哈密顿回路的图. 几点说明： 平凡图是哈密顿图. 哈密顿通路是初级通路，哈密顿回路是初级回路. 环与平行边不影响图的哈密顿性. 18 实例 例 图中, (1), (2)是哈密顿图; (3) 是半哈密顿图. (4)既不是哈密顿图, 也不是半哈密顿图，为什么？
8、 19 无向哈密顿图的一个必要条件 定理 设无向图G=是哈密顿图, 则对于任意V1V 且 V1, 均有 p(G V1) |V1|. 证 设C为G中一条哈密顿回路, 有p(CV1) |V1|. 又因 为 CG, 故 p(G V1) p(C V1) |V1|. 几点说明 定理中的条件是哈密顿图的必要条件, 但不是充分条 件. 可利用该定理判断某些图不是哈密顿图. 由定理可知, Kr,s当sr+1时不是哈密顿图. 当r2时, Kr,r是哈密顿图, 而Kr,r+1是半哈密顿图. 20 实例 例 设G为n阶无向连通简单图, 若G中有割点或桥, 则 G不是哈密顿图. 证 (1) 设v为割点, 则p(Gv)
9、 2|v|=1. 根据定理, G 不是哈密顿图. (2) 若G是K2(K2有桥), 它显然不是哈密顿图. 除K2 外, 其他的有桥连通图均有割点. 由(1), 得证G不是 哈密顿图. 21 无向哈密顿图的一个充分条件 定理 设G是n阶无向简单图, 若任意两个不相邻的顶点 的度数之和大于等于n1, 则G中存在哈密顿通路. 当n3时, 若任意两个不相邻的顶点的度数之和大 于等于n, 则G中存在哈密顿回路, 从而G为哈密顿 图. 22 哈密顿通路(回路)的存在性(续) 定理中的条件是存在哈密顿通路(回路)的充分条 件, 但不是必要条件. 例如, 设G为长度为n1(n4)的路径, 它不满足定理 中哈密
10、顿通路的条件, 但它显然存在哈密顿通路. 设G是长为n的圈, 它不满足定理中哈密顿回路的条 件, 但它显然是哈密顿图. 由定理, 当n3时, Kn均为哈密顿图. 判断某图是否为哈密顿图至今还是一个难题 23 判断是否是哈密顿图的可行方法 n观察出一条哈密顿回路 例如 右图(周游世界问题)中红 边给出一条哈密顿回路, 故它 是哈密顿图. 注意, 此图不满足定理的条件. n满足充分条件 例如 当n3时, Kn中任何两个不同的顶点 u,v, 均 有d(u)+d(v) = 2(n1) n, 所以Kn为哈密顿图. 24 判断是否是哈 密顿图的可行方法(续) 例 1/4国际象棋盘(44方格)上的 跳马问题
11、: 马是否能恰好经过 每一个方格一次后回到原处? 解： 每个方格看作一个顶点, 2个 顶点之间有边当且仅当马可以从一个方格跳到另一个方格, 得到16阶图G, 如左图红边所示. 取V1=a, b, c, d, 则p(GV1) = 6 |V1|, 见右图. 由定理, 图中无哈密顿回路, 故问题无解. 在国际象棋盘(88)上, 跳马问题是否有解? 不满足必要条件 25 应用实例 例 某次国际会议8人参加，已知每人至少与其余7人中的4人有 共同语言，问服务员能否将他们安排在同一张圆桌就座，使 得每个人都能与两边的人交谈？ 解 图是描述事物之间关系的最好的手段之一. 作无向图 G=, 其中V=v|v为与会者，E=(u,v) | u,vV, u与v有共 同语言, 且uv. G为简单图. 根据条件, vV, d(v)4. 于是， u,vV, 有d(u)+d(v)8. 由定理可知G为哈密顿图. 服务员在G 中找一条哈密顿回路C，按C中相邻关系安排座位即可. 由本题想到的：哈密顿图的实质是能将图中所有的顶点排在同 一个圈中. 26