总复习题（一）
一．单选题
1 (C)。一连通的平面图，5个顶点3个面，则边数为（）。
、4        、5        、6      、7
2、 (A)。如果一个简单图，则称为自补图，非同构的无向4阶自补图有（）个。 、1        、2      、3      、4
3、 (D)。为无环有向图，为的关联矩阵，则（）。 、是的终点、与不关联、与关联、是的始点
4、 (B)。一连通的平面图，8个顶点4个面，则边数为。
、9        、10        、11        、12
5、 (D)。如果一个简单图，则称为自补图，非同构的3阶有向完全图的子图中自补图有个。
、1        、2      、3      、4
6、21条边，3个4度顶点，其余顶点为3度的无向图共有个顶点。
、13      、12          、11          、10
7、 (D)。有向图的通路包括。
、简单通路、初级通路、复杂通路、简单通路、初级通路和复杂通路
8、 (D)。一连通的平面图，9个顶点5个面，则边数为。
、9        、10        、11        、12
9、21条边，3个4度顶点，其余顶点为3度的无向图共有个顶点。
、13      、12          、11          、10
10、 (D)。有向图的通路包括。
、简单通路、初级通路、复杂通路、简单通路、初级通路和复杂通路
11、 (D)。一连通的平面图，9个顶点5个面，则边数为。
、9        、10        、11        、12
12、 (B)。为有向图，为的邻接矩阵，则。 、邻接到的边的条数是５、接到的长度为４的通路数是５
A B C D G G ≅G A B C D E ,V D =[]m n ij m ⨯D 1m ij =A i v j e B i v j e C i v j e D i v j e A B C D G G ≅G A B C D A B C D A B C D A B C D A B C D A B C D A B C D E ,V D =[]n n ij a ⨯D 5a )4(ij =A i v j v B i v j v
、长度为４的通路总数是５、长度为４的回路总数是５
13、 (C)。在无向完全图中有个结点，则该图的边数为（）。
A 、
B 、
C 、
D 、
14、 (C)。任意平面图最多是（）的。
A 、3
B 、4
C 、5
D 、6
15、 (A)。对与10个结点的完全图，对其着时，需要的最少颜数为（）
。 A 、10    B 、9    C 、11    D 、12 16、(C)。对于任意的连通的平面图，且每个面的次数至少为有，其中，分别为的阶数、边数。
、、
、、 二．判断题
1、 (A)。有向图的关联矩阵要求图是无环图。（  ）
2、 (A)。是某图的度数序列。（  ）
3、 (A)。无向连通图的点的连通关系是等价关系（  ）
4、 (B)。是某图的度数序列。（  ）
5、 (A)。V 和E 分别为无向连通图G1的点割集和边割集. G1  的连通分支个数为2。  (    )
6、 (A)。彼得森图不是哈密尔顿图。（  ）
7、 (B)。是平面图。（  ）
8、 (B)。设是平面图，若，则它们的对偶图。（  ） 9、 (A)。是平面图。（  ）
10、 (A)。一个简单图的闭包是汉密尔顿图时，这个简单图是汉密尔顿图。（）
11、 (B)。平面图中，任何两条边除端点外可以有其他交点。（）
12、 (B)。余树一定是树。（  ）
13、 (A)。为无向连通图，是的生成子图，并且是树，则是的生成树。（  ）
14、 (A)。是非平凡的无向树，则至少有两片树叶（  ）
C D n 12n 212n 1(1)2n n -(1)n n -G 10K 10()x K G )3l (l ≥m ,n G A )2n (2l l m --≥B )2n (l 2-l m -≤C )2n (2l l m --≤
D )2n (l 2-l m -≥)1,1,2,2,4()1,1,1,4(5K 2
,1G G 21G G ≅**≅21G G 4K G T G T T G T n T
15、 (B)。无向树有3个3度、2个2度顶点，其余顶点都是树叶，共有4片树叶。 (    )
16、 (A)。无向树有3个3度、2个2度顶点，其余顶点都是树叶，共有5片树叶。(    )
17、 (B)。已知n(n>=2)阶无向简单树具有1条边，他一定是树。(    )
18、 (A)。一个连通无向图中，存在两个结点和，如果结点和的每一条路都通过结点，则结点比为割点。（）
19、 (A)。一个有向图，如果中有一个回路，至少包含每个结点一次，则是强连通。
20、 (A)。给定图，则关于树的定义是每一对结点之间有且仅有一条路。（）
21、 (A)。完全叉树是每一个结点的出度等于或0的根树。（）
22、 (A)。在正则叉树中，所有的树叶层次相同。（）
23、 (B)。树中分支点的通路长度为外部通路长度。（）
24、 (B)。树中树叶的通路长度为内部通路长度。（）
25、 (A)。任何一棵二叉树的树叶可对应一个前缀码。（）
26、(A)。任何一个前缀码都对应一棵二叉树。（）
三．综合题
1.证明：若图是自对偶的，则        .
2是一棵树，有两个2度结点，一个3度结点，三个4度结点，T 有几片树叶？
解：设树T 有x 片树叶，则T 的结点数
2+1+3
T 的边数1=5
又由得 2 ·（5）=2·2+3·1+4·3
所以9，即树T 有9片树叶。
3.图所示的赋权图G 表示七个城市及架起城市间直接通讯线路的预测造价。试给出一个设计方案使得各城市间能够通讯且总造价最小，并计算出最小造价。 u v u v w w G G G T m m
m如果有如果
解：最小生成树为 因此如图架线使各城市间能够通讯，且总造价最小，最小造价为：  Ｗ(Ｔ)＝１＋３＋４＋８＋９＋23＝48
4.求出下所示图的邻接矩阵和可达性矩阵，并出
到  长度为 的通路有几条。。
0100001011001110A ⎡⎤⎢⎥⎢⎥=⎢⎥⎢⎥⎣⎦
解：邻接矩阵
到  长度为 的通路有 条
5.求下图的一棵最小生成树.
解：因为图中n ＝8，所以按算法要执行n －1＝7次，其过程见下图中(1)~(7)。
(2)(3)(4)(1)(2)(3)(4)010001000010001000101100110011000110111011101110110001100110111011101110111011101110111011101110A A A P A A A A ⎡⎤⎡⎤⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥=∧=⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎣⎦
⎡⎤⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥==⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎡⎢⎢=∨∨∨=⎢⎣⎤⎥⎥⎥⎢⎥⎦