习题十三
1、构造(n,m)欧拉图，使其满足条件：（1）m,n奇偶性相同；（2）m,n奇偶性相反
答：略
2、设G=（V，E）是一个具有2k(k>0)个奇数度结点的连通图。证明：G中必存在k条边不相重的简单道路P1,P2,…,Pk, 使得E=E(P1) ?E(P2) ?… ?E(Pk)
证明：把2k个奇数度结点分成两两一组的k组，然后每组结点新加一条边，所得图为欧拉图，故存在欧拉回路C；然后去掉欧拉回路C中的k条新加入的边，得到k条互无重复边的道路P1,P2,…,Pk, 即为所求
5、在图13-10中求中国邮递员问题的解 解：
v1 2 v5 v10 6 5 4 3 v6 1 v7 1 v8 4 v3
3 v2 2 v11 3 1 v9 5 2 1 1 v4 如上图标号：
图中有4个奇数度结点v1,v6,v9,v3, 求两两之间最短长度： Pv1v6=3 (v1v6), Pv1v9=7 (v1v2v3v4v9), Pv1v3=4 (v1v2v3), Pv6v9=7 (v6v7v8v9), Pv3v6=6 (v3v8v7v6), Pv3v9=3 (v3v4v9), Pv1v6和Pv3v9满足最小性要求，
复制v1v6和v3v4v9的边，图中欧拉回路即为所求解
6、设G是有两个奇数度点的连通图，设计一个构造G的欧拉道路的算法
解：此算法只要在书中欧拉回路的算法中，添加起点为奇数结点即可，详细描述略
9、证明：凡有割点的图都不是哈密顿图
证明：假设e为图G的割点，根据割点的定义，ω(G-e) > 1，因此不满足哈图的必要条件；所以不是哈图
13、假定在n(>2)个人的团体中，任何2人合起来认识其余的n-2个人，证明：
（1）这n个人可以排成一排，使得站在中间的每个人的两旁都是自己认识的人，站在两端的人旁边各有1个认识的人
（2）当n≥4时，这n个人可以围成一个圆圈，使得每个人两旁都是自己所认识的人
证明：如果团体中的个人看成是结点，而人于人的关系看成是边，那么就构成一个认识与否的图，对于问题（1），就转化为此图中存在哈道路问题；问题（2），就转化为图中存在哈圈的问题，现说明如下： 在此题中，任何2人合起来认识其余的n-2个人蕴含任何人最多只有一人不认识，因为如果a，不认识b和c,那么b和c就不能认识完剩下的全部人，因此此图既有d(u) ≥ n-2 那么，任意两个结点u,v，d(u) + d(v) ≥ n-2 + n -2，因为n>2，所以d(u) + d(v) ≥ n-1，根据书中定理，此图存在哈道路
如果n≥4，那么d(u) + d(v) ≥ n-2 + n -2 ≥ n，根据书中定理，此图存在哈圈