离散数学图论部分形成性考核书面作业讲评
图论作为离散数学的一部分,教学目标是培养学生的抽象思维能力与数学建模能力,并为学生学习后续专业课程等建立必要的数学基础.
图论部分主要介绍图论的基本概念,理论与方法.教学内容包括图的基本概念与结论,几种特殊的图和树,主要内容有图的基本概念,图的连通性与连通度,图的矩阵表示,最短路问题,欧拉图与汉密尔顿图,平面图,对偶图与着色,树与生成树,根树及其应用等.
因此,本次作业主要是复习这部分的主要概念与计算方法,共安排了五种类型题目,其中单项选择题,填空题各有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,故有82=4条边.
6.图G如右图所示,以下说法正确的是 ( ) .
A.{(a, d)}是割边
B.{(a, d)}是边割集
C.{(d, e)}是边割集
D.{(a, d) ,(a, c)}是边割集
正确答案是:C.
许多同学选择答案A.主要是对割边,边割集的概念理解不到位.
定义3.2.9 设无向图G=为连通图,若有边集E1E,使图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=为连通图,若有点集V1V,使图G删除了V1的所有结点后,所得的子图是不连通图,而删除了V1的任何真子集后,所得的子图是连通图,则称V1是G的一个点割集.若某个结点构成一个点割集,则称该结点为割点.
许多同学填写的{f,c}是不满定义3.2.7的,因为{f}是{f,c}的真子集,而删除{f}后,图是不连通的.
6.设有向图D为欧拉图,则图D中每个结点的入度 .
应该填写:等于出度.
许多同学填1,不知为什么.
如果大家记住"具有欧拉回路的图称为欧拉图"和定理4.1.2:一个有向图具有单向欧拉回路,当且仅当它是连通的,且每个结点的入度等于出度.大家一定能填写出正确答案的.
7.设完全图K有n个结点(n2),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.设图GV,E,其中Va1, a2, a3, a4, a5,
Ea1, 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才能使其成为欧拉图.
★ 形成性考核作业 ★
a5
a4
a3
a2
a1
v1
c
d
e
b
a
c
8
3
8
3
9
1
6
2
2
5
1
f
e5
e8
e7
e6
e4
e3
e2
e1
v6
v5
v4
v3
v2
9
1
6
2
2
5
1
f
d
e
b
a