《哈密尔顿图》课后作业及解答 作业及解答详见以下参考书： [1]《离散数学》(第四版)，耿素云等编著，北京大学出版社，2008. [2]《离散数学题解》,屈婉玲等编著，清华大学出版社. 课后作业： 8.8 画一个无向图，使它 (1) 具有欧拉回路和哈密尔顿回路， (2) 具有欧拉回路而没有哈密尔顿回路， (3) 具有哈密尔顿回路而没有欧拉回路， (4) 既没有欧拉回路，也没有哈密尔顿回路。 8.9画一个有向图，使它 (1) 具有欧拉回路和哈密尔顿回路， (2) 具有欧拉回路而没有哈密尔顿回路， (3) 具有哈密尔顿回路而没有欧拉回路， (4) 既没有欧拉回路，也没有哈密尔顿回路。 8.11 在什么条件下kn(n>1)是哈密尔顿图? 在什么条件下是欧拉图? 8.12 今有a, b, c, d, e, f, g 七个人，已知以下事实：a：会说英语；b：会说英语或西班牙语；c；会说英语，意大利语和俄语；d：会说日语和西班牙语；e：会说德语和意大利语；f：会说法语、日语和俄语；g：会说法语和德语.试问：试问这七个人应如何排座位，才能使每个人都能和他身边的两个人交谈？ 作业解答： 8.8 本题的答案很多,这里给出一些满足要求的简单图. (1) n(n3)阶圈,它们都是欧拉图,又都是哈密尔顿图. G,G,,Gk(2) 给定k(k2)个长度大于等于3的初级回路,即圈12,用8.6题方法构造的图G均为欧拉图,但都不是哈密尔顿图,图8.8给出的两个图是这里的特例. (3)n(n4)阶圈中,找两个不相邻的顶点,在它们之间加一条边,所得图均为哈密尔顿图,但都不是欧拉图. (4) 在(2)中的图中,设存在长度大于等于4的圈,比如说G1,在G1中找两个不相邻的 1 顶点,在它们之间加一条新边,然后用8.6题方法构造图G,则G既不是欧拉图,也不是哈密尔顿图,见图8.9所示的图. 8.9 本题的讨论类似于第1题,只是将所有无向圈全变成有向圈即可. 8.11 除K2不是哈密尔顿图之外, Knn3K()全是哈密尔顿图. n(n为奇数)为欧拉图. 规定K1(平凡图)既是欧拉图,又是哈密尔顿图. 分析 从哈密尔顿图的定义不难看出,n阶图G是否为哈密尔顿图,就看是否能将G中的所有顶点排在G中的一个长为n的初级回路,即圈上. (含所有顶点的图), 所以在完全图Knn3()中存在多个这样的生成圈Knn3()都是哈密尔顿图. Kn为欧拉图,则必有n1为偶数,即n为奇Kn中,各顶点的度数均为n-1,若数,于是,当n为奇数时, Kn连通且无度顶点,所以, Knn(为奇数) 都是欧拉图.当n为偶数时,各顶点的度数均为奇数,当然不是欧拉图. 8.13 解：设7个人为7个结点, 将两个懂同一语言的人之间连一条边(即他们能直接交谈),即作无向图GV,E,其中V{a,b,c,d,e,f,g}，E{(u,v)|u,vV且u与v有共同语言}，得到的简单图G如图8.10所示。G是连通图，故能否将这7个人排座在圆桌周围,使得每个人能与两边的人交谈,就转化成了图G中是否存在哈密尔顿回路.通过观察发现G中存在哈密尔顿回路, abdfgeca就是其中的一条哈密尔顿回路. 2 本文来源：https://www.wddqw.com/doc/83fc6666453610661fd9f422.html