离散数学形成性考核作业（二）第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+2B．n-m-2C．n+m-2D．m+n+211．无向连通图G是欧拉图的充分必要条件是_________________．12．设G是具有n个结点的简单图，若在G中每一对结点度数之和大于等于________，则在G中存在一条汉密尔顿路．13．现有一个具有k个奇数度结点的图，若要使图中有一条欧拉回路，最少要向图中添加_________条边．第5章树及其应用1．试指出图2
13中那些是树，那些是森林，并说明理由．图2
13习题1的图2．试画出图2
14中的一个生成树，并说明其中的树枝、弦，以及对应生成树的补．图2
14习题2的图3．试画出如图2
15的完全图K5的所有不同构的生成树．图2
15习题3的图4．试求出图2
16中的最小
