2018年成人高考离散数学图论部分期末复习辅导知识点复
发布时间:2020-10-07 14:42:27
发布时间:2020-10-07 14:42:27
离散数学图论部分期末复习辅导
一、单项选择题
1.设图G=<V, E>,vV,则下列结论成立的是 ( ) .
A.deg(v)=2E B.deg(v)=E
C. D.
解 根据握手定理(图中所有结点的度数之和等于边数的两倍)知,答案C成立。
答 C
2.设无向图G的邻接矩阵为
,
则G的边数为( ).
A.6 B.5 C.4 D.3
解 由邻接矩阵的定义知,无向图的邻接矩阵是对称的.即当结点vi与vj相邻时,结点vj与vi也相邻,所以连接结点vi与vj的一条边在邻接矩阵的第i行第j列处和第j行第i列处各有一个1,题中给出的邻接矩阵中共有10个1,故有102=5条边。
答 B
3.已知无向图G的邻接矩阵为
,
则G有( ).
A.5点,8边 B.6点,7边
C.6点,8边 D.5点,7边
解 由邻接矩阵的定义知,矩阵是5阶方阵,所以图G有5个结点,矩阵元素有14个1,14÷2=7,图G有7条边。
答 D
4.如图一所示,以下说法正确的是 ( ) .
A.{(a, e)}是割边
B.{(a, e)}是边割集
C.{(a, e) ,(b, c)}是边割集
D.{(d, e)}是边割集
定义3.2.9 设无向图G=<V,E>为连通图,若有边集E1E,使图G删除了E1的所有边后,所得的子图是不连通图,而删除了E1的任何真子集后,所得的子图仍是连通图,则称E1是G的一个边割集.若边割集为单元集{e},则称边e为割边(或桥).
解 割边首先是一条边,因为答案A中的是边集,不可能是割边,因此答案A是错误的.删除答案B或C中的边后,得到的图是还是连通图,因此答案B、C也是错误的.在图一中,删去(d, e)边,图就不连通了,所以答案D正确.
答 D
注:如果该题只给出图的结点和边,没有图示,大家也应该会做.如:
若图G=<V, E>,其中V={ a, b, c, d, e },E={ (a, b), (a, c) , (a, e) , (b, c) , (b, e) , (c, e) , (e, d)},则该图中的割边是什么?
5.图G如图二所示,以下说法正确的是 ( ).
A.a是割点
B.{b, c}是点割集
C.{b, d}是点割集
D.{c}是点割集
定义3.2.7 设无向图G=<V,E>为连通图,若有点集V1V,使图G删除了V1的所有结点后,所得的子图是不连通图,而删除了V1的任何真子集后,所得的子图仍是连通图,则称V1是G的一个点割集.若点割集为单元集{v},则称结点v为割点.
解 在图二中,删去结点a或删去结点c或删去结点b和d图还是连通的,所以答案A、C、D是错误的.在图二中删除结点b和c,得到的子图是不连通图,而只删除结点b或结点c,得到的子图仍然是连通的,由定义可以知道,{b, c}是点割集.所以答案B是正确的.
答 B
6.图G如图三所示,以下说法正确的是 ( ) .
A.{(a, d)}是割边
B.{(a, d)}是边割集
C.{(a, d) ,(b, d)}是边割集
D.{(b, d)}是边割集
解 割边首先是一条边,{(a, d)}是边集,不可能是割边.在图三中,删除答案B或D中的边后,得到的图是还是连通图.因此答案A、B、D是错误的.在图三中,删去(a, d)边和(b, d)边,图就不连通了,而只是删除(a, d)边或(b, d)边,图还是连通的,所以答案C正确.
7.设有向图(a)、(b)、(c)与(d)如图四所示,则下列结论成立的是( ).
图四
A.(a)是强连通的 B.(b)是强连通的
C.(c)是强连通的 D.(d)是强连通的
复习:定义3.2.5 在简单有向图中,若在任何结点偶对中,至少从一个结点到另一个结点可达的,则称图G是单向(侧)连通的;
若在任何结点偶对中,两结点对互相可达,则称图G是强连通的;
若图G的底图,即在图G中略去边的方向,得到的无向图是连通的,则称图G是弱连通的.
显然,强连通的一定是单向连通和弱连通的,单向连通的一定是弱连通,但其逆均不真.
定理3.2.1 一个有向图是强连通的,当且仅当G中有一个回路,其至少包含每个结点一次.
单侧连通图判别法:若有向图G中存在一条经过每个结点至少一次的路,则G是单侧连通的。
答 A(有一条经过每个结点的回路)
问:上面的图中,哪个仅为弱连通的?
答:图(d)是仅为弱连通的
请大家要复习“弱连通”的概念.
8.设完全图K有n个结点(n2),m条边,当( )时,K中存在欧拉回路.
A.m为奇数 B.n为偶数
C.n为奇数 D.m为偶数
解 完全图K每个结点都是n1度的,由定理4.1.1的推论知K中存在欧拉回路的条件是n1是偶数,从而n为奇数。
答 C
提示:前面提到n阶无向完全图Kn的每个结点的度数是n-1,现在要问:无向完全图Kn的边数是多少?
答:n(n–1)/2
9.若G是一个汉密尔顿图,则G一定是( ).
A.平面图 B.对偶图
C.欧拉图 D.连通图
定义4.2.1 给定图G,若存在一条路经过图G的每个结点一次且仅一次,则该路称为汉密尔顿路;若存在一条回路经过图G的每个结点一次且仅一次,则该回路称为汉密尔顿回路;
具有汉密尔顿回路的图称为汉密尔顿图.
由定义可知,汉密尔顿图是连通图. 答 D
10.若G是一个欧拉图,则G一定是( ).
A.平面图 B.汉密尔顿图
C.连通图 D.对偶图
定义4.1.1给定无孤立结点图G,若存在一条路经过图G的每条边一次且仅一次,则该路称为欧拉路.(即,欧拉路中没有重复的边,并且包含了图中的每条边.)
若存在一条回路经过图G的每条边一次且仅一次,则该回路称为欧拉回路.
具有欧拉回路的图就称为欧拉图.
由定义可知,欧拉图是连通图. 答 C
11.设G是连通平面图,有v个结点,e条边,r个面,则r= ( ).
A.e-v+2 B.v+e-2
C.e-v-2 D.e+v+2
答 A(定理4.3.2:欧拉公式ver 2)
问:如果连通平面图G有4个结点,7条边,那么图G有几个面?
12.无向树T有8个结点,则T的边数为( ).
A.6 B.7 C.8 D.9 答 B
13.无向简单图G是棵树,当且仅当( ).
A.G连通且边数比结点数少1
B.G连通且结点数比边数少1
C.G的边数比结点数少1
D.G中没有回路.
答 A(定理5.1.1(树的等价定义))
14.已知一棵无向树T中有8个顶点,4度、3度、2度的分支点各一个,T的树叶数为( ).
A.8 B.5 C.4 D.3
解 这棵无向树T有7条边,所有结点的度数之和为14,而4度、3度、2度的分支点各一个共3个结点占用了9度,所以剩下的5个结点占用5度,即这5个结点每个都是1度结点,故有5片树叶.
答 B
15.设G是有n个结点,m条边的连通图,必须删去G的( )条边,才能确定G的一棵生成树.
A. B.
C. D.
答 A(n个结点的连通图的生成树有条边,必须删去条边)
16.设无向图G的邻接矩阵为
,
则G的边数为( ).
A.1 B.6 C.7 D.14 答 C
17.如图二(下图)所示,以下说法正确的是 ( ).
A.e是割点 B.{a, e}是点割集
C.{b, e}是点割集 D.{d}是点割集
图二
答 A
18.设有向图(a)、(b)、(c)与(d)如图六(下图)所示,则下列结论成立的是( ).
图六
A.(a)只是弱连通的 B.(b)只是弱连通的
C.(c)只是弱连通的 D.(d)只是弱连通的 答 D
19.无向完全图K4是( ).
A.欧拉图 B.汉密尔顿图 C.非平面图 D.树 答 B
20.以下结论正确的是( ).
A.无向完全图都是欧拉图
B.有n个结点n-1条边的无向图都是树
C.无向完全图都是平面图
D.树的每条边都是割边 答 D
二、填空题
1.已知图G中有1个1度结点,2个2度结点,3个3度结点,4个4度结点,则G的边数是 .
解 设G有x条边,则由握手定理,
,
答 15
2.设给定图G(如右由图所示),则图G的点割集是 .
解 从图G中删除结点f,得到的子图是不连通图,即结点集{f}是点割集;从图G中删除结点c和e,得到的子图是不连通图,而只删除c或e,得到的子图仍然是连通的,所以结点集{c, e}也是点割集.而其他结点集都不满足点割集的定义的集合,所以应该填写:{f}、{c, e}
答 {f}、{c,e}
提示:若f是图G的割点,则{f}是图G的点割集,删除f点后图G是连通吗?
3.设G是一个图,结点集合为V,边集合为E,则G的结点 等于边数的两倍.
答 的度数之和
4.无向图G存在欧拉回路,当且仅当G连通且 .
答 G的结点度数都是偶数(定理4.1.1的推论)
5.设G=<V,E>是具有n个结点的简单图,若在G中每一对结点度数之和大于等于 ,则在G中存在一条汉密尔顿路.
答 n1(定理4.2.2)
6.若图G=
7.设完全图K有n个结点(n2),m条边,当 时,K中存在欧拉回路.
答 n为奇数(同一、8题)
8.结点数v与边数e满足 关系的无向连通图就是树.
答 ev1(定理5.1.1(树的等价定义))
9.设图G是有6个结点的连通图,结点的总度数为18,则可从G中删去 条边后使之变成树.
解 由握手定理(定理3.1.1)知道图G有182=9 条边,又由定理5.1.1中给出的图T为树的等价定义之一是“图T连通且e=v-1”,可以知道图G的生成树有5条边,从而要删去4条边.
答 4
10.设正则5叉树的树叶数为17,则分支数为i = .答 4(定理5.2.1:(m-1)i=t-1)
三、判断说明题(判断下列各题,并说明理由.)
1.如果图G是无向图,且其结点度数均为偶数,则图G存在一条欧拉回路.
解 错误.
只有当G是连通图且其结点度数均为偶数时,图G才存在一条欧拉回路.
2.如下图所示的图G存在一条欧拉回路.
解 错误.
因为图G有两个奇数度(3度)结点,所以不存在欧拉回路.
注:这是一个汉密尔顿图,但不是欧拉图。可见汉密尔顿图不一定是欧拉图.
其实,欧拉图也不一定是汉密尔顿图.
如下图所示,图(1)是欧拉图又是汉密尔顿图,图(2)是欧拉图但不是汉密尔顿图,图(3)不是欧拉图但它是汉密尔顿图,图(4)不是欧拉图也不是汉密尔顿图。
3.如下图所示的图G不是欧拉图而是汉密尔顿图.
图G
解 正确.
图G有4个3度结点a,b,d,f,所以图G不是欧拉图.图G有汉密尔顿回路abefgdca,所以图G是汉密尔顿图.
4.设G是一个有7个结点16条边的连通简单图,则G为平面图.
解 错误.
由定理4.3.3知,若G有v个结点e条边,且v3,则e≤3v6.但本题中,16≤3×76不成立.
5.设G是一个连通平面图,且有6个结点11条边,则G有7个面.
解 正确.
由欧拉定理,连通平面图G的结点数为v,边数为e,面数为r,则ve+r=2.于是有r=2v+e=26+11=7.
问:“完全图K6是平面图”是否正确?
答 不正确.
因为完全图K6有6个结点15条边,且1536-6=12,即e 3v-6对K6不成立,所以K6不是平面图.
四、计算题
1.设G=<V,E>,V={ v1,v2,v3,v4,v5},E={ (v1,v3),(v2,v3),(v2,v4),(v3,v4),(v3,v5),(v4,v5) },试
(1) 给出G的图形表示; (2) 写出其邻接矩阵;
(3) 求出每个结点的度数; (4) 画出其补图的图形.
解 (1)G的图形为:
(2)图G的邻接矩阵为:
(3)图G的每个结点的度数为:
,,,,.
(4)由关于补图的定义3.1.9可知,先在图G补充边画出完全图(见下面左图),然后去掉原图的边,可得图G补图(见下面右图):
注意:补图中,如果没有标出结点v3,则是错的.
2.图G=<V, E>,其中V={ a, b, c, d, e},E={ (a, b), (a, c), (a, e), (b, d), (b, e), (c, e), (c, d), (d, e) },对应边的权值依次为2、1、2、3、6、1、4及5,试
(1)画出G的图形;
(2)写出G的邻接矩阵;
(3)求出G权最小的生成树及其权值.
解 (1)G的图形如左下图:
(2)G的邻接矩阵为:
(3)图G有5个结点,其生成树有4条边,用Kruskal算法求其权最小的生成树T:
第1步,取具最小权1的边(a,c);
第2步,取剩余边中具最小权1的边(c,e);
第3步,取剩余边中不与前2条边构成回路的具最小权2的边(a,b);
第4步,取剩余边中不与前3条边构成回路的具最小权3的边(b,d).
所求最小生成树T如下图,其权为.
注意:在用避圈法求最小的生成树的关键是:“取图中权数最小的边,且与前面取到的边不构成圈”,很多学生只注意到取权数最小的边了,而忽略了“不构成圈”的要求。
如果题目给出如解(1) 中所示赋权图,要求用Kruskal算法(避圈法)求出该赋权图的最小生成树,大家应该会吧.
3.已知带权图G如右图所示.
(1) 求图G的最小生成树;
(2)计算该生成树的权值.
解 (1)图G有6个结点,其生成树有5条边,用Kruskal算法求其权最小的生成树T:
第1步,取具最小权1的边;
第2步,取剩余边中具最小权2的边;
第3步,取剩余边中不与前2条边构成回路的具最小权3的边;
第4步,取剩余边中不与前3条边构成回路的具最小权5的边;
第5步,取剩余边中不与前4条边构成回路的具最小权7的边.
所求最小生成树T如右图.
(2)该最小生成树的权为
.
4.设有一组权为2, 3, 5, 7, 17, 31,试画出相应的最优二叉树,计算该最优二叉树的权.
解 (Huffman算法):
首先组合2+3,求带权5, 5, 7, 17, 31的最优二叉树;
再组合5+5,求带权7, 10, 17, 31的最优二叉树;
然后组合7+10,求带权17, 17, 31的最优二叉树;
继续组合17+17,求带权31, 34的最优二叉树;
最后组合31+34,得65,这是树根所带的权。
可从树根开始往下画,即得所求最优二叉树T如下图:
所求最优二叉树T的权为:
讲评:作业中最优二叉树往往都能画对了,但计算总权值时可能会把有些权的层数计算错了,导致总权值计算错误,大家一定要细心。
注意:这4个计算题的解题方法大家一定要掌握。
补充:教材第101页
例3 给定如图3.3.3所示有向图,其邻接矩阵以及邻接矩阵的乘积如下:
,
,
从上面的矩阵中可以得到一些结论,如:
(1)从A2中第1行第3列的为1可知,结点v1与v3之间有一条长度为2的路;
(2)从A3中第1行第2列的为2可知,v1与v2之间有2条长度为3的路;
(3)从A4中第2行第2列的为4可知,在结点v2有4条长度为4的回路.
如果改成问题:
试求:
(1)图G中结点v1与v3之间长度为2的路径条数; 1条
(2)图G中v1与v2之间长度为3的路径条数; 2条
(3)图G中经过v2的长度为4的回路条数. 4条
五、证明题
证明题同学一般都做不好,原因是对证明题方法没有掌握,也是对一些概念不清楚所造成的。因此,希望大家认真学习教材和老师讲课中的证明方法,并通过作业逐步掌握做证明题的方法。
1.设G是一个n阶无向简单图,n是大于等于3的奇数.证明图G与它的补图中的奇数度顶点个数相等.
证明 设,.则是由n阶无向完全图的边删去E所得到的.所以对于任意结点,u在G和中的度数之和等于u在中的度数.由于n是大于等于3的奇数,从而的每个结点都是偶数度的(度),于是若在G中是奇数度结点,则它在中也是奇数度结点.故图G与它的补图中的奇数度结点个数相等.
2.设连通图G有k个奇数度的结点,证明在图G中至少要添加条边才能使其成为欧拉图.
证明 由定理3.1.2知,k必为偶数.要使这k个奇数度结点变成偶数度结点,从而使图G变成欧拉图,可在每两个奇数度结点间添加一条边.故在图G中至少要添加条边才能使其成为欧拉图.