2025年离散数学图论部分综合练习辅导

离散数学图论部分综合练习辅导

本次活动是本学期的第二次活动(.11.18),重要是针对第二单元图论的重点

学习内容进行辅导，方式是通过讲解某些经典的综合练习题目，协助大家深入

理解和掌握图论的基本概念和措施。

图论作为离散数学的一部分，重要简介图论的基本概念、理论与措施。教

学内容重要有图的基本概念与结论、图的连通性与连通度、图的矩阵表达、最

短路问题、欧拉图与汉密尔顿图、平面图、对偶图与着色、树与生成树、根树

及其应用等。

本次综合练习重要是复习这一部分的重要概念与计算措施，与集合论同

样，也安排了五种类型，有单项选择题、填空题，判断阐明题、计算题、证明

题。这样的安排也是为了让同学们熟悉期末考试的题型，可以很好地完毕这一

部分重要内容的学习。下面分别讲解。

一、单项选择题

1.设图G的邻接矩即为

00

000

000

000

00

则G的边数为().

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

对的答案：D

上学期的作业中，有的同学选择答案B。重要是对邻接矩阵的概念理解不

到位。我们复习定义：

定义331设G=<V,£>是一种简朴图，其中g{也.vs.….■},则〃阶方阵4

(G)二(劭)称为G的邻接矩阵.其中各元素

1匕与匕相邻

0匕与〃不相邻或

而当给定的简朴图是无向图时，邻接矩阵为对称的.即当结点必•与力相邻

时，结点学与口也相邻，因此连接结点打与0的一条边在邻接矩阵的第i行第/•列处

和第/行第i列处各有一种1，题中给出的邻接矩阵中共有8个1,故有8+2=4条

边。

2.设图G=vV,E>,则下列结论成立的是().

A.deg(V)=21E\B.deg(V)=|E\

C.^deg(v)=2|E|D.^deg(v)=|E|

对的答案：C

该题重要是检查大家对握手定理掌握的状况。复习握手定理:

定理3.1.1设G是一种图，其结点集合为V,边集合为E,则

Xdeg（v）=2|E|

3.图G如右图所示，如下说法对的的是（）.

A.｛（a,或｝是割边

B.｛（〃,"）｝是边割集

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

D.｛（〃,"）,（《c）｝是边割集

对的答案：C

上学期许多同学选择答案A。重要是对割边、边

割集的概念理解不到位。复习割边、边割集的定义:

定义329设无向图G=<V,E>为连通图，若有边集EiuE,使图G删除了B

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

图是连通图，则称©是G的一种边割集.若某个边构成一种边割集，则称该

边为割边（或桥）

假如答案A对的，即删除边3,后，得到的图是不连通图，但实际上它还

是连通的。因此答案A是错误的。

4.设G是连通平面图，有u个结点，e条边，/•个面，则厂（）.

A.e—v+2B.v+e—2C.e-v~2D.e+v+2

对的答案：A

该题重要是检查大家对平面图的欧拉定理的理解状况。

定理4.3.2（欧拉定理）设连通平面图G的结点数为口边数为e,面数为八

则下列欧拉公式成立.

v-e+r=2

5.无向图G存在欧拉通路，当且仅当（）.

A.G中所有结点的度数全为偶数

B.G中至多有两个奇数度结点

C.G连通且所有结点的度数全为偶数

D.G连通且至多有两个奇数度结点

对的答案：D

上学期许多同学选择答案C。重要是将题中的“欧拉通路”误认为“欧拉

回路”了。其实应当运用定理4.1.1进行选择，才是对的的。复习定义和定

理：

定义4.1.1给定无孤立结点图G,若存在一条路通过图G的每条边一次且

仅一次，则该路称为欧拉路；

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

定理4.1.1无向图G具有一条欧拉路，当且仅当G是连通的，且有零个或

2个奇数度数的结点.

推论一种无向图具有一条欧拉回路，当且仅当该图是连通的，并且它的

结点度数都是偶数.

因此，对的答案应当是D.

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

定G的一棵生成树.

A.m—n+\B.in-nC.m+/?4-1D.n—m+\

对的答案：A

上学期许多同学选择答案D。重要是把定理5.1.1给出的图7为树的等价

定义之一是图7连通且右厂1中的公式用错了.大家只要把〃，代入公式e=vl

中的e,把〃代入公式中的也可以懂得答案A是对的。

定理5.1.1给定图八则如下有关图7为树的定义等价.

（1）无回路的连通图.

（2）无回路且其中e是边数，u是顶点数.

（3）连通且e=wl.

（4）无回路，但增长任一新边，得到且仅得到一种回路.

（5）连通，但删去任一边后图便不连通.C22）

（6）每一对顶点之间有且仅有一条路.C22）

定理5.1.1的六个等价定义，大家应当熟记的.最重要的是：无向简朴图G是棵

树，当且仅当G连通且边数比结点数少1.

二、填空题

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

点，则G的边数是.

应当填写：15

重要检查大家对握手定理掌握的状况。

定理3.L1（握手定理）设G是一种图，其结点集合为匕边集合为E,则

Xdeg（v）=2|E|

由于图G中有1个1度结点，2个2度结点，3个3度结点，4个4度结

点，即Zdeg"）=lxl+2x2+3x3+4x4=30,因此边数有闽=30/2=15。

veV

问：若无向树丁中有8个结点，4度，3度，2度的分、X

支点各一种，那么丁的树叶数为多少？\/

2.设给定图G（如右图所示），则图G的点割集是/V--L

应当填写：｛力，[c,e]

上学期许多同学填错答案重要对点割集的概念理解

不对的。

定义327设无向图G=<V,E>为连通图，若有点集Viu匕使图G删除了H的

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

图是连通图，则称□是G的一种点割集.若某个结点构成一种点割集，则称该

结点为割点.

‘、,上学向许多同学填写的｛/，c｝，重要是没有完全理解定义3.2.7,由于｛力是

｛/，c｝的真了集，而删除｛/）后，图是不连通的。

3.设无向图G=<V,£>是汉密尔顿图，则丫的任意非空子集0,均有

<1Vi|.

应当填写：W（G-0）

由于具有汉密尔顿回路的图称为汉密尔顿图.而由

定理4.2.1若图G=<V,E>中具有一条汉密尔顿回路，则对于结点集V的每个

非空子集S均有W（G-S殍⑸成立，其中W（G-0是（G-S）中连通分支数.

因此应当填写：W（G-Vi）.

4.设有向图。为欧拉图，则图。中每个结点的入度.

应当填写：等于出度

假如大家记住“具有欧拉回路的图称为欧拉图”和定理4.L2:一种有向图具

有单向欧拉回路，当且仅当它是连通的，且每个结点的入度等于出度.大家一

定能填写出对的答案的。

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

路.

应当填写：〃为奇数

上学期许多同学填错答案重要对完全图的概念理解不对的。

定义3.1.6简朴图G=<V,E>中，若每一对结点间均有边相连，则称该图为

完全图.有〃个结点的无向完全图记为K”.

由定义可知，完全图K“中的任一结点u到其他结点均有一条边，共有〃-1

条边，即每个结点的度数是当〃为奇数时，〃-1为偶数。

由定理4.1.1的推论可知，应当填写：〃为奇数。

6.给定一种序列集合｛1,01,10,11,001.000｝,若去掉其中的元

素—，则该序列集合构成前缀码.

应当填写：1

由于在二进制中1是10和11的前缀。而前缀码的定义是（定义5.2.10）：给

定一种序列集合，若没有一种序列是另一种序列的前缀，该序列集合称为前缀

码.

填写该题答案时大家一定要对前缀码的定义理解非常清晰。

问：若把序列集合中的1换成0,应当去掉哪个元素？

三、判断阐明题

1.给定两个图Gi,G2（如下图所示）：

（1）试判断它们与否为欧拉图、汉密尔顿图？并阐明理由.

（2）若是欧拉图，请写出一条欧拉回路.

分析：先复习欧拉图的鉴别定理和汉密尔顿图的定义：

定理4.1.1的推论：一种无向图具有一条欧江回路，当且仅当该图是连通

的，并且它的结点度数都是偶数.

定义4.2.1：若存在一条回路通过图G的每个结点一次且仅一次，则该回

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

解，（1）图Gi是欧拉图.

由于图Gi中每个结点的度数都是偶数.

图G是汉密尔顿图.

由于图G2存在一条汉密尔顿回路（不惟一）：

）

a（a,b）b（b,e）e（e,f）f（f,gg（g,d）d（d,c）c（cfd\a

问题：请大家想一想，为何图G不是汉密尔顿图，图G不是欧拉图。

（2）图3的欧拉回路为：（不惟一）：

Vl（vi,V2）V2（V2.V3）V3（V3.V4）V4（V4.V5）V5（V5.V2）V2（V2.V6）V6（V6.V4）V4（V4,V|）V|

（上学期的学生在书写欧拉回路时不规范，大家要按照对的的措施写法。）

2.鉴别图G（如右图所示）是不是平面图，

并阐明理由.

分析：平面图的定义是

定义4.3.1设G=<V,是一种无向图，

假如能把G的所有结点与边画在平面上，并且

使得任何两条边除端点外没有其他的交点，则

称G是一种平面图（也称可平面图）.

显然平面图的边与边只在结点处相交.

解：图G是平面图.

由于只要把结点也与姑6的连线（V2,附拽

到结点VI的外面，把把结点火与此的连线

（V3,咐拽到结点V4,V5的外面，就得到一种平

面图.

注意：定理4.3.3设G是一种有U个结点e条边

的连通简朴平面图，若叱3,则处3斤6.

会用于判断不是平面图。

四、计算题

1.设图G=<V,E>,其中心{。1,。2,。3,。4,⑹,

E={<a\,<42,44〉,<43,0>,<44,45>,<。5,。2>}

(1)试给出G的图形表达；

(2)求G的邻接矩阵;

(3)判断图G是强连通图、单侧连通图还是弱连通图？

解：(1)图G是有向图:(2)邻接矩阵如下:

0100o-

00010

A(D)=10000,

00001

01000

(3)图G是单侧连通图，也是弱连通图.

有关强连通图、单侧连通图还是弱连通图的判断，但愿大家掌握图论综合作业

单项选择题中的第4题。

2.fflG=<V,E>,其中V={〃，/?,c,d,ej},E={(a,b),(a,c),(a,e),(b,J),(/>,

e),(c,e),(d,e),(&力,(e,/)},对应边的权值依次为5,2,1,2,6,1,9,3及

8.

(I)画出G的图形；

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

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

解：(1)由于仁{〃,Z?,c,d,ej}

E={(a,b),(a,c)9(a,e),(b,d),(b,e)9

(c,e),(d,

权值依次为5,2,1,2,6,1,9,3及8

因此，G的图形如右图所示：

(2)分析：定义3.3.1设G=<K皮>是一种简朴图，其中小…,

Vn},贝IJ〃阶方阵4G)=侬)称为G的邻接矩阵.其中

1匕与巳相邻

"0匕.与匕不相邻或i=j.

011010

100110

100010

邻接矩阵：

01001i

111101

000110

1

d

13

(3)用避圈法:

第1步：选(a,e)和(c,e)边;

第2步：选S,J)边；(为何不选(〃“)？)

第3步：选(",./)边；

第4步：选3,份边.

这样，得到了最小的生成树，如右图中粗线所示.

最小的生成树的权为1+1+5+2+3=12.

上学期作业中的最小的生成树求的不对，重要是没有把握“取权数最小的边,

且与前面取到的边不构成圈”，常常是只注意取权数最小的边了，而忽视“不

构成圈”的规定。

问：假如结点集是V={a,b,c,d,e),边集E={(a,/?),(〃,c),3e),(仇d),S,e)9(c,

e),(d,e)},对应边的权值依次为5,2,1,2,6,1,9,那么会求吗？

3.设有一组权为2,3,5,7,11,13,17,19,23,29,31,试

(1)画出对应的最优二叉树；

(2)计算它们的权值.

解：(1)最优二叉树如右图所示：

措施(Huffman)：从2,3,5,7,11,13,17

,19,23,29,31中选2,3为最低层结点，并

从权数中删去，再添.上他们的和数，即

5,5711,13,17,19,23,29,31；

再从5,5,7/1,13,17,19,23,29,31中选

5,5为倒数第2层结点，并从上述数列中

删去，再添上他们的和数，即7,10』1』3,

17,19,23,29,31;

然后，从7,10,11,13,17,19,23,29,31中选7,10和11,13为倒数第3层结点，并

从上述数列中删去，再添上他们的和数,即17,17,24,19,23,29,31；

(2)权值为：

2x64-3x6+5x5+7x4+11x4+13x4+17x3+19x3+23x3+29x3+31x2

=12+18+25+28+444-52+51+57+69+87+62=505

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

了，导致总权值计算错误。

问：假如一组权为2,3,6,9,13,15,能否画出最优二叉树？

五、证明题

证明题上学期的学生做的很不好，原因是他们对证明题措施没有掌握，也

是对某些概念不清晰所导致的。因