10秋作业4(04任务)：图论部分概念和性

《10秋作业4(04任务)：图论部分概念和性》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、离散数学作业4图论部分概念及性质单项选择题1．设图G＝，vÎV，则下列结论成立的是()．A．deg(v)=2½E½B．deg(v)=½E½C．D．答C（握手定理）2．设无向图G的邻接矩阵为，则G的边数为()．A．6B．5C．4D．3答B3．已知无向图G的邻接矩阵为，则G有（）．A．5点，8边B．6点，7边C．6点，8边D．5点，7边答Dooooabcd图一oe4．如图一所示，以下说法正确的是()．A．{(a,e)}是割边B．{(a,e)}是边割集C．{(a,e),(b,c)}是边割集D．{(d,e)

2、}是边割集答D4oooabcd图二o5．图G如图二所示，以下说法正确的是()．A．a是割点B．{b,c}是点割集C．{b,d}是点割集D．{c}是点割集答Boooabcd图三o6．图G如图三所示，以下说法正确的是()．A．{(a,d)}是割边B．{(a,d)}是边割集C．{(a,d),(b,d)}是边割集D．{(b,d)}是边割集答C7．设有向图（a）、（b）、（c）与（d）如图四所示，则下列结论成立的是()．图四A．（a）是强连通的B．（b）是强连通的C．（c）是强连通的D．（d）是强连通的答A（有一条经过

3、每个结点的回路）8．设完全图K有n个结点(n≥2)，m条边，当（）时，K中存在欧拉回路．A．m为奇数B．n为偶数C．n为奇数D．m为偶数答C9．若G是一个汉密尔顿图，则G一定是()．A．平面图B．对偶图C．欧拉图D．连通图答D10．若G是一个欧拉图，则G一定是()．A．平面图B．汉密尔顿图C．连通图D．对偶图4答C11．设G是连通平面图，有v个结点，e条边，r个面，则r=()．A．e－v＋2B．v＋e－2C．e－v－2D．e＋v＋2答A（欧拉公式：v-e+r=2）12．无向树T有8个结点，则T的边数为()．A

4、．6B．7C．8D．9答B13．无向简单图G是棵树，当且仅当()．A．G连通且边数比结点数少1B．G连通且结点数比边数少1C．G的边数比结点数少1D．G中没有回路．答A14．已知一棵无向树T中有8个顶点，4度、3度、2度的分支点各一个，T的树叶数为()．A．8B．5C．4D．3解这棵无向树T有7条边，所有结点的度数之和为14，而4度、3度、2度的分支点各一个共3个结点占用了9度，所以剩下的5个结点占用5度，故有5片树叶．答B15．设G是有n个结点，m条边的连通图，必须删去G的()条边，才能确定G的一棵生成树．

5、A．B．C．D．答A（n个结点的连通图的生成树有条边，必须删去条边）答案：1．C2．B3．D4．D5．B6．C7．A8．C9．D10．C11．A12．B13．A14．B15．A活动说明：本次作业主要是通过单项选择题的形式，使大家了解自己对第二4单元图论的基本概念、基本公式、基本计算方法掌握的情况，更好地掌握这一部分的重点内容．本次作业由10个单项选择题组成，每小题10分，满分100分．请大家按照题目的要求选择正确答案，正确答案是唯一的．本次作业在关闭之前，允许大家反复多次练习，系统将保留您的最好成绩，希望大家

6、多做练习，争取好成绩．需要提醒大家的是每次练习的作业题目可能不一样，请大家一定要认真阅读题目．活动要求：每位同学在完成本次作业前，应该积极利用课程平台中的相关资源开展学习，或参加教学点的面授辅导课．希望大家：1．了解了图的基本概念、类型和几种表示方法，图的同构概念及图同构的必要条件；理解了握手定理，路与回路、简单路径、基本路径、简单回路、基本回路、连通性与连通度、点割集与割点、边割集与割边等概念；掌握了图的路、回路、连通性、强连通、点割集、边割集、割点、割边和图同构的判断方法。2．理解了欧拉通路、欧拉图的概念

7、，掌握了欧拉图判别的基本方法；了解了汉密尔顿通路、汉密尔顿图的概念，会做简单判断；了解平面图、面、边界、面的次数和非平面图的概念，掌握了欧拉公式的基本应用．3．理解了树、生成树和最小生成树等概念，了解了有向树、根树、有序树、二叉树、二叉完全树、正则二叉树、带权二叉树和最优二叉树等概念。活动形式：在线测试．活动时间：4