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