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

离散数学作业4图论部分概念及性质单项选择题1设图G，vV，则下列结论成立的是 ( ) Adeg(v)=2E Bdeg(v)=EC D答 C（握手定理）2设无向图G的邻接矩阵为，则G的边数为( )A6 B5 C4 D3答 B3已知无向图G的邻接矩阵为，则G有（ ）A5点，8边 B6点，7边 C6点，8边 D5点，7边答 Dooooabcd图一oe4如图一所示，以下说法正确的是 ( ) A(a, e)是割边B(a, e)是边割集C(a, e) ,(b, c)是边割集D(d, e)是边割集答 Doooabcd图二o5图G如图二所示，以下说法正确的是 ( )Aa是割点Bb, c是点割集Cb, d是点割集Dc是点割集答 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（有一条经过每个结点的回路）8设完全图K有n个结点(n2)，m条边，当（ ）时，K中存在欧拉回路Am为奇数 Bn为偶数 Cn为奇数 Dm为偶数答 C9若G是一个汉密尔顿图，则G一定是( )A平面图 B对偶图 C欧拉图 D连通图答 D10若G是一个欧拉图，则G一定是( )A平面图 B汉密尔顿图 C连通图 D对偶图答 C11设G是连通平面图，有v个结点，e条边，r个面，则r= ( )Aev2 Bve2 Cev2 Dev2答 A（欧拉公式：v-e+r = 2）12无向树T有8个结点，则T的边数为( )A6 B7 C8 D9答 B13无向简单图G是棵树，当且仅当( )AG连通且边数比结点数少1 BG连通且结点数比边数少1CG的边数比结点数少1 DG中没有回路答 A14已知一棵无向树T中有8个顶点，4度、3度、2度的分支点各一个，T的树叶数为( )A8 B5 C4 D3解 这棵无向树T有7条边，所有结点的度数之和为14，而4度、3度、2度的分支点各一个共3个结点占用了9度，所以剩下的5个结点占用5度，故有5片树叶答 B15设G是有n个结点，m条边的连通图，必须删去G的( )条边，才能确定G的一棵生成树A B C D答 A（n个结点的连通图的生成树有条边，必须删去条边）答案：1C 2B 3D 4D 5B 6C 7A 8C 9D 10C 11A 12B 13A 14B 15A活动说明：本次作业主要是通过单项选择题的形式，使大家了解自己对第二单元图论的基本概念、基本公式、基本计算方法掌握的情况，更好地掌握这一部分的重点内容本次作业由10个单项选择题组成，每小题10分，满分100分请大家按照题目的要求选择正确答案，正确答案是唯一的本次作业在关闭之前，允许大家反复多次练习，系统将保留您的最好成绩，希望大家多做练习，争取好成绩需要提醒大家的是每次练习的作业题目可能不一样，请大家一定要认真阅读题目活动要求：每位同学在完成本次作业前，应该积极利用课程平台中的相关资源开展学习，或参加教学点的面授辅导课希望大家：1了解了图的基本概念、类型和几种表示方法，图的同构概念及图同构的必要条件；理解了握手定理，路与回路、简单路径、基本路径、简单回路、基本回路、连通性与连通度、点割集与割点、边割集与割边等概念；掌握了图的路、回路、连通性、强连通、点割集、边割集、割点、割边和图同构的判断方法。2理解了欧拉通路、欧拉图的概念，掌握了欧拉图判别的基本方法；了解了汉密尔顿通路、汉密尔顿图的概念，会做简单判断；了解平面图、面、边界、面的次数和非平面图的概念，掌握了欧拉公式的基