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