离散数学图论复习

离散数学图论复习

ID:26883976

大小:181.00 KB

页数:8页

时间:2018-11-29

离散数学图论复习_第1页
离散数学图论复习_第2页
离散数学图论复习_第3页
离散数学图论复习_第4页
离散数学图论复习_第5页
资源描述:

《离散数学图论复习》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库

1、WORD格式资料离散数学11春图论部分综合练习辅导大家好!本学期的第二次教学辅导活动现在开始,本次活动主要是针对第二单元图论的重点学习内容进行辅导,方式同样是通过讲解一些典型的综合练习作业题目,帮助大家进一步理解和掌握图论的基本概念和方法.图论作为离散数学的一部分,主要介绍图论的基本概念、理论与方法.教学内容主要有图的基本概念与结论、图的连通性与连通度、图的矩阵表示、最短路问题、欧拉图与汉密尔顿图、平面图、对偶图与着色、树与生成树、根树及其应用等.本次综合练习主要是复习这一单元的主要概念与计算方法,与集合论一样,也安排了五种类型,有单项选

2、择题、填空题,判断说明题、计算题、证明题.这样的安排也是为了让同学们熟悉期末考试的题型,能够较好地完成这一部分主要内容的学习.下面是本学期第4,5次形考作业中的部分题目.一、单项选择题单项选择题主要是第4次形考作业的部分题目.第4次作业同样也是由10个单项选择题组成,每小题10分,满分100分.在每次作业在关闭之前,允许大家反复多次练习,系统将保留您的最好成绩,希望大家要多练几次,争取好成绩.需要提醒大家的是每次练习的作业题目可能不一样,请大家一定要认真阅读题目.1.设图G=,vÎV,则下列结论成立的是().A.deg(v)=2

3、½E½B.deg(v)=½E½C.D.该题主要是检查大家对握手定理掌握的情况.复习握手定理:定理3.1.1设G是一个图,其结点集合为V,边集合为E,则也就是说,无向图G的结点的度数之和等于边数的两倍.正确答案:C2.设无向图G的邻接矩阵为,则G的边数为().A.6B.5C.4D.3主要是检查对邻接矩阵的概念理解是否到位.专业整理WORD格式资料大家要复习邻接矩阵的定义,要记住当给定的简单图是无向图时,邻接矩阵为对称的.即当结点vi与vj相邻时,结点vj与vi也相邻,所以连接结点vi与vj的一条边在邻接矩阵的第i行第j列处和第j行第i列处各

4、有一个1,题中给出的邻接矩阵中共有10个1,故有10¸2=5条边.ooooabcdoe正确答案:B3.如右图所示,以下说法正确的是().A.{(a,e)}是割边B.{(a,e)}是边割集C.{(a,e),(b,c)}是边割集D.{(d,e)}是边割集先复习割边、边割集的定义:定义3.2.9设无向图G=为连通图,若有边集E1ÌE,使图G删除了E1的所有边后,所得的子图是不连通图,而删除了E1的任何真子集后,所得的子图是连通图,则称E1是G的一个边割集.若某个边构成一个边割集,则称该边为割边(或桥)因为删除答案A或B或C中的边后,得

5、到的图是还是连通图,因此答案A、B、C是错误的.正确答案:Doooabcdo4.图G如由图所示,以下说法正确的是().A.a是割点B.{b,c}是点割集C.{b,d}是点割集D.{c}是点割集主要是检查对点割集、割点的概念理解的情况.定义3.2.7设无向图G=为连通图,若有点集V1ÌV,使图G删除了V1的所有结点后,所得的子图是不连通图,而删除了V1的任何真子集后,所得的子图是连通图,则称V1是G的一个点割集.若某个结点构成一个点割集,则称该结点为割点.从图二中删除结点b,c,得到的子图是由不连通图,而只删除结点b或结点c,得到

6、的子图仍然是连通的,由定义可以知道,{b,c}是点割集.所以正确答案:B5.设有向图(a)、(b)、(c)与(d)如下图所示,则下列结论成立的是().A.(a)是强连通的B.(b)是强连通的专业整理WORD格式资料C.(c)是强连通的D.(d)是强连通的我们先复习强连通的概念:定义3.2.5在简单有向图中,若在任何结点偶对中,至少从一个结点到另一个结点可达的,则称图G是单向(侧)连通的;若在任何结点偶对中,两结点对互相可达,则称图G是强连通的.正确答案:A问:上面的图中,哪个仅为弱连通的?请大家要复习“弱连通”的概念.6.设完全图K有n个

7、结点(n³2),m条边,当()时,K中存在欧拉回路.A.m为奇数B.n为偶数C.n为奇数D.m为偶数我们先复习完全图的概念:定义3.1.6简单图G=中,若每一对结点间都有边相连,则称该图为完全图.有n个结点的无向完全图记为Kn.由定义可知,完全图Kn中的任一结点v到其它结点都有一条边,共有n-1条边,即每个结点的度数是n-1,当n为奇数时,n-1为偶数.由定理4.1.1的推论一个无向图具有一条欧拉回路,当且仅当该图是连通的,并且它的结点度数都是偶数.所以,正确答案应该是C.7.若G是一个汉密尔顿图,则G一定是().A.平面图B.

8、对偶图C.欧拉图D.连通图我们先复习汉密尔顿图的概念:定义4.2.1给定图G,若存在一条路经过图G的每个结点一次且仅一次,则该路称为汉密尔顿路;若存在一条回路经过图G的每个结点一次且仅一次,则

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。