★形成性考核作业★
离散数学作业75
姓名：学号：得分：教师签名：教师签名：
离散数学图论部分形成性考核书面作业离散数学图论部分形成性考核书面作业图论部分形成性考核书面
本课程形成性考核书面作业共3次，内容主要分别是图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第二次作业，大家要认真及时地完成图论部分的综合练习作业。要求：要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，完成并上交任课教师（不收电子稿）。并在07任务界面下方点击“保存”和“交卷”按钮，以便教师评分。一、单项选择题001．设图G的邻接矩阵为100A．5A．degV2EC．∑degv2E
v∈V
010000110000，则G的边数为D10011010C．3．B．degVED．∑degvE
v∈V
．
B．6
D．4
2．设图G＝VE，则下列结论成立的是C
3．设有向图（a）、（b）、（c）与（d）如下图所示，则下列结论成立的是D．
A．（a）是强连通的C．（c）是强连通的点集子集中，不是点割集的为（A．bd
B．（b）是强连通的D．（d）是强连通的B）．B．d
bοcο4题图
1
aοοdοe
4．给定无向图G如右图所示，下面给出的结
f★形成性考核作业★
C．acA．ac是割边B．ac是边割集C．bc是边割集D．acbc是边割集
D．be．
aοοdοebοοc5题图
5．图G如右图所示，以下说法正确的是C
6．无向图G存在欧拉通路，当且仅当DA．G中所有结点的度数全为偶数B．G中至多有两个奇数度结点C．G连通且所有结点的度数全为偶数D．G连通且至多有两个奇数度结点7．若G是一个欧拉图，则G一定是C
．
．
A．平面图B．汉密尔顿图C．连通图D．对偶图8．设G是连通平面图，有v个结点，e条边，r个面，则rA．A．e－v＋2确定G的一棵生成树．A．m
1的树叶数为（D
A．8B．m
C．m
1D．
m110．已知一棵无向树T中有8个结点，4度，3度，2度的分支点各一个，T
B．v＋e－2
C．e－v－2
D．e＋v＋2条边，才能
9．设G是有
个结点，m条边的连通图，必须删去G的A
）．
B．5C．4D．3
二、填空题
1．已知图G中有1个1度结点，2个2度结点，3个3度结点，4个4度结
点，则G的边数是15
fcG的结点
．．
2．设给定图Gr