习题四欧拉图与汉密尔顿图.doc

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