【#文档大全网# 导语】以下是®文档大全网的小编为您整理的《哈密尔顿图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(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.wddqxz.cn/83fc6666453610661fd9f422.html