离散数学：第8章 一些特殊的图

1、1第第8章章 一些特殊的图一些特殊的图 8.1 二部图二部图8.2 欧拉图欧拉图8.3 哈密顿图哈密顿图8.4 平面图平面图 28.1 二部图二部图 二部图二部图完全二部图完全二部图匹配匹配极大匹配极大匹配最大匹配最大匹配匹配数匹配数完备匹配完备匹配 3二部图定义定义8.1 设无向图设无向图 G=, 若能将若能将V 分成分成V1 和和 V2 使得使得V1 V2=V, V1 V2=, 且且G中的每条边的两个端点都一个中的每条边的两个端点都一个属于属于V1, 另一个属于另一个属于V2, 则称则称G为为二部图二部图, 记为记为, 称称V1和和V2为为互补顶点子集互补顶点子集. 又若又若G是简单图是简

2、单图, 且且V1中每个中每个顶点均与顶点均与V2中每个顶点都相邻中每个顶点都相邻, 则称则称G为为完全二部图完全二部图, 记为记为Kr,s, 其中其中r=|V1|, s=|V2|. K23K334二部图的判别法二部图的判别法 定理定理 无向图无向图G=是二部图当且仅当是二部图当且仅当G中无奇圈中无奇圈 例例 下述各图都是二部图下述各图都是二部图 5二部图的判别定理定理定理8.1 无向图无向图G=是二部图当且仅当是二部图当且仅当G中无奇长度中无奇长度的回路的回路证证 必要性必要性. 设设G=是二部图是二部图, 每条边只能从每条边只能从V1到到V2, 或从或从V2到到V1, 故任何回路必为偶长度故

3、任何回路必为偶长度.充分性充分性. 不妨设不妨设G至少有一条边且连通至少有一条边且连通. 取任一顶点取任一顶点u, 令令 V1=v | v V d(v,u)为偶数为偶数, V2=v | v V d(v,u)为为奇数奇数则则V1 V2=V, V1 V2=. 先证先证V1中任意两点不相邻中任意两点不相邻. 假设假设存在存在s,t V1, e=(s,t) E. 设设 1, 2分别是分别是u到到s,t的短程线的短程线, 则则 1 e 2是一条回路是一条回路, 其长度为奇数其长度为奇数, 与假设矛盾与假设矛盾. 同理同理可可证证V2中任意两点不相邻中任意两点不相邻. 6实例非二部图非二部图非二部图非二部

4、图7匹配匹配 设设G=,匹配匹配(边独立集边独立集): 任任2条边均不相邻的边子集条边均不相邻的边子集极大匹配极大匹配: 添加任一条边后都不再是匹配的匹配添加任一条边后都不再是匹配的匹配最大匹配最大匹配: 边数最多的匹配边数最多的匹配匹配数匹配数: 最大匹配中的边数最大匹配中的边数, 记为记为 1 例例 下述下述3个图的匹配数个图的匹配数 依次为依次为3, 3, 4. 8匹配匹配 (续续)设设M为为G中一个匹配中一个匹配vi与与vj被被M匹配匹配: (vi,vj) Mv为为M饱和点饱和点: M中有边与中有边与v关联关联v为为M非饱和点非饱和点: M中没有边与中没有边与v关联关联M为完美匹配为完

5、美匹配: G的每个顶点都是的每个顶点都是M饱和点饱和点 例例 关于关于M1, a,b,e,d是饱和点是饱和点 f,c是非饱和点是非饱和点 M1不是完美匹配不是完美匹配 M2是完美匹配是完美匹配M1M29二部图中的匹配二部图中的匹配 定义定义 设设G=为二部图为二部图, |V1| |V2|, M是是G中最中最大匹配大匹配, 若若V1中顶点全是中顶点全是M饱和点饱和点, 则称则称M为为G中中V1到到V2的的完备匹配完备匹配. 当当|V1|=|V2|时时, 完备匹配变成完美完备匹配变成完美匹配匹配.(1)(2)(3)例例 图中红边组成各图的一个匹配，图中红边组成各图的一个匹配，(1)为完备的为完备的

6、, 但不是完但不是完美的美的; (2)不是完备的不是完备的, 其实其实(2)中无完备匹配中无完备匹配; (3) 是完美的是完美的.10Hall定理定理 定理定理(Hall定理定理) 设二部图设二部图G=中，中，|V1| |V2|. G中存中存在从在从V1到到V2的完备匹配当且仅当的完备匹配当且仅当V1中任意中任意k 个顶点至少与个顶点至少与V2中的中的k个顶点相邻个顶点相邻(k=1,2,|V1|).由由Hall定理不难证明定理不难证明, 上一页图上一页图(2)没有完备匹配没有完备匹配. 定理定理 设二部图设二部图G=中中, 如果存在如果存在t 1, 使得使得V1中每个中每个顶点至少关联顶点至少

7、关联 t 条边条边, 而而V2中每个顶点至多关联中每个顶点至多关联t条边，则条边，则G中存在中存在V1到到V2的完备匹配的完备匹配. Hall定理中的条件称为定理中的条件称为“相异性条件相异性条件”, 第二个定理中的条第二个定理中的条件件称为称为 t 条件条件. 满足满足 t 条件的二部图一定满足相异性条件条件的二部图一定满足相异性条件.11实例例例1 某中学有某中学有3个课外活动小组个课外活动小组:数学组数学组, 计算机组和生物计算机组和生物组组. 有赵有赵,钱钱,孙孙,李李,周周5名学生名学生, 问分别在下述问分别在下述3种情况下种情况下, 能能否选出否选出3人各任一个组的组长人各任一个组

8、的组长?(1) 赵赵, 钱为数学组成员钱为数学组成员, 赵赵,孙孙,李为计算机组成员李为计算机组成员, 孙孙,李李,周为生物组成员周为生物组成员.(2) 赵为数学组成员赵为数学组成员, 钱钱,孙孙,李为计算机组成员李为计算机组成员, 钱钱,孙孙,李李,周周为生物组成员为生物组成员.(3) 赵为数学组和计算机组成员赵为数学组和计算机组成员, 钱钱,孙孙,李李,周为生物组成员周为生物组成员.12实例(续)解解(1),(2)有多种方案有多种方案, (3) 不可能不可能(1)数数计计生生赵赵 钱钱 孙孙 李李 周周(2)数数计计生生赵赵 钱钱 孙孙 李李 周周(3)数数计计生生赵赵 钱钱 孙孙 李李

9、周周13一个应用实例一个应用实例 例例 某课题组要从某课题组要从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) | u V1, v V2, v想去想去u,其中其中s, g, x分别表示上海、广州和香港分别表示上海

10、、广州和香港. G如图所示如图所示. G 满足相异性条件，因而可给满足相异性条件，因而可给出派遣方案，共有出派遣方案，共有9种派遣方案种派遣方案(请给出这请给出这9种方案种方案). 148.2 欧拉图欧拉图欧拉通路欧拉通路欧拉回路欧拉回路欧拉图欧拉图半欧拉图半欧拉图 15哥尼斯堡七桥问题哥尼斯堡七桥问题 欧拉图是能一笔画出的边不重复的回路欧拉图是能一笔画出的边不重复的回路. . 16欧拉图欧拉图 欧拉通路欧拉通路: 图中行遍所有顶点且恰好经过每条边一次的通路图中行遍所有顶点且恰好经过每条边一次的通路. 欧拉回路欧拉回路: 图中行遍所有顶点且恰好经过每条边一次的回路图中行遍所有顶点且恰好经过每条

11、边一次的回路.欧拉图欧拉图: 有欧拉回路的图有欧拉回路的图.半欧拉图半欧拉图: 有欧拉通路而无欧拉回路的图有欧拉通路而无欧拉回路的图.几点说明：几点说明：上述定义对无向图和有向图都适用上述定义对无向图和有向图都适用.规定平凡图为欧拉图规定平凡图为欧拉图.欧拉通路是简单通路欧拉通路是简单通路, 欧拉回路是简单回路欧拉回路是简单回路.环不影响图的欧拉性环不影响图的欧拉性. 17欧拉图欧拉图( (续续) )例例 图中图中, (1), (4)为欧拉图为欧拉图; (2), (5)为半欧拉图为半欧拉图; (3)，(6)既不既不 是欧拉图是欧拉图, 也不是半欧拉图也不是半欧拉图. 在在(3), (6)中各至

12、少加几条边才能成为欧拉图中各至少加几条边才能成为欧拉图?18欧拉图的判别法欧拉图的判别法 定理定理 无向图无向图G为欧拉图当且仅当为欧拉图当且仅当G连通且无奇度顶点连通且无奇度顶点. 无向图无向图G是半欧拉图当且仅当是半欧拉图当且仅当G连通且恰有两个奇度顶点连通且恰有两个奇度顶点. 定理定理 有向图有向图D是欧拉图当且仅当是欧拉图当且仅当D连通且每个顶点的入度都连通且每个顶点的入度都等于出度等于出度. 有向图有向图D具有欧拉通路当且仅当具有欧拉通路当且仅当D连通且恰有两个奇度顶连通且恰有两个奇度顶点点, 其中一个入度比出度大其中一个入度比出度大1, 另一个出度比入度大另一个出度比入度大1, 其

13、余其余顶点的入度等于出度顶点的入度等于出度.19实例实例例例1 哥尼斯堡七桥问题哥尼斯堡七桥问题例例2 下面两个图都是欧拉图下面两个图都是欧拉图. 从从A点出发点出发, 如何一次成功地走出一条欧拉回路来？如何一次成功地走出一条欧拉回路来？ 20实例无欧拉通路无欧拉通路欧拉图欧拉图欧拉图欧拉图有欧拉通路有欧拉通路非欧拉图非欧拉图有欧拉通路有欧拉通路非欧拉图非欧拉图无欧拉通路无欧拉通路21实例欧拉图欧拉图无欧拉通路无欧拉通路无欧拉通路无欧拉通路有欧拉通路有欧拉通路无欧拉回路无欧拉回路无欧拉通路无欧拉通路有欧拉通路有欧拉通路无欧拉回路无欧拉回路228.3 哈密顿图哈密顿图 哈密顿通路哈密顿通路哈密顿

14、回路哈密顿回路哈密顿图哈密顿图半哈密顿图半哈密顿图 23哈密顿周游世界问题哈密顿周游世界问题 24哈密顿回路与哈密顿通路哈密顿通路哈密顿通路: : 经过图中所有顶点一次且仅一次的通路经过图中所有顶点一次且仅一次的通路. .哈密顿回路哈密顿回路: : 经过图中所有顶点一次且仅一次的回路经过图中所有顶点一次且仅一次的回路. .哈密顿图哈密顿图: : 具有哈密顿回路的图具有哈密顿回路的图. .半哈密顿图半哈密顿图: : 具有哈密顿通路而无哈密顿回路的图具有哈密顿通路而无哈密顿回路的图. .说明：说明：哈密顿通路是哈密顿通路是初级通路初级通路哈密顿回路是哈密顿回路是初级回路初级回路有哈密顿通路不一定有

15、哈密顿回路有哈密顿通路不一定有哈密顿回路环与平行边不影响图的哈密顿性环与平行边不影响图的哈密顿性25哈密顿图的必要条件定理定理8.6 若无向图若无向图G=是哈密顿图是哈密顿图, 则对于则对于V的任意的任意非空真子集非空真子集V1均有均有 p(G V1) |V1|.证证 设设C为为G中一条哈密顿回路中一条哈密顿回路, 有有p(C V1) |V1|. 又因为又因为C G, 故故 p(G V1) p(C V1) |V1|. 例如例如 当当rs时时, Kr,s不是哈密顿图不是哈密顿图推论推论 有割点的图不是哈密顿图有割点的图不是哈密顿图26实例例例2 证明下述各图不是哈密顿图证明下述各图不是哈密顿图:

16、(a)(b)(c)(c) 中存在哈密顿通路中存在哈密顿通路27实例例例3 证明右图不是哈密顿图证明右图不是哈密顿图证证 假设存在一条哈密顿回路假设存在一条哈密顿回路, a,f,g是是2度顶点度顶点, 边边(a,c), (f,c)和和(g,c)必在这条哈密顿回路上必在这条哈密顿回路上,从而点从而点c出现出现3次次, 矛盾矛盾.abcde fg此外此外, 该图满足定理该图满足定理6.10的条件的条件, 这表明此条件是必要、这表明此条件是必要、而不充分的而不充分的.又又, 该图有哈密顿通路该图有哈密顿通路.28存在哈密顿回路(通路)的充分条件定理定理8.7 设设G是是n(n 3)阶无向简单图阶无向简

17、单图, 若任意两个不相邻若任意两个不相邻的顶点的度数之和大于等于的顶点的度数之和大于等于n 1, 则则G中存在哈密顿通路中存在哈密顿通路;若任意两个不相邻的顶点的度数之和大于等于若任意两个不相邻的顶点的度数之和大于等于n, 则则G中中存在哈密顿回路存在哈密顿回路, 即即G为哈密顿图为哈密顿图.推论推论 设设G是是n(n 3)阶无向简单图阶无向简单图, 若若(G) n/2, 则则G是哈是哈密顿图密顿图当当n 3时时, Kn是哈密顿图是哈密顿图; 当当r=s 2时时, Kr,s是哈密顿图是哈密顿图.定理定理8.8 设设D是是n(n 2)阶有向图阶有向图, 若略去所有边的方向后若略去所有边的方向后所得无向图中含子图所得无向图中含子图Kn, 则则D中有哈密顿通路中有哈密顿通路.29应用例例4 有有7个人个人, A会讲英语会讲英语, B会讲英语和汉语会讲英语和汉语, C会讲英语、会讲英语、意大利语和俄语意大利语和俄语