内容发布更新时间 : 2024/11/17 5:27:14星期一 下面是文章的全部内容请认真阅读。
习题四: 欧拉图与汉密尔顿图
1．判定图7-4.15的图形是否能一笔画。
(a)
图7-4.15
(b)
2．构造一个欧拉图，其结点数v和边数e满足下述条件 a）v，e的奇偶性一样。 b）v，e的奇偶性相反。 如果不可能，说明原因。
3．确定n取怎样的值，完全图Kn有一条欧拉回路。
4．a）图7-4.16中的边能剖分为两条路（边不相重），试给出这样的剖分。
b）设G是一个具有k个奇数度结点（k>0）的连通图，证明在G中的边能剖分为k2 条路（边不相重）。
c）设G是一个具有k个奇数度结点的图，问最少加几条边到G中，而使所得的图有一条欧拉回路，说明对于图7-4.16如何能做到这一点。
图7-4.16
图7-4.17
d）在c）中如果只允许加平行于G中已存在的边，问最少加几条边到G中，使所得的图有一条欧拉回路，这事总能做到吗？叙述能做到这事的充分必要条件。
5．找一种9个a，9个b，9个 c的圆形排列，使由字母｛a,b,c｝组成的长度为3的27个字的每个字仅出现一次。
6．a）画一个有一条欧拉回路和一条汉密尔顿回路的图。
b）画一个有一条欧拉回路，但没有一条汉密尔顿回路的图。 c）画一个没有一条欧拉回路，但有一条汉密尔顿回路的图。 7．判断图7-4.17所示的图中是否有汉密尔顿回路。
8．设G是一个具有n个结点的简单无向图，n?3，设G的结点表示n个人，G的边表示他们间的友好关系，若两个结点被一条边连结，当且仅当对应的人是朋友。 a）结点的度数能作怎样的解释。 b）G是连通图能作怎样的解释。
c）假定任意两人合起来认识所留下的n-2个人，证明n个人能站成一排，使得中间每个人两旁站着自己的朋友，而两端的两个人，他们每个人旁边只站着他的一个朋友。
d）证明对于n?4，c）中条件保证n个人能站成一圈，使每一个人的两旁站着自己的朋友。
9．证明如G具有汉密尔顿路，则对于V的每一个真子集S有 W(G?S)?S?1
10．一个简单图是汉密尔顿图的充要条件是其闭包是汉密尔顿图。
11．设简单图G??V,E?且V?v,E?e，若有e?Cv?2,?2，则G是汉密尔顿图。 12．将无向完全图K6的边随意地涂上红色或绿色，证明：无论如何涂法，总存在红色的K3 或绿色的K3。
2n213．证明如果G是二部图，它有n个顶点，m条边，则m?。
414．设G为有n个结点的简单图，且E??n?1??n?2?2，则G是连通图。
15．无向图G的各个结点的度数都是3，且结点数n与边数m有关系m?2n?3。在同构 的意义下G是唯一的吗？为什么？
16．（1）n为何值时，无向完全图Kn是欧拉图？n为何值时Kn为半欧拉图？ （2）什么样的完全二部图是欧拉图？ （3）n为何值时，轮图Wn为欧拉图？
17．求图6-20中的两个图各需要几笔画出（笔不离纸，每条边均不能重复画）？
a e l
j f k b
d
g c （1）
图6-20
a i
e h g
f b j
c （2）
d