习题?/p>
:
欧拉图与汉密尔顿?/p>
1
.判定图
7-4.15
的图形是否能一笔画?/p>
2
.构造一个欧拉图,其结点?/p>
v
和边?/p>
e
满足下述条件
a
?/p>
v
?/p>
e
的奇偶性一样?/p>
b
?/p>
v
?/p>
e
的奇偶性相反?/p>
如果不可能,说明原因?/p>
3
.确?/p>
n
取怎样的值,完全?/p>
n
K
有一条欧拉回路?/p>
4
?/p>
a
)图
7-4.16
中的边能剖分为两条路(边不相重)
,试给出这样的剖分?/p>
b
)设
G
是一个具?/p>
k
个奇数度结点?/p>
k
>0
)的连通图,证明在
G
中的边能剖分?/p>
2
k
条路(边不相重)
?/p>
c
)设
G
是一个具?/p>
k
个奇数度结点的图,问最少加几条边到
G
中,而使所得的图有一
条欧拉回路,说明对于?/p>
7-4.16
如何能做到这一点?/p>
d
)在
c
)中如果只允许加平行?/p>
G
中已存在的边,问最少加几条边到
G
中,使所得的
图有一条欧拉回路,这事总能做到吗?叙述能做到这事的充分必要条件?/p>
5
.找一?/p>
9
?/p>
a
?/p>
9
?/p>
b
?/p>
9
?/p>
c
的圆形排列,使由字母?/p>
c
b
a
,
,
}组成的长度?/p>
3
?/p>
27
个字的每个字仅出现一次?/p>
6
?/p>
a
)画一个有一条欧拉回路和一条汉密尔顿回路的图?/p>
?/p>
7-4.15
(a)
(b)
?/p>
7-4.16
?/p>
7-4.17