《6-2-特殊的图PPT》由会员分享，可在线阅读，更多相关《6-2-特殊的图PPT（34页珍藏版）》请在金锄头文库上搜索。
1、请交作业五,作业讲评四,P115 4.13,S=a,b,c,d R1=, R2 =, R1 R2= R2 R1=, R12=R1 R1=, R23=R22 R2 =, R2 =,P116 4.16,哈斯图,极小元、最小元,极大元、最大元,补充题,若 R、S是对称的，给出 R S 不是对称的例子。 R=, S=, R S= 若 R、S是反自反的，给出 R S 不是反自反的例子。 R=，S= R S=,第6章 特殊的图,6.1 二部图 6.2 欧拉图 6.3 哈密顿图 6.4 平面图,哥尼斯堡七桥问题,哥尼斯堡城有一条横贯全市的河，河中有两个小岛，用七座桥将岛和岛、河岸和岛连接起来。 18世纪中叶
2、，人们提出了问题：能否不重复的走完七桥，最后回到原地。很多人试图解决这个问题，但都失败。 1736年欧拉发表了哥尼斯堡七桥问题，它的基本内容就是定理“无向图G为欧拉图当且仅当G连通且无奇度顶点.”的证明，论文首次论证了这个问题无解。 问题等价于图中存在一条回路，经过每一条边一次且仅一次，即图中存在欧拉回路。,应用实例,设旋转磁鼓分成8个扇区, 每个扇区标记一个0或1, 有3个探测器能够读出连续的3个扇区的标记. 如何赋给扇区标记, 使得能够根据探测器的读数确定磁鼓的位置. 为了能够根据读数确定磁鼓的位置, 必须构造一个由8个0和1组成的圆环, 使得圆环上连续3个数字的序列都不相同.,1 1 0
3、 1 1 0 1 0 1 1,应用实例(续),构造一个4阶有向图, 8条边 的标记是不同的, 图中存在一条欧拉回路: 000, 001, 011, 111, 110, 101, 010, 100. 顺着这条回路取每一条边标记的 第一位得到00011101, 按照这个顺序标记磁鼓的扇区.,哈密顿周游世界问题,1859年，数学家哈密顿发明了一个周游世界的游戏：在一个实心的正十二面体，每面是一个正五边形。共计20个顶点标上世界著名大城市的名字，要求游戏者从某一城市出发，遍历各城市一次，最后回到原地。 周游世界问题即找一条经过所有顶点(城市)的回路。,6.3 哈密顿图,哈密顿回路: 经过图中所有顶点一
4、次且仅一次的回路. 哈密顿图: 具有哈密顿回路的图. 哈密顿通路: 经过图中所有顶点一次且仅一次的通路. 半哈密顿图: 具有哈密顿通路而无哈密顿回路的图. 几点说明： 平凡图是哈密顿图. 哈密顿回路是初级回路. 哈密顿通路是初级通路， 环与平行边不影响图的哈密顿性.,下列图中哪些是哈密顿图？半哈密顿图?,(1) 是哈密顿图; (2) 是哈密顿图; (3) 是半哈密顿图. (4) 既不是哈密顿图, 也不是半哈密顿图.,无向哈密顿图的一个必要条件,定理：设无向图G=是哈密顿图, 则对V1V且V1, 均有 p(GV1)|V1|. 证：设C为G中任一条哈密顿回路, (1) 当 V1中顶点在C上均不相邻
5、时， p(CV1) = |V1| (2) 当 V1中顶点在C中有彼此相邻时， p(CV1) |V1| 所以，有p(CV1) |V1|. 又因为CG, 故 p(GV1) p(CV1) |V1|. 几点说明 定理中的条件是哈密顿图的必要条件, 但不是充分条件. 即满足此定理条件的图不一定是汉密尔顿图， 而不满足此定理条件的图一定不是汉密尔顿图。,无向哈密顿图的一个必要条件,由定理知, Kr,s当sr+1时不是哈密顿图. 当r2时, Kr,r 是哈密顿图, 而Kr,r+1 是半哈密顿图.,实例1,设G为n阶无向连通简单图, 若G中有割点或桥, 则G不是哈密顿图. 证: 设v为割点,删除结点v，图成为
6、不连通的，且至少有两个连通分支。 则p(Gv) 2 |v| = 1. 根据定理, G不是哈密顿图. (2) 如果G中有桥，则该桥的一个端点是割点。 可以归结为G中有割点的情况。 所以G也不是哈密尔顿图。,哈密顿图的必要条件： p(GV1)|V1|,实例2,下图为彼得森图。它满足定理的条件， 在删除任意一个或两个顶点，仍是连通的； 删除3个顶点，最多只能得到有两个连通分支的子图； 删除4个顶点，最多只能得到有3个连通分支的子图； 删除5个顶点，余下子图的顶点数都不大于5，故必不能有5个以上的连通分支数， 所以，满足p(G-S)|S| 。 但此图是典型的非哈密尔顿图。,哈密顿图的必要条件： p(G
7、V1)|V1|,无向哈密顿图的一个充分条件,定理 设G是n阶无向简单图, 若任意两个不相邻的顶点的度数之和大于等于n1, 则G中存在哈密顿通路. d(u) + d(v) n-1 (u, v 不相邻) 推论 当n3时, 若任意两个不相邻的顶点的度数之和大于等于n, 则G中存在哈密顿回路. d(u) + d(v) n (u, v 不相邻) 说明： 定理中的条件是存在哈密顿通路(回路)的充分条件, 但不是必要条件.,哈密顿通路(回路)的存在性,下图有6个结点，任意两个结点度数的和小于5，但图中存在一条哈密尔顿路。,下图也有6个结点，任意两个结点度数的和小于6，但图中存在一条哈密尔顿回路。,由定理,
8、当n3时, Kn均为哈密顿图. 判断某图是否为哈密顿图至今还是一个难题!,判断是否是哈密顿图的可行方法,观察出一条哈密顿回路 例如： 右图(周游世界问题)中 红边给出一条哈密顿回路, 故它 是哈密顿图。 满足充分条件 如 当n3时, Kn中两个顶点 u,v, 均有d(u)+d(v) = 2(n1) n, 所以Kn为哈密顿图. 不满足必要条件 如 Kr, r+1不满足 p(GV1)|V1|. 所以, 不是哈密顿图,判断是否是哈 密顿图的可行方法,例 44国际象棋盘上的跳马问题: 马是否能恰好经过每一个方格一次后回到原处? 解: 每个方格看作一个顶点, 2个顶点之间有边 当且仅当马可 从一个方格跳
9、到另一个方格, (x, y)(x1, y2) (x, y)(x2, y1) 得到16阶图G, 取V1=a, b, c, d, 则p(GV1)= 6 |V1|, 由定理得G中无哈密顿回路, 问题无解.,不满足必要条件,判断是否为哈密顿图是NP完全的,哈密顿通路(回路)的存在性判断,必定是哈密顿图,必定不是哈密顿图,不能确定是否是哈密顿图,n=5时,需要计算12个权值. n=25时,需要计算24!/23.11023个权值. 如果计算每个哈密顿回路权值需要1ns,共需1千万年才能全部算完,找到权值最小的哈密顿回路.,货郎担问题（旅行商问题）Traveling Salesman ProblemTSP,
10、一个货郎需要经过若干个城镇,然后回到出发点. 已知每两个城镇之间的距离,这个货郎应如何选择路线,经过每个城镇一次且仅一次,并且总的行程最短? 算法:求每一条哈回路的总权值,然后从中找出最小值. 对于n个顶点的完全图有(n-1)!条不同的哈回路.,需要计算(n-1)!/2个权值.,货郎担问题（旅行商问题）Traveling Salesman ProblemTSP,目前世界解决TSP问题的情况,应用实例1圆桌排座问题,某次国际会议8人参加，已知每人至少与其余7人中的4人有共同语言，问服务员能否将他们安排在同一张圆桌就座，使得每个人都能与两边的人交谈？ 解 ：作无向图G=, 其中 V=v|v为与会者
11、， E=(u,v) | u,vV, u与v有共同语言, 且uv. G为简单图. 根据条件, vV, d(v)4. 于是，u, vV, 有d(u)+d(v)8. 由定理可知G为哈密顿图. 服务员可在G中找一条哈密顿回路，按它的相邻关系安排座位即可. 哈密顿图的实质是能将图中所有的顶点排在同一个圈中,应用实例2竞赛图,竞赛图 任意两个顶点之间恰好有一条有向边. 在循环赛中, n个参赛队中的任意两个队比赛一次, 假设没有平局, 用有向图描述比赛结果: 顶点表示参赛队, A到B有一条边当且仅当A队胜B队. 定理 在n(n2)阶有向图D中, 如果所有有向边均用无向边代替, 所得无向图中含生成子图Kn,
12、则有向图D中存在哈密顿通路.,应用实例2竞赛图,根据定理, 竞赛图中一定有哈密顿通路, 当然也可能有哈密顿回路. 当没有哈密顿回路时, 通常只有一条哈密顿通路, 这条通路给出参赛队的惟一名次. 例如, CABD是一条哈密顿通路, 它没有哈密顿回路, 比赛结果是C第一, A第二B, C第三, D第四.,6.4 平面图引例1,在一块地上盖了3座房子，并且挖了3口井供3家主人使用， 这3家人后来相互成了冤家，决定修建各家通往3口井的小道，使他们在去3口井的途中不会相遇，你能否设计整个小道的路线，満足他们的要求？,平面图引例2,在许多实际问题中，往往会涉及图的可平面化问题，如： 电路设计经常要考虑布线
13、是否可以避免交叉以减少元件间的互感影响-单层印刷电路板布线问题; 为安全起见，建筑物的地下水管、煤气管、电缆线等不能交叉 ;,平面图和平面嵌入,定义 如果能将图G除顶点外边不相交地画在平面上, 则称G是平面图. 这个画出的无边相交的图称作G的平面嵌入. 没有平面嵌入的图称作非平面图.,完全图K3是平面图,完全图K4是平面图,K2,3是平面图,平面图和平面嵌入,设GG, 若G为平面图, 则G也是平面图; 设GG, 若G为非平面图, 则G也是非平面图. K5和K3,3是非平面图 Kn(n5), K3,n(n3)都是非平面图. 平行边与环不影响图的平面性.,K5,K3,3,平面图的面与次数,设G是一
14、个平面嵌入， G的面: 由G的边将平面划分成的每一个区域。 无限面(外部面): 面积无限的面, 用R0表示。 有限面(内部面): 面积有限的面, 用R1, R2, Rk表示。 面Ri的边界: 包围Ri的所有边构成的回路组。 面Ri的次数: Ri边界的长度，用deg(Ri)表示。 说明: 构成一个面的边界的回路组可能是初级回路、 简单回路, 也可能是复杂回路, 甚至还可能是 非连通的回路之并.,上图共有4个面： deg(R1)=1 deg(R2)=3 deg(R3)=2 deg(R0)=8,右图是左图的平面嵌入。 R3: 外部面(左图), 内部面(右图) R1: 内部面(左图),外部面(右图) 其实，在平面嵌入中可把任何面作为外部面.,平面图的面与次数,平面图的面与次数,定理 在一个平面图G中，所有面的次数之和等于边数m的2倍. 其中，r为面数。 说明 G中每条边无论作为两个面的公共边界，还是作为一个面的边界，在计算总的次数时都计算两次。,作业 18,P154： 8，10，15 P155：16，18 P156：27,
