资源描述：
《中央电大离散数学作业5习题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、中央电大离散数学作业5?形成性考核作业?离散数学作业5离散数学图论部分形成性考核书面作业本课程形成性考核书面作业共3次，)(A(5B(6C(3D(42(设图G,<V,E>，则下列结论成立的是(C)(A(B(((3(设有向图(a)、(b)、(c)与(d)如下图所示，则下列结论成立的是(D)(A((a)是强连通的B((b)是强连通的C((c)是强连通的D((d)是强连通的4(给定无向图G如右图所示，下面给出的结点集子集中，不是点割集的为(B)(A({b,d}B({d}abc4题图de1?形成性考核作业?C({a,c}D({b,e}5(图G如右图所示，以下说法正确的是(C)(A({(a
2、,c)}是割边B({(a,c)}是边割集C({(b,c)}是边割集D({(a,c),(b,c)}是边割集6(无向图G存在欧拉通路，当且仅当(D)(A(G中所有结点的度数全为偶数B(G中至多有两个奇数度结点C(G连通且所有结点的度数全为偶数D(G连通且至多有两个奇数度结点7(若G是一个欧拉图，则G一定是(C)(A(平面图B(汉密尔顿图C(连通图D(对偶图8(设G是连通平面图，有v个结点，e条边，r个面，则r=(A)(A(e,v，2B(v，e,2C(e,v,2D(e，v，29(设G是有n个结点，m条边的连通图，必须删去G的(A)条边，才能确定G的一棵生成树(A((((10(已知一棵无向树T中有8
3、个结点，4度，3度，2度的分支点各一个，T的树叶数为(D)(A(8B(5C(4D(3二、填空题1(已知图G中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G的边数是15(2(设给定图G(如右由图所示)，则图G的点割集是3(设G是一个图，结点集合为V，边集合为E，则G的结点等于边数的两倍(4(设有向图D为欧拉图，则图D中每个结点的入度5(设G=<V，E>是具有n个结点的简单图，若在G中每一对结点度数之和大于等于n-1，则在G中存在一条汉密尔顿路(6(设无向图G,<V，E>是汉密尔顿图，则V的任意非空子集V1，都有(7(设完全图Kn有n个结点，m条边，当当m
4、=2n时，Kn中存在欧拉回路(8(设图，其中，(则图G是树当且仅当G是连通的，b5题图adec2?形成性考核作业?且-2(9(连通无向图G有6个顶点9条边，从G中删去条边才有可能得到G的一棵生成树T(10(设正则5叉树的树叶数为17，则分支数为i三、判断说明题(判断下列各题，并说明理由()1((1)如果图G是无向图，且其结点度数均为偶数，则图G存在一条欧拉回路(((2)图G1，(如下图所示)是欧拉图(解:(1)错，图G是无向图，当且仅当G是连通的，且所有结点度数均为偶数，这里不能确定G图是否是连通的。(2)错，由欧拉图的定理“无向图G具有一条欧拉路，当且仅当G是连通的，且有零个或两个奇数度结
5、点”得到这里任何一个结点都没有奇数度结点。2(图G2(如下图所示)不是欧拉图而是汉密尔顿图(解:错，既不是欧拉图也不是汉密尔图。欧拉图要求所有结点度数均为偶数，这里结点b,d各有三个节点;汉密尔图要求每一对结点度数之和大于等于总结点数，这里不满足。3?形成性考核作业?3((1)设G是一个有7个结点16条边的连通图，则G为平面图((2)设G是一个连通平面图，且有6个结点11条边，则G有7个面(解:(1)错，没有提到面。(2)对，由欧拉定理得到:结点-边+面=2，即为连通平面图，这里6-11+7=24(下图给出的树是否同构的(解:(a)同构，(b),(c)同构。因为由图的同构相关联，得到同构的必
6、要条件:(1)结点数目相同。(2)边数相同。(3)度数相同的结点数目相同故(a)不满足，即不同构。四、计算题4?形成性考核作业?1(设G=<V，E>，V={v1，v2，v3，v4，v5}，E={(v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5)}，试(1)给出G的图形表示;(2)写出其邻接矩阵;(3)求出每个结点的度数;(4)画出其补图的图形(解:(1)(3)v1度数为1，v2度数为2，v3度数为4，v4度数为3，v5度数为22(图G=<V,E>，其中V={a,b,c,d,e,f}，E={(a,b),(a,c),(a,e),
7、(b,d),(b,e),(c,e),(d,e),(d,f),(e,f)}，对应边的权值依次为5，2，1，2，6，1，9，3及8((2)写出G的邻接矩阵;(1)画出G的图形;(3)求出G权最小的生成树及其权值(5?形成性考核作业?解:(3)最{(a,e),(e,c),(b,d),(d,f)}权值为3(已知带权图G如右图所示((1)求图G的最小生成树;(2)计算该生成树的权值(解:(1)最小生成树为{1,4,3,
