loading第8 章 习题解答
8.1 图8.6 中,(1)所示的图为K1,3,(2) 所示的图为K2,3,(3)所示的图为
K2,2,它们分别各有不同的同构形式.
8.2 若G为零图,用一种颜色就够了,若G是非零图的二部图,用两种颜色就够了.
分析 根据二部图的定义可知,n阶零图(无边的图)是三部图(含平凡图),对n阶零图的每个顶点都用同一种颜色染色,因为无边,所以,不会出现相邻顶点染同色,因而一种颜色就够用了.
8.3 完全二部图Kr,s,中的边数m?rs.
分析 设完全二部图Kr,s的顶点集为V, 则V?V1?V2,V1?V2??,且
|V1|?r,|V2|?s,Kr,s是简单图,且V1中每个顶点与V2中所有顶点相邻,而且V1中任何两个不同顶点关联的边互不相同,所以,边数m?rs.
8.4 完全二部图Kr,s中匹配数?1?min{r,s},即?1等于r,s中的小者. 分析 不妨设r?s,且二部图Kr,s中,|V1|?r,|V2|?s,由Hall定理可知,图中存在V1到的完备匹配,设M为一个完备匹配,则V1中顶点全为M饱和点,所以,?1?r.
8.5 能安排多种方案,使每个工人去完成一项他们各自能胜任的任务.
甲,乙,丙},则V1为工人集合, V2?{a,b,c},则V2为任务集合.分析 设V1?{令V?V1?V2,E?{(x,y)|x能胜任y},得无向图G??V,E?,则G为二部图,见图8.7 所示.本题是求图中完美匹配问题. 给图中一个完美匹配就对应一个分配方案.图8.7 满足Hall定理中的相异性条件,所以,存在完备匹配,又因为|V1|?|V2|?3,所以,完备匹配也为完美匹配.其实,从图上,可以找到多个完美匹配. 取
M1?{(甲,a),(乙,b),(丙,c)}
此匹配对应的方案为甲完成a,乙完成b, 丙完成c,见图中粗边所示的匹配.
M?{(甲,b),(乙,a),(丙,c)}
M2对应的分配方案为甲完成b,乙完成a,丙完成c. 请读者再找出其余的分配方案.
8.6 本题的答案太多,如果不限定画出的图为简单图,非常容易地给出4族图分别满足要求.
(1) n (n 为偶数,且n?2)阶圈都是偶数个顶点,偶数条边的欧拉图. (2) n (n 为奇数,且n?1)阶圈都是奇数个顶点,奇数条边的欧拉图. (3) 在(1) 中的圈上任选一个顶点,在此顶点处加一个环,所务图为奇数个顶点,偶数条边的欧拉图.
分析 上面给出的4族图都是连通的,并且所有顶点的度数都是偶数,所以,都是欧拉图.并且(1),(2) 中的图都是简单图.而(3),(4)中的图都带环,因而都是非简单图. 于是,如果要求所给出的图必须是简单图,则(3),(4)中的图不满足要求.
其实,欧拉图是若干个边不重的图的并,由这种性质,同样可以得到满足(3),(4)中要求的简单欧拉图.设G1,G2,?,Gk是长度大于等于3的k个奇圈(长度为奇数的圈称为奇圈),其中k为偶数,将G1中某个顶点与G2中的某顶点重合,但边不重合, G2中某顶点与G3中某顶点重合,但边不重合,继续地,最后将Gk?1中某顶点与Gk中某顶点重合,边不重合,设最后得连通图为G,则G中有奇数个顶点,偶数条边,且所有顶点度数均为偶数,所以,这样的一族图满足(4)的要求,其中一
个特例为图8.8中(1)所示.在以上各图中,若G1,G2,?,Gk中有一个偶圈,其他条件不变,构造方法同上,则所得图G为偶数个顶点,奇数条边的简单欧拉图,满足(3)的要求,图8.8中(2)所示为一个特殊的情况.
8.7 本题的讨论类似于8.6题,只是将所有无向圈全变成有向圈即可,请读者自己画出满足要求的一些特殊有向欧拉图.
8.8 本题的答案也是很多的,这里给出满足要求的最简单一些图案,而且全为简单图.
(1) n(n?3)阶圈,它们都是欧拉图,又都是哈密尔顿图.
(2) 给定k(k?2)个长度大于等于3的初级回路,即圈G1,G2,?,Gk,用8.6题方法构造的图G均为欧拉图,但都不是哈密尔顿图,图8.8给出的两个图是这里的特例.
(3)n(n?4)阶圈中,找两个不相邻的顶点,在它们之间加一条边,所得图均为哈密尔顿图,但都不是欧拉图.
(4) 在(2)中的图中,设存在长度大于等于4的圈,比如说G1,在G1中找两个不相邻的相邻顶点,在它们之间加一条新边,然后用8.6题方法构造图G,则G既不是欧拉图,也不是哈密尔顿图,见图8.9所示的图.
分析 (1) 中图满足要求是显然的.(2)
中构造的图G是连通的,并且各顶点度数均为偶数,所以,都是欧拉图,但因为G中存在割点,将割点从G中删除,所得图至少有两个连通分支,这破坏了哈密尔顿图的必要条件,所以,G不是哈密尔顿图.(3) 中构造的图中,所有顶点都排在一个圈上,所以,图中存在哈密尔顿回路,因而为哈密尔顿图,但因图中有奇度顶点(度数为奇数的顶点),所以,不是欧拉图. 由以上讨论可知,(4) 中图既不是欧拉
图,也不是哈密尔顿图.
其实,读者可以找许多族图,分别满足题中的要求. 8.9 请读者自己讨论. 8.10 其逆命题不真.
分析 若D是强连通的有向图,则D中任何两个顶点都是相互可达的,但并没有要求D中每个顶点的入度都等于出度. 在图8.2 所示的3个强连通的有向衅都不是欧拉图.
8.11 除K2不是哈密尔顿图之外, Kn(n?3)全是哈密尔顿图. Kn(n为奇数)为欧拉图. 规定K1(平凡图)既是欧拉图,又是哈密尔顿图.
分析 从哈密尔顿图的定义不难看出,n阶图G是否为哈密尔顿图,就看是否能将G中的所有顶点排在G中的一个长为n的初级回路,即圈上. Kn(n?3)中存在多个这样的生成圈(含所有顶点的图), 所以Kn(n?3)都是哈密尔顿图.
在完全图Kn中,各顶点的度数均为n-1,若Kn为欧拉图,则必有n?1为偶数,即n为奇数,于是,当n为奇数时, Kn连通且无度顶点,所以, Kn(n为奇数) 都是欧拉图.当n为偶数时,各顶点的度数均为奇数,当然不是欧拉图.
8.12 有割点的图也可以为欧拉图.
分析 无向图G为欧拉图当且仅当G连通且没有奇度顶点.只要G连通且无奇度顶点(割点的度数也为偶数),G就是欧拉图.图8.8所示的两个图都有割点,但它们都是欧拉图.
. 8.13 将7个人排座在圆桌周围,其排法为abdfgeca分析 做无向图G??V,E?,其中,
V?{a,b,c,d,e,f,g}
E?{(u,v)|u,v?V且u与v有共同语言}
图G为图8.10所示.图G是连通图,于是,能否将这7个人排座在圆桌周围,使得每个人能与两边的人交谈,就转化成了图G中是否存在哈密尔顿回路(也就是G是否为哈密尔顿图).通过观察发现G中存在哈密尔顿回路, abdfgeca就是其