当前位置：文档库 › 离散数学图论答案

离散数学图论答案

【篇一：离散数学图论习题】

综合练习

一、单项选择题

1．设l是n阶无向图g上的一条通路，则下面命题为假的是( )． (a) l可以不是简单路径，而是基本路径 (b) l可以既是简单路径,又是基

本路径 (c) l可以既不是简单路径，又不是基本路径 (d) l可以是简单路径，而不是基本路径答案：a

2．下列定义正确的是( )．

(a) 含平行边或环的图称为多重图(b) 不含平行边或环的图称为简单

图 (c) 含平行边和环的图称为多重图(d) 不含平行边和环的图称为简

单图答案：d

3．以下结论正确是 ( )．

(a) 仅有一个孤立结点构成的图是零图 (b) 无向完全图kn每个结点

的度数是n (c) 有n(n1)个孤立结点构成的图是平凡图(d) 图中的基本回路都是简单回路答案：d

4．下列数组中，不能构成无向图的度数列的数组是( )． (a)

(1,1,1,2,3) (b) (1,2,3,4,5) (c) (2,2,2,2,2) (d) (1,3,3,3) 答案：b

5．下列数组能构成简单图的是( )． (a) (0,1,2,3)(b) (2,3,3,3)(c) (3,3,3,3)(d) (4,2,3,3) 答案：c

6．无向完全图k3的不同构的生成子图的个数为（）． (a) 6 (b)

5(c) 4 (d) 3 答案：c

7．n阶无向完全图kn中的边数为（）．

(a)

n(n?1)n(n?1)

(b) (c) n (d)n(n+1) 22

答案：b

8．以下命题正确的是( )．

(a) n(n?1)阶完全图kn都是欧拉图(b) n(n?1)阶完全图kn都是哈密顿图

10．下列结论不正确是( )．

(a) 无向连通图g是欧拉图的充分必要条件是g不含奇数度结点

(b) 无向连通图g有欧拉路的充分必要条件是g最多有两个奇数度结点 (c) 有向连通图d是欧拉图的充分必要条件是d的每个结点的入度等于出度

(d) 有向连通图d有有向欧拉路的充分必要条件是除两个结点外，每个结点的入度等

于出度答案：d

11．无向完全图k4是（）．

（a）欧拉图（b）哈密顿图（c）树答案：b

12．有4个结点的非同构的无向树有 ( )个．

(a) 2 (b) 3(c) 4(d) 5 答案：a

13．设g是有n个结点，m条边的连通图，必须删去g的( )条边，才能确定g的一棵生成树．

(a) m?n?1 (b) n?m (c) m?n?1 (d) n?m?1 答案：a

14．设g是有6个结点的完全图，从g中删去( )条边，则得到树． (a) 6 (b) 9 (c) 10 (d) 15 答案：c

二、填空题

1．数组{1，2，3，4，4}是一个能构成无向简单图的度数序列，此命题的真值是 . 答案：0

2．无向完全图k3的所有非同构生成子图有个．答案：4

3．设图g??v,e?，其中?v??n,?e??m．则图g是树当且仅当g是连通的，且m?．答案：n－1

4．连通图g是欧拉图的充分必要条件是答案：图g无奇数度结点 5．连通无向图g有6个顶点9条边，从g中删去g的一棵生成树t．答案：4

6．无向图g为欧拉图，当且仅当g是连通的，且g中无答案：奇数度

7．设图g??v,e?是简单图，若图中每对结点的度数之和，则g一定是哈密顿图．答案：?

8．如图1所示带权图中最小生成树的权是．

答案：12

三、化简解答题

1．设无向图g＝v,e，v={v1，v2，v3，v4，v5，v6}， e={( v1，v2), ( v2，v2), ( v4，v5), ( v3，v4), ( v1，v3),

( v3，v1), ( v2，v4)}． (1) 画出图g的图形；

图1

图2

(2) 写出结点v2, v4，v6的度数； (3) 判断图g是简单图还是多重图．解：(1) 图g的图形如图5所示．

(2) deg(v2)?4,deg(v4)?3,deg(v6)?0．

(3) 图g是多重图．作图如图2. 2．设图g＝v，e，其中

v＝{a,b,c,d,e}, e={(a,b),(b,c),(c,d), (a,e)}

试作出图g的图形，并指出图g是简单图还是多

重图？是连通图吗？说明理由.b e

解：图g如图8所示．. 图g中既无环，也无平行边，是简单

图． cd 图g是连通图．g中任意两点都连通.

图3

所以，图g有9个结点．作图如图3．

四、计算题

1．设简单连通无向图g有12条边，g中有2个1度结点，2个2

度结点，3个4度结点，其余结点度数为3．求g中有多少个结

点．试作一个满足该条件的简单无向图．

解：设图g有x个结点，由握手定理

2?1+2?2+3?4+3?（x?2?2?3）＝12?2

3x?24?21?18?27x＝9 故图g有9个结点．图4

满足该条件的简单无向图如图4所示

2．设图g(如图5表示)是6个结点a,b,c, d,e,f

的图，试求，图g的最小生成树，并计算它的权．

c 解：构造连通无圈的图，即最小生成树，用

克鲁斯克尔算法：

第一步：取ab＝1；第二步：取af=4第三步：取fe＝3；第四步：取ad=9图5 第五步：取bc=23

如图6．权为1+4+3+9+23=40

3．一棵树t有两个2度顶点，1个3度顶点；3个4

问它有几片树叶？

解：设t有n顶点，则有n－1条边．t中有2个 2度顶点，1个3

度顶点，3个4度顶点，其余n－2－1-3个1度顶

点．

五、证明题

1．若无向图g中只有两个奇数度结点，则这两个结点一定是连通的．证：用反证法．设g中的两个奇数度结点分别为u和v．假若u和

v不连通．

即它们之间无任何通路，则g至少有两个连通分支g1，g2，且u

和v分别属于g1和g2，于是g1和g2各含有一个奇数度结点．这

与握手定理的推论矛盾．因而u和v一定是连通的．

【篇二：离散数学图论练习题】

题

1、设g是一个哈密尔顿图，则g一定是()。 (1) 欧拉图 (2) 树 (3)

平面图(4) 连通图 2、下面给出的集合中，哪一个是前缀码？( ) (1) {0，10，110，101111}(2) {01，001，000，1} (3) {b，c，aa，ab，aba} (4) {1，11，101，001，0011} 3、一个图的哈密尔顿路是一条

通过图中( )的路。 4、设g是一棵树，则g 的生成树有( )棵。 (1) 0 (2) 1 (3) 2 (4) 不能确定

5、n阶无向完全图kn 的边数是( )，每个结点的度数是( )。

6、一

棵无向树的顶点数n与边数m关系是( )。 7、一个图的欧拉回路是

一条通过图中( )的回路。8、有n个结点的树，其结点度数之和是()。

9、下面给出的集合中，哪一个不是前缀码( )。 (1) {a，ab，110，

a1b11}(2) {01，001，000，1} (3) {1，2，00，01，0210} (4) {12，11，101，002，0011}

10、n个结点的有向完全图边数是( )，每个结点的度数是( )。 11、

一个无向图有生成树的充分必要条件是( )。 12、设g是一棵树，

n,m分别表示顶点数和边数，则 (1) n=m (2) m=n+1 (3) n=m+1 (4)

不能确定。

13、设t=〈v,e〉是一棵树，若|v|1，则t中至少存在( )片树叶。

14、任何连通无向图g至少有( )棵生成树，当且仅当g 是()，g的

生成树只有一棵。

15、设g是有n个结点m条边的连通平面图，且有k个面，则k

等于: (1) m-n+2 (2) n-m-2 (3) n+m-2 (4) m+n+2。 16、设t是一棵树，则t是一个连通且( )图。

17、设无向图g有16条边且每个顶点的度数都是2，则图g有()个

顶点。

(1) 10(2) 4(3) 8 (4) 16

18、设无向图g有18条边且每个顶点的度数都是3，则图g有()个

顶点。(1) 10(2) 4(3) 8 (4) 12

19、任一有向图中，度数为奇数的结点有()个。

20、具有6 个顶点，12条边的连通简单平面图中，每个面都是由( )条边围成？ (1) 2 (2) 4 (3) 3 (4) 5

21、在有n个顶点的连通图中，其边数（）。 (1) 最多有n-1条 (2) 至少有n-1 条 (3) 最多有n条 (4) 至少有n 条

22、一棵树有2个2度顶点，1 个3度顶点，3个4度顶点，则其

1度顶点为（(1) 5 (2) 7 (3) 8(4) 9

23、若一棵完全二元（叉）树有2n-1个顶点，则它（）片树叶。(1) n (2) 2n (3) n-1(4) 2 24、下列哪一种图不一定是树（）。

(1) 无简单回路的连通图 (2) 有n个顶点n-1条边的连通图 (3) 每对顶点间都有通路的图 (4) 连通但删去一条边便不连通的图 25、连通

图g是一棵树当且仅当g中（）。 (1) 有些边是割边 (2) 每条边都

是割边

(3) 所有边都不是割边(4) 图中存在一条欧拉路径26．对于无向图，下列说法中（）是正确的. a．不含平行边及环的图称为完全图

b．任何两个不同结点都有边相连且无平行边及环的图称为完全图c．具有经过每条边一次且仅一次回路的图称为哈密尔顿图 d．具有

经过每个结点一次且仅一次回路的图称为欧拉图

27．设图g的邻接矩阵为

??0

0100?

?00011?

??10000??

?01001?

???01010??

则g的边数为( )．

a．5b．6c．3d．4 28．设图g＝v, e，则下列结论成立的是 ( )．

a．deg(v)=2?e?b．deg(v)=?e?

）。

c．

?deg(v)?2e d．?deg(v)?e

v?v

29．图g如右图所示，以下说法正确的是 ( ) ．

a．{(a, d)}是割边 b．{(a, d)}是边割集 c．{(d, e)}是边割集

d．{(a, d) ,(a, c)}是边割集

30．设g是连通平面图，有v个结点，e条边，r个面，则r= ( )．

a．e－v＋2b．v＋e－2c．e－v－2d．e＋v＋2 31．无向图g存在

欧拉通路，当且仅当( )．

a．g中所有结点的度数全为偶数 b．g中至多有两个奇数度结点c．g连通且所有结点的度数全为偶数 d．g连通且至多有两个奇数

度结点

二、填空题

1．已知图g中有1个1度结点，2个2度结点，3个3度结点，4

个4度结点，则g的边数是．

2．设给定图g(如右图所示)，则图g的点割集是．

3．设无向图g＝v, e是汉密尔顿图，则v的任意非空子集v1，都

有 ??v1?．

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

5．设完全图kn有n个结点(n?2)，m条边，当时，kn中存在欧拉

回路．

6．给定一个序列集合{1，01，10，11，001，000}，若去掉其中的

元素合构成前缀码．

e d

a ?d b

f c

三、计算题

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是强连通图、单侧连通图还是弱连通图？

2．图g=v, e，其中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的邻接矩阵；

a 2 c

5 6

2 d

（3）求出g权最小的生成树及其权值．

问：如果结点集是v={a, b, c, d, e }，边集e={ (a, b), (a, c), (a, e), (b, d), (b, e), (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）计算它们的权值．

160 ?

65 95

解：（1）最优二叉树如右图所示：

42 3453 1724 19

105

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

【篇三：离散数学习题解答第6部分(图论)】

1．从日常生活中列举出三个例子，并由这些例子自然地导出两个无

向图及一个向图。

[解] ①用v代表全国城市的集合，e代表各城市间的铁路线的集合，则所成之图g=（v，e）是全国铁路交通图。是一个无向图。

②v用代表中国象棋盘中的格子点集，e代表任两个相邻小方格的对角线的集合，则所成之图g=（v，e）是中国象棋中“马”所能走的路

线图。是一个无向图。

③用v代表fortran程序的块集合，e代表任两个程序块之间的调用

关系，则所成之图g+（v，e）是fortran程序的调用关系图。是一

个有向图。 2．画出下左图的补图。

[解] 左图的补图如右图所示。

3．证明下面两图同构。

a 图g′

v3 图g

[证] 存在双射函数?:v→v′及双射函数? : e→e′

? (v1)=v1′ ? (v2)=v2′ ? (v3)=v3′ ? (v4)=v4′ ? (v5)=v5′ ?

(v6)=v6′

? (v1，v

2)=(v1′，v2′) ? (v2，v3)=(v2′，v3′) ? (v3，v4)=(v3′，v4′) ? (v4，

v5)=(v4′，v5) ? (v5，v6)=(v5′，v6′) ? (v6，v1)=(v6′，v1′) ? (v1，

v4)=(v1′，v4′) ? (v2，v5)=(v2′，v5′) ? (v3，v6)=(v3′，v6′)

显然使下式成立：

4．证明（a），（b）中的两个图都是不同构的。

图g中有一个长度为4的圈v1v2v6v5v1，其各顶点的度均为3点，而在图g′中却没有这样的圈，因为它中的四个度为3的顶点v1?，

v5?，v7?，v3?不成长度的4的圈。

图g中′有四个二度结点，v6?，v8?，v4?，它们每个都和两个三度

结点相邻，而g中一个区样的结点都没有。

在（b）中，图g?中有一2度结点v3?，它相邻的两个项点v2?，

v4?的度均为4，而在图g中却没有这样的点。

g′

v3?

v4?

5．一个图若同构于它的外图，则称此图为自补图。在满足下列条件

的无向简单图中： 1) 给出一个五个结点的自补图；

2)有三个或一结点的自补图吗？为什么？

3）证明：若一个图为自补图，则它对应的完全图的边数不清必然为

偶数。 [解] 1) 五个结点的自补图如左图g所示

同构函数? : v→v及? : e→e如下： ? (a)=a? (b)=c? (c)=e? (d)=b?

(e)=d

?(a，b)=(a，c) ?(b，c)=(c，e) ?(c，d)=(e，d) ?(d，e)=(b，d) (e，a)=(d，a)

2)（a）没有三个结点的自补图。因为三个结点的完备图的边数为

3(3?1)=3

2为奇数，所以由下面3)的结论，不可能有自补图。

（b）有五个结点的自补图。1）中的例子即是一个五个结点的自补图。 3）证：一个图是一个自补图，则它对应的完全图的边数必为偶数。

实际上，n个项点（n＞3）的自补图g，由于其对应的完全图的边

数|e*|=

n(n?1)n(n?1)

，因此有=2|e|，为偶数。这里n≥4。对于所有大于或等22

于4的正整数，都可表达成n=4k，4k+1，4k+2，4k+3的形式，这

里k=1，2，?。

其中只有n=4k，4k+1，才能使4k或4k+1形式，（k∈n）

n(n?1)

为偶数，所以自补图的项点数只能是2

6．证明在任何两个或两个以上人的组内，总存在两个人在组内有相

同个数的朋友。

[证] 令上述组内的人的集合为图g的项点集v，若两人互相是朋友，则其间联以一边。所得之图g是组内人员的朋友关系图。显然图g

是简单图，图中项点的度恰表示该人在组内朋友的个数，利用图g，上述问题就抽象成如下的图认论问题：在简单图g中，若|v|≥2，则

在g中恒存在着两个项点，v1，v2∈v，使得它们的度相等，即

deg(v1)=deg(v2)。其证明如下：

若存在着一个项点v∈v，使得deg(v)=0，则图g中各项点的度最

大不超过n-2。因此n个项点的度在集合{0，1，2，?，n-2}里取值，而这个集合只有n-1个元素，因此，根据鸽笼原理，必有两个项点

的度相同。

若不存在一个度为零的项点，则图g中各项点的度最大不超过n-1。因此n个项点的度在集合{1，2，?，n-1}中取值，这个集合只有n-1

个元素，因此，根据鸽笼原理，必有两具项点的度相同。

7．设图g的图示如右所示： 1) 找出从a到f的所有初级路；

2）找出从a到f的所有简单路； 3）求由a到f的距离。 [解] 1）

从a到f的初级路有7条

p1 : (a，b，c，f)，p2 (a，b，c，e，f)，p3 : (a，b，e，f) p4 : (a，b，e，c，f)，p5 : (a，d，c，e，f)，p6 : (a，d，e，c，f) p7 : (a，d，e，b，c，f)。 2）从a到f的简单路有9条

除了上述1）中7条外，不有p8 : (a，d，e，c，b，e，f) p9 : (a，d，e，b，c，e，f)。 3）从a到f的距离为3。

由图可看出，显然从a到f，一步不可能到达，二步也不可到达；但有长度为3的路，比如p1，p3，p5等能从a到f，故从a到f的距

离为3。

8．在下面的图中，哪此是边通图？哪些是简单图？

（a） (b) (c)

[解] （1）图（2）与图（b）不连通，它们能分成两个边通支。所以只有图（c）是

连能图。

（2）图（c）是简单图，图为它显然无平等边，无自环。图（a）、（b）是多重图（a）有平行边（b）有自环。

9．求出所有具有四个结点的简单无向连通图。

[解] 在不同构的意义下，具有四个结点的简单无向连通图共有6个。如下面所示：

g2 g2

g4 g4

g5 g5

g6 g6

?lya定理得证。参见卢（实际上，具有四个结点的简单图共有11个，这可由p?o

开澄的《组合数学一算法与分析》上册p241-p244）。 10．设g是一个简单无向图，且为（n，m）图，若

m?(n?1)(n?2)

证明g是连通图。

[证] 用反证法。假若简单无向图g不是连通图，那么g必可成k

（≥2）个连通分支g1，g2，?，gk，每个连通分支gi（1≤i≤k）都

是一个简单无向图，因此它们分别为（n1，m1），（n2，m2），?

（nk，mk）图显然有n=n1+n2+?nk，m=m1+m2+?mk，且ni≤n-1（1≤i≤k）于是有

m=m1+m2+?mk