离散数学形成性考核作业（二）

离散数学形成性考核作业（二）第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等于( )Am-n+2 Bn-m-2 Cn+m-2 Dm+n+211无向连通图 G 是欧拉图的充分必要条件是_12设G是具有n个结点的简单图，若在G中每一对结点度数之和大于等于_，则在G中存在一条汉密尔顿路13现有一个具有个奇数度结点的图，若要使图中有一条欧拉回路，最少要向图中添加_条边第5章 树及其应用1试指出图2.13中那些是树，那些是森林，并说明理由图2.13 习题1的图2试画出图2.14中的一个生成树，并说明其中的树枝、弦，以及对应生成树的补 图2.14 习题2的图3试画出如图2.15的完全图K5 的所有不同构的生成树 图2.15 习题3的图4试求出图2.16中的最小生成树及其权值 图2.16 习题4的图 5给定一组权值为1，2，2，3，6，7，9，12，是求出相应的一个最优树 6无向树T有7片树叶, 3个3度结点,其余的都是4度结点，则T有（ ）个4度结点？ A1 B2 C3 D4 7无向树T有3个3度结点,2个4度结点,其余的都是树叶，则T有（ ）片树叶？ A3 B7 C9 D11 8无向树T有1个2度结点,3个3度结点,4个4度结点,1个5度结点,其余的都是树叶，则T有（ ）片树叶？ A12 B14 C16 D20 9无向树T有9片树叶,5个3度结点,其余的都是4度结点，则T有几个4度结点？ A0 B1 C2 D3