发布时间 : 星期一 文章四川大学离散数学（冯伟森版）课后习题答案习题参考解答（图论部分）更新完毕开始阅读
去找 http://www.7zhao.net
解：当n为大于2的奇数时，无向完全图Kn是欧拉图，因为每个节点的度数为偶数。当n为2时，K2，是唯一存在两个奇度点的完全图，因此此图只存在欧拉道路■
8. n（n≥2）个结点的有向完全图中，哪些是欧拉图？
解：n（n≥2）个结点的有向完全图中，每个都是欧拉图，因为每个节点都有相同的入度和出度，可以找到有向欧拉回路■ 9. 证明:凡有割点的图都不是哈密顿图。 证明：反证法，假设存在有割点v的图是哈密顿图，那么此图存在哈密顿圈。在此圈中删除割点v，那么剩下的节点依然连通。这和割点的定义相矛盾，所以题设命题成立■ 10. 证明: 4k+l阶的所有2k正则简单图都是哈密顿图。 证明：因为图是的正则简单图，因此对任意的u，v∈V, 有d(u) + d(v) = 4k. 根据定理13.4，存在哈密顿道路P= v1v2…v4k+1. 1）如果 v1v4k+1∈E, 则v1v2…v4k+1v1构成一个H圈； 2）如果v1v4k+1E，则是v1的邻接点，那么必为v4k+1的邻接点。否则，v4k+1点度为4k-1-2k=2k-1,与题设矛盾。假设vit-1v4k+1∈E，那么可构造H圈如下：v1…vit-1v4k+1 v4k…vitv1 因此，此图为哈密顿图■ 11．在无向完全图Kn中有多少条没有公共边的哈密尔顿回路？ 解：1) 设n=2k+1,将节点编号为0,1,2…2k,并作如下图示， 1 2k 2k-1 2k-2 0 2 3 4 K+3 K+2 K+1 k
在上图中先取一条哈密顿回路为0,1,2,2k,3,2k-1,4,…k+3,k,k+2,k+1,0,然后将圆周上的结点按逆时针方向依次转动一个位置，然后可以得到另一条回路为：0,2,3,1,4,2k,5,…k+4,k+1,k+3,k+2,0;显然，这两条回路是没有公共边。继续这样做下去，共可产生条无公共边的哈密顿回路。
25
去找 http://www.7zhao.net 若n=2k+2,那么只要在中间增加一个结点ｕ，就可以同样地得到条无公共边的哈密顿回路■
12. 11个学生打算几天都在一张圆桌上共进午餐，并且希望每次午餐时每个学生两旁所坐的人都不相同，问11人共进午餐最多能有多少天？
解：将１１个学生分别用结点表示，由于每个同学都可能邻座，因此每两个结点之间都有一条边，因此得到无向完全图Ｋ１１，每次午餐时学生都按照一条哈密顿回路落座，如果两条哈密顿回路有公共边，则公共边端点所代表的学生就是相邻的。因此上述问题转化为求Ｋ１１有多少条无公共边的哈密顿回路问题，利用１１题的结论，共有(11-1)/2=5条无公共边的哈密顿回路，因此这１１个学生共进午餐最多能有５天■
13. 假定在n个人的团体中,任何2人合起来认识其余的n-2个人。证明:
(1)这n个人可以排成一排,使得站在中间的每个人的两旁都是自己认识的人,站在两端的人旁边各有1个认识的人；
(2)当月时,这n个人可以围成一个圆圈,使得每个人两旁都是自己所认识的人。
证明：因为任意两个人加起来认识其余的ｎ－２个人，那么每个人至少认识n-2个人。否则，设ｖ不认识ｕ，ｔ两人，那么ｕ和ｔ两个人将不能认识完剩下的ｎ－２个人，矛盾。当ｎ≥3时，将n个人看成图的结点，相互认识则在相关两个结点间有一条边，构成一个简单无向图G。此图中，任何两个结点的点度之和 d(u)+d(v)≥2(n-2)≥n-1,因此存在哈密顿道路，即这n个人可以排成一排,使得站在中间的每个人的两旁都是自己认识的人,站在两端的人旁边各有1个认识的人；
当n≥4, 任何两个结点的点度之和 d(u)+d(v)≥2(n-2)≥n,因此图中存在哈密顿回路，即这n个人可以围成一个圆圈,使得每个人两旁都是自己所认识的人■
14. 设G是(n, m)简单图。若 ,证明G必是哈密顿图。
证明：假设此图中存在两个点v,u 其点度之和d(v)+d(u)≤n-1,那么剩余n-2个结点的点度之和最大值为(n-2)(n-3) + n-1,那么整个图的最大点度之和为(n-2)(n-3)+n-1+n-1=n2-3n+4,但根据题设条件，点度之和Σd(u) = 2m ≥n2-3n+6.矛盾，因此任意两结点点度之和d(v)+d(u)≥n，因此图G必是哈密顿图■
15. 用两种以上的办法判别图13.11不是哈密顿图。 解：
方法1 ：删点法，如下
26
去找 http://www.7zhao.net 删除任何结点之前的原图 删除黑色结点之后 由上图可知，删除7个黑色点后，此图变成为具有9个分支的子图，根据哈密顿图的必要性判定定理ω(G-S)≤|S|可知，此图不是哈密顿图。 方法2：根据平面哈密顿图的面度公式：此图只有4度面，因此如果是哈图，则必须满足其中，代表内部面数，代表外部面数。但是，面的总数是13，无论如何不能成立，因此不是哈密顿图■ 16. 证明:图13.12中不存在同时包含边e1和e2的哈密顿图。（请冯老师帮忙证明下） 17. 对于下面给出的权阵,试用分枝定界法求对应的最优哈密顿圈。 解：略，请参考教材的算法实例■ 27