小米课
返回首页 | 淘宝问答 | 提交答案
关键字: 威胁 防范 国外 科技优势 考核 电大 汉语专题 赤脚医生 | 时间:2024-09-19 15:36

发布时间:2024-09-19 15:36

| 人浏览

【答案】《离散数学图论部分》形成性考核书面作业讲评


离散数学图论部分形成性考核书面作业讲评
  
  图论作为离散数学的一部分,教学目标是培养学生的抽象思维能力与数学建模能力,并为学生学习后续专业课程等建立必要的数学基础。
  图论部分主要介绍图论的基本概念、理论与方法。教学内容包括图的基本概念与结论、几种特殊的图和树,主要内容有图的基本概念、图的连通性与连通度、图的矩阵表示、最短路问题、欧拉图与汉密尔顿图、平面图、对偶图与着色、树与生成树、根树及其应用等。
  因此,本次作业主要是复习这部分的主要概念与计算方法,共安排了五种类型题目,其中单项选择题、填空题各有10个题,判断说明题、计算题、证明题各有4题。这样的安排也是为了让同学们熟悉期末考试的题型。通过对作业的批阅,发现作业中错误比较集中在以下一些问题中,在此给出一些分析。
  
  一、单项选择题
  1.设图G的邻接矩阵为
  
则G的边数为( ).
   A.5 B.6 C.3 D.4
  正确答案是:D。
  许多同学选择答案B。主要是对邻接矩阵的概念理解不到位。
定义3.3.1 设G=是一个简单图,其中V={v1,v2,..., vn},则 n阶方阵A(G)=(aij)称为G的邻接矩阵.其中各元素

  而当给定的简单图是无向图时,邻接矩阵为对称的.即当结点vi与vj相邻时,结点vj与vi也相邻,所以连接结点vi与vj的一条边在邻接矩阵的第i行第j列处和第j行第i列处各有一个1,题中给出的邻接矩阵中共有8个1,故有8?2=4条边。
  
  6.图G如右图所示,以下说法正确的是 ( ) .
   A.{(a, d)}是割边
   B.{(a, d)}是边割集
   C.{(d, e)}是边割集
   D.{(a, d) ,(a, c)}是边割集
  正确答案是:C。
  许多同学选择答案A。主要是对割边、边割集的概念理解不到位。
定义3.2.9 设无向图G=为连通图,若有边集E1?E,使图G删除了E1的所有边后,所得的子图是不连通图,而删除了E1的任何真子集后,所得的子图是连通图,则称E1是G的一个边割集.若某个边构成一个边割集,则称该边为割边(或桥)
  如果答案A正确,即删除边(a, d)后,得到的图是不连通图,但事实上它还是连通的。因此答案A是错误的。
  
  8.无向图G存在欧拉通路,当且仅当( ).
   A.G中所有结点的度数全为偶数
   B.G中至多有两个奇数度结点
   C.G连通且所有结点的度数全为偶数
   D.G连通且至多有两个奇数度结点
  正确答案是:D。
  许多同学选择答案C。主要是将题中的"欧拉通路"误认为"欧拉回路"了。
这样应该用定理4.1.1选择才是正确的。

  9.设G是有n个结点,m条边的连通图,必须删去G的( )条边,才能确定G的一棵生成树.
   A. B. C. D.
  正确答案是:A。
  许多同学选择答案D。主要是把定理5.1.1给出的图T为树的定义等价之一是图T连通且e=v-1中的公式用错了.大家只要把m代入公式e=v-1中的e,把n代入公式e=v-1中的v,可以知道答案A是正确。
  
  二、填空题
  1.已知图G中有1个1度结点,2个2度结点,3个3度结点,4个4度结点,则G的边数是 .
  应该填写:15。
  许多同学填错答案主要对握手定理掌握的不好。
  定理3.1.1(握手定理) 设G是一个图,其结点集合为V,边集合为E,则

  因为图G中有1个1度结点,2个2度结点,3个3度结点,4个4度结点,即,所以边数有。
  
  2.设给定图G(如由图所示),则图G的点割集是 .
  应该填写:{f},{c,e}。
  许多同学填错答案主要对点割集的概念理解不正确。
  定义3.2.7 设无向图G=为连通图,若有点集V1?V,使图G删除了V1的所有结点后,所得的子图是不连通图,而删除了V1的任何真子集后,所得的子图是连通图,则称V1是G的一个点割集.若某个结点构成一个点割集,则称该结点为割点.
  许多同学填写的{f,c}是不满定义3.2.7的,因为{f}是{f,c}的真子集,而删除{f}后,图是不连通的。
  
  6.设有向图D为欧拉图,则图D中每个结点的入度     .
  应该填写:等于出度。
  许多同学填1,不知为什么。
如果大家记住"具有欧拉回路的图称为欧拉图"和定理4.1.2:一个有向图具有单向欧拉回路,当且仅当它是连通的,且每个结点的入度等于出度.大家一定能填写出正确答案的。
  
  7.设完全图K有n个结点(n?2),m条边,当 时,K中存在欧拉回路.
  应该填写:n为奇数。
  许多同学填错答案主要对完全图的概念理解不正确。
定义3.1.6 简单图G=中,若每一对结点间都有边相连,则称该图为完全图.有n个结点的无向完全图记为Kn.
  由定义可知,完全图Kn中的任一结点v到其它结点都有一条边,共有n-1条边,即每个结点的度数是n-1,当n为奇数时,n-1为偶数。
  由定理4.1.1的推论可知,应该填写:n为奇数。
  
  10.给定一个序列集合{1,01,10,11,001,000},若去掉其中的元素 ,则该序列集合构成前缀码.
  应该填写:1。因为在二进制中1是10和11的前缀。而前缀码的定义是(定义5.2.10):给定一个序列集合,若没有一个序列是另一个序列的前缀,该序列集合称为前缀码.
  填写该题答案是,大家一定要对前缀码的定义理解非常清楚。
  
  三、判断说明题
  2.给定两个图G1,G2(如下图所示):
  (1)试判断它们是否为欧拉图、汉密尔顿图?并说明理由.
  (2)若是欧拉图,请写出一条欧拉回路.

  
  分析:大家的判断都正确,而且欧拉图的理由说明也是正确的。
问题是
  1.欧拉回路的书写不规范,正确的写法(不惟一):
v1 e1 v2 e2 v3 e3 v4 e5v5 e7 v2 e8v6 e6 v4 e4v1
2.汉密尔顿图的理由说明不对,其实只要写出一条汉密尔顿回路(不惟一):
a(a, b)b(b, e) e(e, f) f (f, g) g(g, d) d(d, c) c(c, a)a
即可。
  
  四、计算题
  1.设图G??V,E?,其中V??a1, a2, a3, a4, a5?,
E???a1, a2?,?a2, a4?,?a3, a1?,?a4, a5?,?a5, a2??
  (1)试给出G的图形表示;
  (2)求G的邻接矩阵;
  (3)判断图G是强连通图、单侧连通图还是弱连通图?
  解:(1)图G是有向图: (2)邻接矩阵如下:
                     
  (3)单侧连通图.
  
讲评:作业中的问题主要是粗心大意,如有向图中有些边上没标方向,在邻接矩阵中第1行第3列中填了1。因此,做题要细心。
  
  2.图G=,其中V={a, b, c, d, e, f },E={ (a, b), (a, c), (a, e), (b, d), (b, e), (c, e), (d, e), (d, f), (e, f) },对应边的权值依次为5,2,1,2,6,1,9,3及8.
  (1)画出G的图形;
  (2)写出G的邻接矩阵;
  (3)求出G权最小的生成树及其权值.
  解:(1)G的图形表示为:





  (2)邻接矩阵:

  (3)粗线表示最小的生成树:
         






最小的生成树的权为1+1+5+2+3=12.
  
讲评:作业中的最小的生成树求错,主要是没有把握"取权数最小的边且与前面取到的边不构成圈"的方法。

  4.设有一组权为2,3,5,7,11,13,17,19,23,29,31,试
  (1)画出相应的最优二叉树;
  (2)计算它们的权值.
  
讲评:作业中最优二叉树都画对了,但计算总权值时把有些权的层数计算错了,导致总权值计算错误。
  
  五、证明题
讲评:证明题几乎全部做错,应该是大家对证明题方法没有掌握,也是一些概念不清楚所造成的,希望大家各自分析原因,找出问题所在,通过作业逐步掌握做证明题的方法。
  
  1.若无向图G中只有两个奇数度结点,则这两个结点一定是连通的.
  证明:用反证法.设G中的两个奇数度结点分别为u和v.假设u和v不连通,即它们之间无任何通路,则G至少有两个连通分支G1,G2,且u和v分别属于G1和G2,于是G1和G2各含有一个奇数度结点.这与握手定理的推论矛盾.因而u和v一定是连通的.
  
  2.设G是一个n阶无向简单图,n是大于等于2的奇数.证明图G与它的补图中的奇数度顶点个数相等.
证明:因为n是奇数,即n阶完全图每个顶点度数为偶数.那么,若G中顶点v的度数为奇数时,在补图中v的度数一定也是奇数,所以G与中的奇数度顶点个数相等.
  
  3.设G是连通简单平面图,则它一定有一个度数不超过5的结点.(提示:用反证法)
  证明:因为G是连通简单平面图,它的每个面至少有3条边,所以有
,即
假设结论不成立,则每个结点的度数都大于等于6.则有
,即有
  由欧拉公式: 2==0
  矛盾.所以G中至少有一个结点的度数小于或等于5.
  
  4.设连通图G有k个奇数度的结点,证明在图G中至少要添加条边才能使其成为欧拉图.
  证明:由定理3.1.2,任何图中度数为奇数的结点必是偶数,可知k是偶数.
又根据定理4.1.1的推论,图G是欧拉图的充分必要条件是图G不含奇数度结点.因此只要在每对奇数度结点之间各加一条边,使图G的所有结点的度数变为偶数,成为欧拉图.
  故最少要加条边到图G才能使其成为欧拉图.
★ 形成性考核作业 ★




1



答案有错

上一篇:《离散数学》形成性考核作业1

下一篇:暂无

小米课手机端XML联系我们