第10章 特殊图last

《离散数学教程》教案与习题解析理工学院段景辉1第10章特殊图10.1欧拉图与哈密顿图10.1.1欧拉图及欧拉路径定义10.1图G称为欧拉图(Eulergraph)，如果图G上有一条经过G的所有顶点、所有边的闭路径，或图G为一个孤立顶点。图G称为欧拉路径(Eulerwalk)，如果图G上有一条起始于一个顶点，经过G所有顶点、所有边而终止于另一顶点的路径。定理10.1无向图G为欧拉图当且仅当G连通，并且所有顶点的度都是偶数。有向图G为欧拉图，当且仅当G是弱连通的，并且每个顶点的出度与入度相等。定理10.2无向图G为欧拉路径，当且仅当G连通，并且恰有两个顶点的度是奇数。有向图G为欧拉路径，当且仅当G连通，并且恰有两个顶点的入度与出度不等，它们中一个的出度比入度多1，另一个入度比出度多l。10.1.2哈密顿图及哈密顿通路定义10.2如果无向图G上有一条经过所有顶点的回路，或图G为一个孤立顶点，那么，称图G为哈密顿图(Hamiltongraph)，（也称这一回路为哈密顿回路）。如果无向图G上有一条起始于一个顶点，经过G所有顶点而终止于另一顶点的通路，那么，称图G上有哈密顿通路(Hamiltonpath)。定理10.3设图G为具有n（n≥3）个顶点的简单无向图，如果G的每一对顶点的度数之和都不小于n–1，那么G中有一条哈密顿通路；如果G的每一对顶点的度数之和不小于n，那么G为一哈密顿图。定理10.4当n为不小于3的奇数时，Kn上恰有(1)!2n条互不相同的哈密顿回路；恰有21n条互相均无公共边的哈密顿回路。定义10.3如果可以用两种颜色对图G的所有顶点着色，每个顶点着一种颜色，并且使得相邻的顶点着不同的颜色，那么，称图G是可2-着色的。定理10.5设图G是可2-着色的。如果G是哈密顿图，那么着两种颜色的顶点数目相等；如果G有哈密顿通路，那么着两种颜色的顶点数目之差至多为一。定理10.5只指出了哈密顿图和哈密顿通路存在的必要条件，它并不充分，很容易作出可2-着色且两种颜色顶点数目相等的图，它却不是哈密顿图。定理10.5用来判定某些图不是哈密顿图或没有哈密顿通路是方便的，但是，它要求图是可2-着色的，这并不是任何图都能满足的。当一个图不可2-着色时，可以在二度顶点所关联的边上添加顶点，使图可以《离散数学教程》教案与习题解析理工学院段景辉2二着色。练习10.11、选择题（1）欧拉图是（）A、路径B、闭路径C、回路D、通路【答案】：B（2）哈密尔顿图是（）A、路径B、闭路径C、回路D、三者都不是【答案】：C（3）设G=(n,m)是欧拉图，则n,m有关系（）A、n=mB、n,m的奇偶性必相同C、n,m的奇偶性必相反D、n,m的奇偶性既可相同也可相反【答案】：D2、填空题（1）无向图G有一条欧拉路径，当且仅当。【答案】：G连通且恰有零个或两个奇数度节点。（2）当n为时，Kn必为欧拉图。【答案】：奇数（3）当n为时，Kn必为哈密尔顿图。【答案】：大于2的整数（4）当n为时，n个顶点的树必非欧拉图和哈密尔顿图。【答案】：大于1的整数3、“蚂蚁赛跑问题”：图10.1中，在结点v2，v3上的两只蚂蚁跑过图的所有边（至少一次）到达目标v4，谁花费的时间多？（假设蚂蚁通过每一条边所花费时间相同）。《离散数学教程》教案与习题解析理工学院段景辉3图10.1【答案】：解.结点v2上的蚂蚁花费的时间多。根据定理10.2，图10.13有一条v3到v4的欧拉路径，即由v3到v4有一条经过图中的每条边一次且仅一次的路径；而要想找一条从v2到v4且经过每条边的拟路径，必有边重复。所以由v3到v4只需经过9条边，从v2到v4所经过的边数必多于9条。4、试作出四个图的图示，使第一个既为欧拉图又为哈密顿图；第二个是欧拉图而非哈密顿图；第三个是哈密顿图却非欧拉图；第四个既非欧拉图也非哈密顿图。【答案】：解.图10.2(a)既为欧拉图又为哈密顿图；(b)是欧拉图而非哈密顿图；(c)是哈密顿图却非欧拉图；(d)既非欧拉图也非哈密顿图。图10.25、像第4题要求的那样对欧拉路径和哈密顿通路作出四个图。【答案】：解.图10.3(a)既有欧拉路径又有哈密顿通路；(b)有欧拉路径而无哈密顿通路；(c)有哈密顿通路却无欧拉路径；(d)既无欧拉路径也无哈密顿通路。图10.3v1v4v5v2v3(a)(b)(c)(d)（a）(b)(c)(d)《离散数学教程》教案与习题解析理工学院段景辉46、问n为何种数值时，Kn既是欧拉图又是哈密顿图。问k为何值时，k-正则图既是欧拉图又是哈密顿图。【答案】：解.n为奇数时，Kn既是欧拉图又是哈密顿图。k为大于或等于n/2的偶数时，k-正则图既是欧拉图又是哈密顿图。7、证明：恰有两个奇数度顶点u,v的无向图G是连通的,当且仅当在G上添加边(u,v)后所得的图G*是连通的。【答案】：证.必要性是显然的。设G*是恰有两个奇数度顶点u,v的无向图G添加边（u，v）后所得，且是连通的,那么图G*是一个欧拉图（每一个顶点都是偶数度的连通图），因此G*中删除边（u，v）后所得的图G仍是连通的。8、十一个学生在一张圆桌旁共进晚餐，要求在每次晚餐上每个学生的邻座都与其它各次晚餐的邻座不同。问这样共进晚餐能安排多少次。【答案】：解.每次晚餐上每个学生的邻座都与其它各次晚餐的邻座不同的安排方式有21n种（根据定理10.4。）9、判别图10.4中各图是否为哈密顿图，若否，请说明理由，并回答它是否有哈密顿通路。(a)(b)(c)图10.4【答案】：解.(a)是哈密顿图。(b)不是哈密顿图，有哈密顿通路，给(b)做如图(d)所示的二着色，两种颜色的顶点数目不等，根据定理10.5，(b)不是哈密顿图，但能找到一条哈密顿通路；(c)不是哈密顿图，也没有哈密顿通路，给(c)做如下图(e)所示的二着色，两种颜色的顶点数目不等，且两种颜色顶点数目之差大于1，根据定理10.5，(c)不是哈密顿图，也不存在哈密顿通路。《离散数学教程》教案与习题解析理工学院段景辉5(d)(e)图10.410、证明：对哈密顿图G=V，E删除S（V）中的所有顶点后，所得图G’的连通分支数不大于S。【答案】：证.设G1是G中的哈密顿回路，显然在G1中删除S（V）中的所有顶点后，所得图G1’的连通分支数k1，不小于在G中删除S（V）中的所有顶点后，所得图G’的连通分支数k，即k≤k1。由于G1是一条回路，在G1中删除S（V）中的所有顶点后，所得图G1’的连通分支数k1不大于S是显然的，即k1≤S。因此k≤k1≤S11、设G为(n，m)图。证明：如果221nCm，那么G为哈密顿图（提示：运用定理10.3）。【答案】：证.设G中有两个顶点v1和v2的度数之和不大于n–1，那么以v1和v2为端点的边不多于n–1条。而其余顶点之间的边的数目不多于2)3)(2(nn条。故G的总边数m满足11)2)(1(21)43(21)6522(21)3)(2(2112122nCnnnnnnnnnnm与221nCm矛盾，故G中任意两个顶点的度数之和大于n。根据定理10.3，G为哈密顿图。《离散数学教程》教案与习题解析理工学院段景辉612、设有n（n为偶数）个围成一圈跳舞的孩子，每个孩子都至少与其中2n个是朋友。试证明，总可安排得使每个孩子的两边都是他的朋友。【答案】：证.设n个孩子为n个顶点，用边表示顶点间的朋友关系构成一个图G。由于每个孩子都至少与其中2n个是朋友，因此G的每一顶点的度数至少是2n，从而G的任何两个顶点的度数之和至少是n。根据定理10.3，G为哈密顿图。即G有哈密顿回路，这表明，总可安排n个孩子围成一圈跳舞，使每个孩子的两边都是他的朋友。13、有N张卡片，每个卡片上写着一个仅由小写字母组成的英文单词。若需要给这些卡片按照合适的顺序排成一行，使得相邻两个卡片中，前一个卡片上的单词的末位字母等于后一个卡片上的单词的首字母。请你回答：应如何判断这N张卡片不能达到这个要求？【答案】：按照以下方法做图G，以每张卡片为顶点，单词首尾相同的卡片间画一条有向边。要判断这N张卡片能否达到要求，就是判断图G中是否存在一条哈密顿通路，可以尝试给G二着色，如果两种颜色的顶点数目相差大于1，则这N张卡片一定达不到要求。14、（1）邮递员所管辖的街道如图10.5(a)所示，若投递邮件时他必须走遍所辖各街道中每一条街至少一次，最后返回邮局。计算他的投递路线的长度。（2）设想用当代速度最快的计算机求解100个城镇的货郎担问题需要多长时间【答案】：（1）根据中国邮路问题，由图10.5(a)得图10.5(b)，图10.5(b)所有顶点的度数都是偶数，它是一个欧拉图，所以邮递员只需走过每条街道一次即可返回邮局，即他的投递路线长度是这些边的权值和22。（2）100个城镇的哈密顿回路的个数是2)!1100(≈9.3*1015，每条回路上要进行100次加法运算，共需加法运算次数约9.3*1017次。以美国劳伦斯-利弗摩尔国家实验室的蓝色基因/L计算机（由131072颗处理器组成，运算速度达到每秒280.6×1012次浮点运算）为例，算出所有回路的长度约需时间3300秒，将近一小时。然后再对这些回路做排序，假设使用快速排序算法，最好情况下算法时间复杂度为O(nlog2n)，这里n为哈密顿回路的数量。所以还需要时间15152129.310log(9.310)1745280.610秒，约半小时。《离散数学教程》教案与习题解析理工学院段景辉7(a)(b)图10.510.2二分图10.2.1二分图基本概念定义10.4无向图G=V，E称为二分图(bipartitegraph)，如果有非空集合X，Y使X∪Y=V，X∩Y=，且对每一eE，都有e={x,y}，xX，yY。此时常用X，E，Y表示二分图G。若对X中任一x及Y中任一y恰有一边eE，使e={x,y},则称G为完全二分图(completebipartitegraph)。当X=m，Y=n时，完全二分图G记为Km,n。定理10.6无向图G为二分图的充分必要条件是，G至少有两个顶点,且其所有回路的长度均为偶数。10.2.2二分图的匹配及其应用定义10.5设G=X,E,Y为二分图，ME，如果M中任何两条边都没有公共端点，那么，称M为G的一个匹配(matching)，。M=时称M为空匹配。G的所有匹配中边数最多的匹配称为最大匹配(maximalmatching)。如果X(Y)中任一顶点均为匹配M中边的端点，那么称M为X(Y)-完全匹配(X(Y)-perfectmatching)。若M既是X-完全匹配又是Y-完全匹配，则称M为G的完全匹配(perfectmatching)。定义10.6设G=X,E,Y，M为G的一个匹配。（1）M中边的端点称为M-顶点，其它顶点称为非M-顶点。（2）G中vk到vl的通路P称为交替链，如果P的起点vk和终点vl为非M-顶点，而其边的序列中非匹配边与匹配边交替出现（从而首尾两边必为非匹配边，除顶点vk，vl以外各顶点均为M-顶点）。特别地，当一边{v,v'}两端点均为非M-顶点，通路{v,v'}亦称为交替链。把G中任一匹配M扩充为最大匹配的匈牙利算法：（1）首先用（*）标记X中所有的非M-顶点，然后交替进行步骤（2），（3）。（2）选取一个刚标记（用（*）或在步骤（3）中用（yi）标记）过的X中顶点，例如顶点xi，如果xi与y为同一非匹配边的两端点，且在本步骤中y尚未被标记过，那么用（xi）去标记Y中顶点y。否则，重新选取另一个标记过的顶点重复步骤（2），直至对标记过的Xxyzwxyzw12uuuvuv2《离散数学教程》教案与习题解析理工学院段景辉8中顶点全部尝试完毕。（3）选取一个刚标记（在步骤（2）中用（xi）标记）过的Y中结点，例如yi，如果yi与x为同一匹配边的两端点，且在本步骤中x尚未被标记过，那么用（yi）去标记X中结点x。否则，重新选取另一个标记过的顶点重复步骤