离散数学形成性考核作业(二)

《离散数学形成性考核作业(二)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、离散数学形成性考核作业（二）图论部分本课程形成性考核作业共4次，内容由中央电大确定、统一布置。本次形考作业是第二次作业，大家要认真及时地完成图论部分的形考作业，字迹工整，抄写题目，解答题有解答过程。第3章图的基本概念与性质1．计算出下图2.1的结点数与边数，并说明其满足握手定理．图2.1习题1的图2．试分别画出下列图2.2(a)、(b)、(c)的补图．图2.2习题2的图3．找出下图2.3中的路、通路与圈．图2.3习题3的图4．设G为无向图，

2、G

3、=9，且G每个结点的度数为5或6，试证明G中至少有5个6度结点或至少有6个5度结点．5．设有向图D=如图2.4所示

4、，图2.4习题5的图试问图中是否存在长度分别为3,4,5,6的回路，如存在，试找出．6．若无向图G有10条边，3度与4度结点均2个，其余结点的度数均小于3，试问G中至少有几个结点？若无向图G中有6条边，3度与5度结点均有一个，其余结点的度数均是2，试问G中有几个结点?7．试求图2.5中有向图的强分图，单侧分图和弱分图．图2.5习题7的图8．试说明图2.6中G1和G2同构．图2.6习题8的图9．试求图2.7中的邻接矩阵与可达矩阵．图2.7习题9的图10．有n个结点的无向完全图的边数为．11．图中度数为奇数的结点为数个．12．已知图G的邻接矩阵为，则G有（）．A．5点，8

5、边B．6点，7边C．5点，7边D．6点，8边第4章几种特殊图1．试分别构造满足下列条件的无向欧拉图（1）有偶数个结点，奇数条边．（2）有偶数个结点，偶数条边．（3）有奇数个结点，偶数条边．（4）有奇数个结点，奇数条边．2．分别构造满足下列条件的四个汉密尔顿图（1）偶数个结点，奇数条边．（2）有偶数个结点，偶数条边．（3）有奇数个结点，偶数条边．（4）有奇数个结点，奇数条边．3．试画出一个没有一条欧拉回路，但有一条汉密尔顿回路的图．4．如图2.8是否为欧拉图？试说明理由．图2.8判断是否为欧拉图5．如图2.9是否为汉密尔顿图？试说明理由．图2.9判断是否为汉密尔顿图6．

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中每

7、一对结点度数之和大于等于________，则在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，是求出相应的一个最优

8、树．6．无向树T有7片树叶,3个3度结点,其余的都是4度结点，则T有（）个4度结点？A．1B．2C．3D．47．无向树T有3个3度结点,2个4度结点,其余的都是树叶，则T有（）片树叶？A．3B．7C．9D．118．无向树T有1个2度结点,3个3度结点,4个4度结点,1个5度结点,其余的都是树叶，则T有（）片树叶？A．12B．14C．16D．209．无向树T有9片树叶,5个3度结点,其余的都是4度结点，则T有几个4度结点？A．0B．1C．2D．3