离散数学形成性考核作业（三）VIP免费

离散数学图论部分综合练习辅导本次活动是本学期的第二次活动(2008

18)，主要是针对第二单元图论的重点学习内容进行辅导，方式是通过讲解一些典型的综合练习题目，帮助大家进一步理解和掌握图论的基本概念和方法

图论作为离散数学的一部分，主要介绍图论的基本概念、理论与方法

教学内容主要有图的基本概念与结论、图的连通性与连通度、图的矩阵表示、最短路问题、欧拉图与汉密尔顿图、平面图、对偶图与着色、树与生成树、根树及其应用等

本次综合练习主要是复习这一部分的主要概念与计算方法，与集合论一样，也安排了五种类型，有单项选择题、填空题，判断说明题、计算题、证明题

这样的安排也是为了让同学们熟悉期末考试的题型，能够较好地完成这一部分主要内容的学习

下面分别讲解

一、单项选择题1．设图G的邻接矩阵为则G的边数为()．A．5B．6C．3D．4正确答案：D上学期的作业中，有的同学选择答案B

主要是对邻接矩阵的概念理解不到位

我们复习定义：定义3

1设G=是一个简单图，其中V={v1，v2，…，vn}，则n阶方阵A（G）=（aij）称为G的邻接矩阵．其中各元素aij=¿{1viv与j相邻¿¿¿¿而当给定的简单图是无向图时，邻接矩阵为对称的．即当结点vi与vj相邻时，结点vj与vi也相邻，所以连接结点vi与vj的一条边在邻接矩阵的第i行第j列处和第j行第i列处各有一个1，题中给出的邻接矩阵中共有8个1，故有82=4条边

2．设图G＝，则下列结论成立的是()．A．deg(V)=2EB．deg(V)=EC．∑v∈Vdeg(v)=2|E|D．∑v∈Vdeg(v)=|E|正确答案：Ccabedf该题主要是检查大家对握手定理掌握的情况

复习握手定理：定理3

1设G是一个图，其结点集合为V，边集合为E，则∑v∈Vdeg(v)=2|E|3．图G如右图所示，以下说法正确的是()．A．{(a,d)