哈密尔顿图2

《哈密尔顿图》课后作业及解答

作业及解答详见以下参考书：

[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(n?3)阶圈,它们都是欧拉图,又都是哈密尔顿图.

G,G,?,Gk(2) 给定k(k?2)个长度大于等于3的初级回路,即圈12,用8.6题方法构

造的图G均为欧拉图,但都不是哈密尔顿图,图8.8给出的两个图是这里的特例.

(3)n(n?4)阶圈中,找两个不相邻的顶点,在它们之间加一条边,所得图均为哈密尔顿图,但都不是欧拉图.

(4) 在(2)中的图中,设存在长度大于等于4的圈,比如说G1,在G1中找两个不相邻的

1

顶点,在它们之间加一条新边,然后用8.6题方法构造图G,则G既不是欧拉图,也不是哈密尔顿图,见图8.9所示的图.

8.9 本题的讨论类似于第1题,只是将所有无向圈全变成有向圈即可. 8.11 除K2不是哈密尔顿图之外,

Knn?3K()全是哈密尔顿图. n(n为奇数)为欧拉图.

规定K1(平凡图)既是欧拉图,又是哈密尔顿图.

分析 从哈密尔顿图的定义不难看出,n阶图G是否为哈密尔顿图,就看是否能将G中的所有顶点排在G中的一个长为n的初级回路,即圈上. (含所有顶点的图), 所以

在完全图

Knn?3()中存在多个这样的生成圈

Knn?3()都是哈密尔顿图.

Kn为欧拉图,则必有n?1为偶数,即n为奇

Kn中,各顶点的度数均为n-1,若

数,于是,当n为奇数时,

Kn连通且无度顶点,所以,

Knn(为奇数) 都是欧拉图.当n为偶

数时,各顶点的度数均为奇数,当然不是欧拉图.

8.13 解：设7个人为7个结点, 将两个懂同一语言的人之间连一条边(即他们能直接交谈),即作无向图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中存在哈密尔顿回路, abdfgeca就是其中的一条哈密尔顿回路.

2

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库哈密尔顿图2在线全文阅读。