文档介绍：离散数学图论部分形成性考核书面作业讲评
图论作为离散数学的一部分,教学目标是培养学生的抽象思维能力与数学建模能力,并为学生学****后续专业课程等建立必要的数学基础。
图论部分主要介绍图论的基本概念、理论与方法。教学内容包括图的基本概念与结论、几种特殊的图和树,主要内容有图的基本概念、图的连通性与连通度、图的矩阵表示、最短路问题、欧拉图与汉密尔顿图、平面图、对偶图与着色、树与生成树、根树及其应用等。
因此,本次作业主要是复****这部分的主要概念与计算方法,共安排了五种类型题目,其中单项选择题、填空题各有10个题,判断说明题、计算题、证明题各有4题。这样的安排也是为了让同学们熟悉期末考试的题型。通过对作业的批阅,发现作业中错误比较集中在以下一些问题中,在此给出一些分析。
一、单项选择题
则G的边数为( ).
正确答案是:D。
许多同学选择答案B。主要是对邻接矩阵的概念理解不到位。
设G=<V,E>是一个简单图,其中V={v1,v2,…, vn},则 n阶方阵A(G)=(aij)
而当给定的简单图是无向图时,,结点vj与vi也相邻,所以连接结点vi与vj的一条边在邻接矩阵的第i行第j列处和第j行第i列处各有一个1,题中给出的邻接矩阵中共有8个1,故有8¸2=4条边。
,以下说法正确的是( ) .
A.{(a, d)}是割边
B.{(a, d)}是边割集
C.{(d, e)}是边割集
D.{(a, d) ,(a, c)}是边割集
正确答案是:C。
许多同学选择答案A。主要是对割边、边割集的概念理解不到位。
设无向图G=<V, E>为连通图,若有边集E1ÌE,使图G删除了E1的所有边后,所得的子图是不连通图,而删除了E1的任何真子集后,所得的子图是连通图,,则称该边为割边(或桥)
如果答案A正确,即删除边(a, d)后,得到的图是不连通图,但事实上它还是连通的。因此答案A是错误的。
,当且仅当( ).
正确答案是:D。
许多同学选择答案C。主要是将题中的“欧拉通路”误认为“欧拉回路”了。
。
,m条边的连通图,必须删去G的( )条边,才能确定G的一棵生成树.
A. B. C. D.
正确答案是:A。
许多同学选择答案D。=v-=v-1中的e,把n代入公式e=v-1中的v,可以知道答案A是正确。
二、填空题
,2个2度结点,3个3度结点,4个4度结点,则G的边数是.
应该填写:15。
许多同学填错答案主要对握手定理掌握的不好。
(握手定理) 设G是一个图,其结点集合为V,边集合为E,则
因为图G中有1个1度结点,