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