图论练习题
一.选择题
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 的邻接矩阵为
⎥⎥⎥
⎥⎥⎥⎦
⎤
⎢⎢⎢⎢⎢⎢⎣⎡0101010010000011100000100
则G 的边数为( ).
A .5
B .6
C .3
D .4 28.设图G =<V ,
E >,则下列结论成立的是 ( ).
A .deg(V )=2∣E ∣
B .deg(V )=∣E ∣
C .
E v V
v 2)deg(=∑∈ D .E v V
v =∑∈)deg(
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 +2
B .v +e -2
C .e -v -2
D .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 的任意非空子集V 1,都有 ≤∣V 1∣.
4.设有向图D 为欧拉图,则图D 中每个结点的入度 .
5.设完全图K n 有n 个结点(n ≥2),m 条边,当 时,K n 中存在欧拉回路.
6.给定一个序列集合{1,01,10,11,001,000},若去掉其中的元素 ,则该序列集合构成前缀码.
ο
ο
ο ο ο
c
a
b e
d ο f
ο
ο
ο
ο ο
c
a b e d
ο f
三、计算题
1.设图G =<V ,E >,其中V ={a 1, a 2, a 3, a 4, a 5},
E ={<a 1, a 2>,<a 2, a 4>,<a 3, a 1>,<a 4, a 5>,<a 5, a 2>}
(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 的邻接矩阵;
(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)计算它们的权值.
解:(1)最优二叉树如右图所示:
问:如果一组权为2,3,6,9,13,15,能否画出最优二叉树?
ο ο ο ο ο
c a b e
d
ο f
1
5 2 2 6
1
9
3 8
ο ο ο ο
ο
ο ο ο ο 3
2 7 1
3 5 5
11 17 34 ο ο 160 29 10 ο ο ο 23 19
42 ο ο 17 ο 24 ο 53 31
ο ο
ο 95
65。