第6-7章
一．选择/填空
1、设图G 的邻接矩阵为
01
010
1001000001
110000010
0，则G 的边数为( D )． A ．5 B ．6 C ．3 D ．4
2、设有向图（a ）、（b ）、（c ）与（d ）如下图所示，则下列结论成立的是( A )．
A ．（a ）是强连通的
B ．（b ）是强连通的
C ．（c ）是强连通的
D ．（d ）是强连通的
3、给定无向图G 如下图所示，下面给出的结点集子集中，不是点割集的为（ B ）． A ．{b , d }
B ．{d }
鸟的天堂课堂实录
C ．{a , c }
D ．{b , e }
4、图G 如下图所示，以下说法正确的是 ( D ) ．
A ．{(a , c )}是割边
B ．{(a , c )}是边割集
C ．{(b , c )}是边割集
D ．{(a, c ) ,(b, c )}是边割集
5、无向图G 存在欧拉通路，当且仅当(D )．
B ．G 中至多有两个奇数度结点
C ．G 连通且所有结点的度数全为偶数
D ．G 连通且至多有两个奇数度结点
6、设G 是有n 个结点，m 条边的连通图，必须删去G 的( A )条边，才能确定G 的一棵生成树． A ．1m n −+
辉南四中
B ．m n −
C ．1m n ++
D ．1n m −+
7、已知一棵无向树T 中有8个结点，4度，3度，2度的分支点各一个，T 的树叶数为（B ）．
A ．8
B ．5
C ．4
经济制裁D ．3
8、已知图G 中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G 的边数是 15 ． 9、连通无向图G 有6个顶点9条边，从G 中删去 4 条边才有可能得到G 的一棵生成树T ． 10、如右图 相对于完全图K 5的补图为（A ）
。
11、给定无向图，如下图所示，下面哪个边集不是其边割集（ B ）。
A 、；
B 、{<v1,v4>,<v4,v6>};
C 、；
D 、。
12、设D 是有n 个结点的有向完全图，则图D 的边数为( A ) (A))1(−n n (B))1(+n n (C)2/)1(+n n (D)2/)1(−n n 13、无向图G 是欧拉图，当且仅当( C )
(A) G 的所有结点的度数都是偶数 (B)G 的所有结点的度数都是奇数
(C)G 连通且所有结点的度数都是偶数 (D) G 连通且G 的所有结点度数都是奇数。 14、n 阶完全图K n 的边数为 。
；
15、右图 的邻接矩阵A= 。
>=<E V G ,},,,{4341><><v v v v },,,{8474><><v v v v },,,{3221><><v v v v )1(21
−n
n
；
16、任何(n,m) 图G = (V,E) , 边数与顶点度数的关系是 。
17、当n 为 时，非平凡无向完全图K n 是欧拉图。 奇数
18、已知一棵无向树T 有三个3顶点，一个2度顶点，其余的都是1度顶点,
则T 中有 个1度顶点。 答案： 5
19、下面四组数能构成无向图的度数列的有( B )。 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。
20、图 的邻接矩阵为( C )。 A 、
；B 、；C 、
；D 、
。
21、下列图中是欧拉图的有( A )。
22、下面给出的集合中，哪一个是前缀码？( （2） ) (1) {0，10，110，101111} (2) {01，001，000，1}
新三国穿帮
01
10001011001010∑∈=V
v m
v d 2)(
00
0110111010000
1
11
1111111111
111
1 000110111010001
(3) {b，c，aa，ab，aba} (4) {1，11，101，001，0011}
23、一棵树有2个2度顶点，1 个3度顶点，3个4度顶点，则其1度顶点为（（4））。
(1) 5 (2) 7 (3) 8 (4) 9
24、下图中既不是Eular图，也不是Hamilton图的图是（ B ）
海乐冰箱25、一棵无向树的顶点数n与边数m关系是( m=n-1 )。
26、有n个结点的树，其结点度数之和是( 2n-2 )。
27、下面给出的集合中，哪一个不是前缀码( (1) )。
(1) {a，ab，110，a1b11} (2) {01，001，000，1}
(3) {1，2，00，01，0210} (4) {12，11，101，002，0011}
28、n个结点的有向完全图边数是( n(n-1) )，每个结点的度数是( 2n-2 )。
29、设G是一棵树，n,m分别表示顶点数和边数，则（（3））
(1) n=m (2) m=n+1 (3) n=m+1 (4) 不能确定。
30、任何连通无向图G至少有( 1 )棵生成树。
31、设无向图G有16条边且每个顶点的度数都是2，则图G有( （4） )个顶点。
(1) 10 (2) 4 (3) 8 (4) 16
32、任一有向图中，度数为奇数的结点有( 偶数 )个。
33、在有n个顶点的连通图中，其边数（（2））。
(1) 最多有n-1条 (2) 至少有n-1 条
(3) 最多有n条 (4) 至少有n 条
34、在如下各图中（ B ）欧拉图。
二．综合题
1、设G=<V，E>，V={ v1，v2，v3，v4，v5}，E={ (v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5) }，试
(1) 给出G 的图形表示； (2) 写出其邻接矩阵； (3) 求出每个结点的度数； (4) 画出其补图的图形． 解：(1) G 的图形如下
(2)G =
01
100
1011011011
高温密封材料011000010
0 (3)v 1度数为1，v 2度数为2，v 3度数为4，v 4度数为3，v 5度数为2 (4)其补图的图形如下
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 权最小的生成树及其权值． 解：(1) G 的图形如下
(2)G =
011000
101111110010010001011001010110
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议