离散数学形成性考核作业（二）第 4 章 几种特殊图1．试分别构造满足下列条件的无向欧拉图（1）有偶数个结点，奇数条边．（2）有偶数个结点，偶数条边．（3）有奇数个结点，偶数条边．（4）有奇数个结点，奇数条边．2．分别构造满足下列条件的四个汉密尔顿图（1）偶数个结点，奇数条边．（2）有偶数个结点，偶数条边．（3）有奇数个结点，偶数条边．（4）有奇数个结点，奇数条边．3．试画出一种没有一条欧拉回路，但有一条汉密尔顿回路的图．4．如图 2
8 与否为欧拉图
试阐明理由．图 2
8 判断与否为欧拉图 5．如图 2
9 与否为汉密尔顿图
试阐明理由．图 2
9 判断与否为汉密尔顿图6．试分别阐明图 4
3（a）、（b）与（c）与否为平面图．图 2
10 判断与否为平面图 7．试分别求出图 2
11（a）、（b）与（c）的每个图的面的次数．图 2
11 求面的次数 8．试运用韦尔奇·鲍威尔算法分别对图 2
12（a）、（b）与（c）着色．图 2
12 图的着色9．若 G 是一种汉密尔顿图，则 G 一定是( )．A．欧拉图 B．平面图 C．连通图10．设 G 是有 n 个结点 m 条边的连通平面图，且有 k 个面，则 k 等于( )．A．m-n+2 B．n-m-2 C．n+m-2 D．m+n+211．无向连通图 G 是欧拉图的充足必要条件是_________________．12．设 G 是具有 n 个结点的简单图，若在 G 中每一对结点度数之和不小于等于________，则在 G 中存在一条汉密尔顿路．13．既有一种具有k 个奇数度结点的图，若要使图中有一条欧拉回路，至少要向图中添加_________条边．第 5 章 树及其应用1．试指出图 2
13 中那些是树，那些是森林，并阐明理由．图 2
13 习题 1 的图2．试画出图 2
14 中的一种生成树，并阐明其中的树枝、弦，以及对应生
