离散数学图论部分经典试题和答案

. . .

离散数学图论部分综合练习

一、单项选择题

1.设图G的邻接矩阵为

?01?10? ?10??01??01100?011??000?

?001?010??

则G的边数为( ).

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

2.已知图G的邻接矩阵为

则G有( ).

A.5点,8边 B.6点,7边 C.6点,8边 D.5点,7边

3.设图G=,则下列结论成立的是 ( ).

A.deg(V)=2?E? B.deg(V)=?E? C.?deg(v)?2E D.?deg(v)?E

v?Vv?Va ? d? ? c

图一

b ? ? f

?e

4.图G如图一所示,以下说法正确的是 ( ) . A.{(a, d)}是割边 B.{(a, d)}是边割集 C.{(d, e)}是边割集 D.{(a, d) ,(a, c)}是边割集

5.如图二所示,以下说法正确的是 ( ). A.e是割点 B.{a, e}是点割集 C.{b, e}是点割集 D.{d}是点割集

6.如图三所示,以下说法正确的是 ( ) .

)} 是边割集 图二 A.{(a, e)}是割边 B.{(a, eC.{(a, e) ,(b, c)}是边割集 D.{(d, e)}是边割集

..........

. . .

图三

7.设有向图(a)、(b)、(c)与(d)如图四所示,则下列结论成立的是 ( ).

图四

A.(a)是强连通的 B.(b)是强连通的

C.(c)是强连通的 D.(d)是强连通的 应该填写:D

8.设完全图Kn有n个结点(n≥2),m条边,当( )时,Kn中存在欧拉回路.

A.m为奇数 B.n为偶数 C.n为奇数 D.m为偶数 9.设G是连通平面图,有v个结点,e条边,r个面,则r= ( ).

A.e-v+2 B.v+e-2 C.e-v-2 D.e+v+2 10.无向图G存在欧拉通路,当且仅当( ). A.G中所有结点的度数全为偶数 B.G中至多有两个奇数度结点 C.G连通且所有结点的度数全为偶数 D.G连通且至多有两个奇数度结点

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

A.m?n?1 B.m?n C.m?n?1 D.n?m?1 12.无向简单图G是棵树,当且仅当( ).

A.G连通且边数比结点数少1 B.G连通且结点数比边数少1 C.G的边数比结点数少1 D.G中没有回路.

二、填空题

1.已知图G中有1个1度结点,2个2度结点,3个3度结点,4个4度结

b a?点,则G的边数是 . ?

2.设给定图G(如图四所示),则图G的点割

f ? ..........

? c ?d

e ? 图四

. . .

集是 .

3.若图G=中具有一条汉密尔顿回路, 则对于结点集V的每个非空子集S,在G中删除S 中的所有结点得到的连通分支数为W,则S中结点

数|S|与W满足的关系式为 .

4.无向图G存在欧拉回路,当且仅当G连通 且 .

5.设有向图D为欧拉图,则图D中每个结点的入度 . 应该填写:等于出度

6.设完全图Kn有n个结点(n?2),m条边,当 时,Kn中存在欧拉回路.

7.设G是连通平面图,v, e, r分别表示G的结点数,边数和面数,则v,e和r满足的关系式 .

8.设连通平面图G的结点数为5,边数为6,则面数为 . 9.结点数v与边数e满足 关系的无向连通图就是树.

10.设图G是有6个结点的连通图,结点的总度数为18,则可从G中删去 条边后使之变成树.

11.已知一棵无向树T中有8个结点,4度,3度,2度的分支点各一个,T的树叶数为 .

12.设G=是有6个结点,8条边的连通图,则从G中删去 条边,可以确定图G的一棵生成树.

13.给定一个序列集合{000,001,01,10,0},若去掉其中的元素 ,则该序列集合构成前缀码.

三、判断说明题 1.如图六所示的图G存在一条欧拉回路.

v4 v5 d e g v1 n c f h a v3 b v2 图六

2.给定两个图G1,G2(如图七所示):

(1)试判断它们是否为欧拉图、汉密尔顿图?并说明理由. (2)若是欧拉图,请写出一条欧拉回路.

..........

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4