离散数学第二次作业

13级计算机专业1-3班离散数学作业2

班级 姓名 学号 成绩

一、 图的概念、连通性与矩阵表示

选择/填空题

1、 任何n个节点m条边的图G = (V,E) , 边数与顶点度数的关系是 。

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

3、n阶完全图Kn的边数为 。

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

5、已知图G中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G的边数是 ．

6、下面四组数能构成无向图的度数列的有( )。

A、 2,3,4,5,6,7； B、 1,2,2,3,4；

C、 2,1,1,1,2； D、 3,3,5,6,0。

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

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

8、在有n个顶点的连通图中，其边数（ ）。

(1) 最多有n-1条 (2) 至少有n-1 条

(3) 最多有n条 (4) 至少有n 条

9、如右图 相对于完全图K5的补图为（ ）。

10、给定无向图G如下图所示，下面给出的结点集子集中，不是点割集的为（ ）．

A．{b, d} B．{d}

C．{a, c} D．{b, e} 13级计算机专业1-3班离散数学作业2

2 11、图G如右图所示，以下说法正确的是 ( ) ．

A．{(a, c)}是割边

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

C．{(b, c)}是边割集

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

12、给定无向图G=如下图所示，下面哪个边集不是其边割集（ ）。

A、；

B、{,};

C、；

D、。

13、设有向图（a）、（b）、（c）与（d）如下图所示，则下列结论成立的是( )．

A．（a）是强连通的 B．（b）是强连通的

C．（c）是强连通的 D．（d）是强连通的

14、下图 的邻接矩阵A=

15、设无向图G的邻接矩阵为0101010010000011100000100，则G的边数为( )．

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

16、图 的邻接矩阵为( )。

},,,{4341vvvv},,,{8474vvvv},,,{3221vvvv13级计算机专业1-3班离散数学作业2

3

A、；B、；C、；D、。

综合题

17、设G=，V={ v1，v2，v3，v4，v5}，E={ (v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5) }，试

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

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

18、已知：D=，V={1,2,3,4,5}，E={<1,2>,<1,4>,<2,3>,<3,4>,<3,5>,<5,1>}，求D的邻接距阵A和可达距阵P。

19、无向图G有12条边，G中有6个3度结点，其余结点的度数均小于3，问G中至少有多少个结点？

20、 有向图G如右图所示。

（1）求G的邻接矩阵A；

（2）G中1v到4v长度为4的路径有几条？

（3）G中1v到自身长度为3的回路有几条？

（4）G是哪类连通图？

0001101110100001111111111111111100011011110000100001101110100010e2 e7 v4 e4 v1

v2 v3 e1

e3 e6

e5 13级计算机专业1-3班离散数学作业2

4

21、设图G如图1所示，

(1) 求G的邻接矩阵A；

(2) 求(2)(3)(4),,AAA，说明从1v到4v的长为2,3,4的路径各有几条；

(3) 求G的可达矩阵P；

(4) 求G的强连通分图。

22、设有如下有向图G=，

（1）求G的邻接矩阵；

（2）G中v1到v4的长度为4 的通路有多少条？

（3）G中经过v1的长度为3 的回路有多少条？

（4）G中长度不超过4 的通路有多少条？其中有多少条通路？

13级计算机专业1-3班离散数学作业2

5

二、 二部图、欧拉图、哈密顿图

选择/填空题

23、无向图G存在欧拉通路，当且仅当( )．

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

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

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

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

24、无向图G是欧拉图,当且仅当( )

(A) G的所有结点的度数都是偶数 (B)G的所有结点的度数都是奇数

(C)G连通且所有结点的度数都是偶数 (D) G连通且G的所有结点度数都是奇数。

25、当n为 时,非平凡无向完全图Kn是欧拉图。

26、下列图中是欧拉图的有( )。

27、下图中既不是Eular图，也不是Hamilton图的图是（ ）

28、在如下各图中（ ）是欧拉图。

综合题 13级计算机专业1-3班离散数学作业2

6

29、若一个有向图G是欧拉图，它是否一定是强连通的？若一个有向图G是强连通的，它是否一定是欧拉图？说明理由。

30、一次学术会议的理事会共有20个人参加，他们之间有的相互认识但有的相互不认识。但对任意两个人，他们各自认识的人的数目之和不小于20。问能否把这20个人排在圆桌旁，使得任意一个人认识其旁边的两个人?根据是什么?

三、 树及应用

选择/填空题

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

A．1mn B．mn C．1mn D．1nm

32、已知一棵无向树T中有8个结点，4度，3度，2度的分支点各一个，T的树叶数为（ ）．

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

33、连通无向图G有6个顶点9条边，从G中删去 条边才有可能得到G的一棵生成树T．

34、已知一棵无向树T有三个3顶点,一个2度顶点,其余的都是1度顶点,

则T中有 个1度顶点。

35、一棵树有2个2度顶点，1 个3度顶点，3个4度顶点，则其1度顶点为（ ）。

(1) 5 (2) 7 (3) 8 (4) 9

36、一棵无向树的顶点数n与边数m关系是 。

37、有n个结点的树，其结点度数之和是 。

38、设G是一棵树，n,m分别表示顶点数和边数，则（ ）

(1) n=m (2) m=n+1 (3) n=m+1 (4) 不能确定。

39、任何连通无向图G至少有 棵生成树。 13级计算机专业1-3班离散数学作业2

7

40、下面给出的集合中，哪一个不是前缀码( )。

(1) {a，ab，110，a1b11} (2) {01，001，000，1}

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

41、下面给出的集合中，哪一个是前缀码？( )

(1) {0，10，110，101111} (2) {01，001，000，1}

(3) {b，c，aa，ab，aba} (4) {1，11，101，001，0011}

综合题

42、图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权最小的生成树及其权值．

43、已知带权图G如右图所示．

(1) 求图G的最小生成树； (2)计算该生成树的权值．

44、如下图所示的赋权图表示某七个城市及预先算出它们之间的一些直接通信成路造价（单位：万元），试给出一个设计方案，使得各城市之间既能够通信又使总造价最小。 721,,,vvv13级计算机专业1-3班离散数学作业2

8

45、设带权无向图G如下，求G的最小生成树T及T的权总和，要求写出解的过程。

46、求叶的权分别为2、4、6、8、10、12、14的最优二叉树及其权。

47、在通讯中，八进制数字出现的频率如下：

0：30%、1：20%、2：15% 、3：10%、4：10%、5：5%、6：5%、7：5%

求传输它们最佳前缀码（写出求解过程）。