电大_离散数学_形成性考核册_作业(二)答案.doc

离散数学形成性考核作业（二）图论部分本课程形成性考核作业共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为无向图，|G|=9，且G每个结点的度数为5或6，试证明G中至少有5个6度结点或至少有6个5度结点5设有向图D=如图2.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有（ C ） A5点，8边 B6点，7边 C5点，7边 D6点，8边第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一定是( C )A欧拉图 B平面图 C连通图10设G是有n个结点m条边的连通平面图，且有k个面，则k等于( A )Am-n+2 Bn-m-2 Cn+m-2 Dm+n+211无向连通图 G 是欧拉图的充分必要条件是_应填：图中每个结点的度数都是偶度数。12设G是具有n个结点的简单图，若在G中每一对结点度数之和大于等于_，则在G中存在一条汉密尔顿路应填：n-1（即书中P.123定理4.2.2）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的图解：见课堂答疑。W(T)=1+1+1+1+1+2=7 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