离散数学图论部分形成性考核书面作业评n.doc

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