2024年电大离散数学图论部分期末复习辅导

离散数学图论部分期末复习辅导

-V单项选择题

1.设图G=<V,£>,veV,则下列结论成立的是().

A.deg(v)=2|E\B.deg(v)=|E\

C.Zdeg")=2|E|D.£deg3)=|E|

veVveV

解依照握手定理(图中所有结点的度数之和等于边数的两倍)知，答案C成立。

答c

2.设无向图G的邻接矩阵为

-01100_

10011

1000oJ

01001

01010

则G的边数为().

A.6B.5C.4D.3

解由邻接矩阵的定义知，无向图的邻接矩阵是对称的.即当结点口与均相邻时，结点

芍与力也相邻，因此连接结点力与芍的一条边在邻接矩阵的第i行第j列处和第j行

第i列处各有一个1,题中给出的邻接矩阵中共有1()个1,故有10+2=5条边。

答B

3.已知无向图G的邻接矩阵为

01011

10001

00011，

10101

11110

则6有（）.

A.5点，8边B.6点，7边

C.6点，8边D.5点，7边

解由邻接矩阵的定义知，矩阵是5阶方阵，因此图G有5个结点，矩阵元素有14个

1,144-2=7,图G有7条边。

答D

4.如图一所示，如下说法正确的是

（）•

A.｛（4,6）｝是割边

B.｛（«e）｝是边割集

C.｛（4,6）,伉。）｝是边割集

D.｛（d,e）｝是边割集

定义329设无向图为连通图，若有边集EiuE,使图G删除了El的所有边

后，所得的子图是不连通图，而删除了E的任何真子集后，所得的子图仍是连通图,

则称B是G的一个边割集.若边割集为单元集｛G｝,则称边e为割边（或桥）.

解割边首先是一条边，因为答案A中的是边集，不也许是割边，因此答案A是错误

的.删除答案B或C中的边后,得到的图是还是连通怪I,因此答案B、C也是错误的.在

图一中，删去(",e)边，图就不连通了，因此答案D正确.

答D

注：假如该题只给出图的结点和边，没有图示，大家也应当会做.如：

若图G=<V,E>,其中V=｛a,b,c,d,e),E=｛(«,/?),(a,c),(Q,e),(/?,c),(b,e),(c,e),(e,

t/)｝，则该图中的割边是什么？

5.图G如图二所示，如下说法正确的是().

A.a是割点力

B.｛b,c｝是点割集

C.｛44｝是点割集图二

D.｛c｝是点割集

定义327设无向图G=vV,E>为连通图，若有点集《uV,使图G删除了5的所有结

点后，所得的子图是不连通图，而删除了看的任何真子集后，所得的子图仍是连通

图，则称《是G的一个点割集.若点割集为单元集｛□｝,则称结点u为割点.

解在图二中，删去结点。或删去结点。或删去结点。和"图还是连通的，困此答案A、

C、D是错误的.在图二中删除结点。和如得到的子图是不连通图，而只删除结点〃

或结点c,得到的子图仍然是连通的，由定义能够懂得，｛仇c｝是点割集.因此答案B

是正确的.

答B

6.图G如图三所示，如二说法正确的是

)•

A.｛(〃,")｝是割边

B.｛Q切是边割集

C.{(a,d),(b,d)}是边割集

D.｛S,4｝是边割集

解割边首先是一条边，｛(。，〃)｝是边集，不也许是割边.在图三中，删除答案B或D

中的边后，得到的图是还是连通图.因此答案A、B、D是错误的.在图三中，删去

(«d)边和S,d)边，图就不连通了，而只是删除(qd)边或出,①边，图还是连通的，因

此答案C正确.

7.设有向图(〃)、(b)、(c)与(、d)如图四所示，则下列结论成立的是().

图四

A.(a)是强连通的B.(b)是强连通的

C.(c)是强连通的D.(d)是强连通的

复习：定义3.2.5在简单有向图中，若在任何结点偶对中,最少从一个结点到另一个

结点可达的，则称图G是单向(侧)连通的;

若在任何结点偶对中，两结点对相互可达，则称图G是强连通的；

若图G的底图，即在图G中略去边的方向，得到的无向图是连通的，则称图G是弱连

通的.

显然，强连通的一定是单向连通和弱连通的，单向连通的一定是弱连通，但其逆均不

真.

定理321一个有向图是强连通的，当且仅当G中有一个回路，其最少包括每个结点

一次.

单侧连通图判别法：若有向图G中存在一条通过每个结点最少一次的路，则G是单侧

连通的。

答A（有一条通过每个结点的回路）

问：上面的图中，哪个仅为弱连通的？

答：图（d）是仅为弱连通的

请大家要复习“弱连通”的概念.

8.设完全图K〃有〃个结点（应2）,小条边，当（）时，K”中存在欧拉回路.

A.阳为奇数B.几为偶数

C.n为奇数D.m为偶数

解完全图K.每个结点都是度的，由定理4.1.1的推论知K”中存在欧拉回路的条

件是〃-1是偶数，从而〃为奇数。

答C

提示：前面提到〃阶无向完全图瓦〃的每个结点的度数是〃T,目前要问：无向完全图

K〃的边数是多少？

答：n（n-1）/2

9.若G是一个汉密尔顿图，则G一定是（）.

A.平面图B.对偶图

C.欧拉图D.连通图

定义4.2.1给定图G,若存在一条路通过图G的每个结点一次且仅一次，贝J该路称为汉

密尔顿路；若存在一条回路通过图G的每个结点一次且仅一次，则该回路称为汉密尔

顿回路；

具备汉密尔顿回路的图称为汉密尔顿图.

由定义可知，汉密尔顿图是连通图.答D

10.若G是一个欧拉图，则G一定是（）.

A.平面图B.汉密尔顿图

C.连通图D.对偶图

定义4.L1给定无孤立结点图G,若存在一条路通过图G的每条边一次且仅一次，则

该路称为欧拉路.（即，欧拉路中没有重复的边，并且包括了图中的每条边.）

若存在一条回路通过图G的每条边一次且仅一次，则该回路称为欧拉回路.

具备欧拉回路的图就称为欧拉图.

由定义可知，欧拉图是连通图.答C

11.设G是连通平面图，有U个结点，e条边，，•个面，则（）.

A.e—v+2B.v+e~2

C.e-v—2D.e+u+2

答A（定理4.3.2：欧拉公式u-e+r=2）

问：假如连通平面图G有4个结点，7条边，那么图G有几个面？

12.无向树了有8个结点，则r的边数为（）.

A.6B.7C.8D.9答B

13.无向简单图G是棵树，当且仅当（）.

A.G连通且边数比结点数少1

B.G连通且结点数比边数少1

C.G的边数比结点数少1

D.G中没有回路.

答A（定理5.L1（树的等价定义））

14.已知-一棵无向树7中有8个顶点,4度、3度、2度的分支点各一个，7的树叶数

为（）・

A.8B.5C.4D.3

解这棵无向树了有7条边，所有结点的度数之和为14,而4度、3度、2度的分支点

各一个共3个结点占用了9度，因此剩余的5个结点占用5度，即这5个结点每个都

是1度结点，故有5片树叶.

答B

15.设G是有〃个结点，〃”条边的连通图，必须删去6的（）条边，才能确定G的

一棵生成树.

A.m-n+\B.m-n

C.m+n+\D./2-m+l

答A（〃个结点的连通图的生成树有,7-1条边，必须删去6-5-1）条边）

16.设无向图G的邻接矩阵为

o111r

10011

10000’

11001

11010

则G的边数为（）.

A.1B.6C.7D.14答C

17.如图二（下图）所示，如下说法正确的是（）.

A.e是割点B.是点割集

C.g,e｝是点割集D.｛矶是点割集

aP

图二

答A

18.设有向图(〃)、(〃)、(c)与(d)如图六(下图)所示，则下列结论成立的是().

图六

A.(〃)只是弱连通的B.(/?)只是弱连通的

C.(c)只是弱连通的D.(d)只是弱连通的答D

19.无向完全图K是().

A.欧拉图B.汉密尔顿图C.非平面图D.树答B

20.如下结论正确的是().

A.无向完全图都是欧拉图

B.有〃个结点〃一1条边的无向图都是树

C.无向完全图都是平面图

D.树的每条边都是割边答D

二、填空题

1.已知图G中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G

的边数是.

解设G有x条边，则由握手定理，

1x14-2x2+3x34-4x4=2A:,X=15

答15

2是.--设--给--定--图--G--（-如--右--由--图-所示），则图G的点割集八日Ab

解从图G中删除结点/,得到的子图是不连通图，cJd

即结点集6是点割集；从图G中删除结点。和e,得到的子图是不连通图，而只删除

c或e,得到的子图仍然是连通的，因此结点集｛c“｝也是点割集.而其他结点集都不

满足点割集的定义的集合，因此应当填写：仍、｛c,e｝

答｛小｛c,e｝

提示：若/是图G的割点，则｛/｝是图G的点割集，删除了点后图G是连通吗？

3.设G是一个图，结点集合为V,边集合为E,则G的结点等于边

数的两倍.

答的度数之和

4.无向图G存在欧拉回路，当且仅当G连通且.

答G的结点度数都是偶数（定理4.1.1的推论）

5.设G=〈匕£＞是具备〃个结点的简单图，若在G中每一对结点度数之和不小于等

于，则在G中存在一条汉密尔顿路.

答＞1-1（定理4.2.2）

6.若图G=＜V,中具备一条汉密尔顿回路，则对于结点集V的每个非空子集S,在

G中删除S中的所有结点得到的连通分支数为W，则S中结点数|S|与W满足的关系

式为.答W4|S|（定理4.2.1）

7.设完全图K〃有〃个结点（应2）,根条边，当时，K〃中存在欧拉回路.

答n为奇数（同一、8题）

8.结点数u与边数e满足关系的无向连通图就是树.

答e=v-l（定理5.1.1（树的等价定义））

9.设图G是有6个结点的连通图，结点的总度数为18,则可从G中删去条边

后使之变成树.

解由握手定理（定理懂得图G有18+2=9条边，又由定理5.L1中给出的图7

为树的等价定义之一是“图丁连通且e=v-lf\能够懂得图G的生成树有5条边，从

而要删去4条边.

答4

10.设正则5叉树的树叶数为17,则分支数为i=.答4（定理5.2.1：（m-l）i=t-l）

三、判断阐明题（判断下列各题，并阐明理由.）

1.假如图G是无向图，且其结点度数均为偶数，则图G存在一条欧拉回路.

解错误.

只有当G是连通图且其结点度数均为偶数时，图G才存在一条欧拉回路.

2.如下图所示的图G存在一条欧拉回路.

cd

解错误.

因为图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为平面图.

解错误.

由定理433知，若G有v个结点e条边，且亚3,贝lje03v-6.但本题中，16S3X7-6

不成立.

5.设G是一个连通平面图，且有6个结点11条边，则G有7个面.

解正确.

由欧拉定理，连通平面图G的结点数为v,边数为e,面数为r,则v-e+r=2.于是有

r=2-v+e=2-6+ll=7.

问：“完全图K6是平面图”是否正确?

答不正确.

因为完全图K6有6个结点15条边，且1523x6-6=12,即eW3止6对K不成立，因此

心不是平面图.

四、计算题

1.设G=VKE>,V=｛VI,V2,V3,V4,V5）,E=｛（VI,V3）,（V2,V3）,（V2,V4）,（V3,V4）,（V3,V5）,

（V4,V5）｝，试

(1)给出G的图形表示;(2)写出其邻接矩阵;

(3)求出每个结点的度数;(4)画出其补图的图形.

解(DG的图形为:

玲匕

图G

(2)图G的邻接矩阵为:

「00100、

00110

A=11011

01101

,00110；

(3)图G的每个结点的度数为：

deg(匕)=1deg(v2)=2deg(匕)=4deg(v4)=3deg(匕)=2

(4)由有关补图的定义3.1.9可知，先在图G补充边画出完全图(见下面左图)，然

后去掉原图的边，可得图G补图(见下面右图)：

注意:

2.图G=<V9E>,其中V={a,b9c,d,e],E={(a,/?),(a,c)9(a,e)9(b,d),(b,e)f(c9e)9(c9d),

(d,e)},对应边的权值依次为2、1、2、3、6、1、4及5,试

(1)画出G的图形;

(2)写出G的邻接矩阵;

(3)求出G权最小的生成树及其权值.

解(1)G的图形如左下图:

1

b

6

3

d5

(2)G的邻接矩阵为:

「0110P

i0011

A=10011

01101

J、1I10?

(3)图G有5个结点,其生成树有4条边，用Kruskal算法求其权最小的生成树T：

第1步，取具最小权1的边

第2步，取剩余边中具最小权1的边(c,e)；

第3步，取剩余边中不与前2条边组成回路的具最小权2的边(a,b)；

第4步，取剩余边中不与前3条边组成回路的具最小权3的边(b,d).

所求最小生成树T如下图，其权为卬(乃=1+1+2+3=7.

注意：在用避圈法求最小的生成树的核心是：“取图中权数最小的边，且与前面取到的

边不组成圈”，诸多学生只注意到取权数最小的边了，而忽视了“不组成圈”的要求。

假如题目给出如解(1)中所示赋权图，要求用Kruskal算法(避圈法)求出该赋权图的

最小生成树，大家应当会吧.

3.已知带权图G如右图所示.

(1)求图G的最小生成树;

47机/3

⑵计算该生成树的权值.

解(1)图G有6个结点，其生成树有5条边，用Kruskal算法求其权最小的生成树

T：

第1步，取具最小权1的边；

第2步，取剩余边中具最小权2的边；

第3步，取剩余边中不与前2条边组成回路的具最小权3的边；

第4步，取剩余边中不与前3条边组成回路的具最小权5的边；

第5步,取剩余边中不与前4条边组成回路的具△

最小权7的边.

所求最小生成树T如右图.

(2)该最小生成树的权为

W(T)=l+2+3+5+7=18

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的权为：

以7)=(2+3)x5+5x4+7x3+17x2+31x1=131

讲评：作业中最优二叉树往往都能画对了，但计算总权值时也许会把有些权的层数计

算错了，导致总权值计算错误，大家一定要细心。

注意：这4个计算题的解题措施大家一定要掌握。

补充：教材第101页

例3给定如图333所示有向图，其邻接矩阵以及邻接矩阵的乘积如下:

V1

V4

图3.3.3例3图

0100010100

1010002000

A=01000,A2=10100

0000100010

0001000001

-02000--20200

2