2023年7月19日发(作者：)

第二部分 图论 选择题 判断题

注意：A B C D顺序会出现变动！根据选项确定答案！

1. 已知无向图G的邻接矩阵为

，

则G有（ 5点，7边 ）．

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

2. 设无向图G的邻接矩阵为

，

则G的边数为( 5 )．

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

3．设无向图G的邻接矩阵为

则G的边数为（ 7 ）。

A．1 B. 6 C. 7 D. 14

4．设图G＝

E>，vV，则下列结论成立的是 (vV A. deg(v)=2|E|

B. deg(v)=|E|

degv2EdegvE

C.vV D.

vV

degv2E ) ．

5. 图G如图二所示，以下说法正确的是 ( {b,

c}是点割集 )

A.

a是割点 B. {b,

c}是点割集

C. {b,

d}是点割集 D. {c}是点割集

6. 如图所示，以下说法正确的是 (

e是割点)．

A.

e是割点 B. {a,

e}是点割集

C. {b,

e}是点割集 D. {d}是点割集

7. 如图所示，以下说法正确的是（

e是割点 ）

A.

e是割点 B. {a,

e}是点割集

C. {b,

e}是点割集 D. {d}是点割集

8. 如图一所示，以下说法正确的是 ( {(d,

e)}是边割集 ) ．

A. {(a, e)}是割边 B. {(a, e)}是边割集

C. {(a, e) ,(b, c)}是边割集 D. {(d,

e)}是边割集

9. 图G如图四所示，以下说法正确的是

( {(a, d) ,(b, d)}是边割集) ．

A. {(a, d)}是割边 B. {(a, d)}是边割集

C. {(a, d) ,(b, d)}是边割集 D. {(b,

d)}是边割集

图四

10. 设有向图（a）、（b）、（c）与（d）如图五所示，则下列

结论成立的是 (（a）是强连通的 )．

图五

A. （a）是强连通的 B. （b）是强连通的

C. （c）是强连通的 D. （d）是强连通的

11. 设有向图（a）、（b）、（c）与（d）如图六所示，则下列结论成立的是

( （d）只是弱连通的 )．

图六

A. （a）只是弱连通的 B. （b）只是弱连通的

C. （c）只是弱连通的 D. （d）只是弱连通的

12. 设G是连通平面图，有v个结点，e条边，r个面，则r

= (

e－v＋2 )．

A.

e－v＋2 B.

v＋e－2 C.

e－v－2 D.

e＋v＋2

13. 设完全图Kn有n个结点(n2)，m条边，当（

n为奇数）时，Kn中存在欧拉回路．

A.

m为奇数 B.

n为偶数 C.

n为奇数 D.

m为偶数

14. 若G是一个欧拉图，则G一定是( 连通图)．

A. 平面图 B. 汉密尔顿图 C. 连通图 D. 对偶图

15. 若G是一个汉密尔顿图，则G一定是( 连通图 )．

A. 平面图 B. 对偶图 C. 欧拉图 D. 连通图

16.无向完全图K4是（ 汉密尔顿图 ）．

A. 欧拉图 B. 汉密尔顿图 C. 非平面图 D. 树

17. 无向树T有8个结点，则T的边数为( 7 )．

A. 6 B. 7 C.8 D.9

18. 无向简单图G是棵树，当且仅当(

G连通且边数比结点数少1 )．

A.

G连通且边数比结点数少1 B.

G连通且结点数比边数少1

C.

G的边数比结点数少1 D.

G中没有回路

19. 已知一棵无向树T中有8个顶点，4度、3度、2度的分支点各一个，T的树叶数为( 5 )．

A．8 B.5 C.4 D.3

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

A. m-n+1 B. m-n C. m+n+1 D. n-m+1

21. 以下结论正确的是（树的每条边都是割边 ）

A. 无向完全图都是欧拉图 B. 有n个结点n－1条边的无向图都是树

C. 无向完全图都是平面图 D. 树的每条边都是割边

22. 无向图G存在欧拉回路，当且仅当（ G连通且至多有两个奇数度结点 ）.

A. G中所有结点的度数全为偶数

B. G中至多有两个奇数度结点

C. G连通且所有结点的度数全为偶数

D. G连通且至多有两个奇数度结点

二、 判断题 1.设G是一个有7个结点16条边的连通图，则G为平面图． ( 错 )

2. 如果图G是无向图，且其结点度数均为偶数，则图G存在一条欧拉回路．

( 错 )

3. 如图九所示的图G不是欧拉图而是汉密尔顿图． ( 对 )

4. 设图G如图七所示，则图G的点割集是{f}． ( 错 )

5. 两个图同构的必要条件是结点数相等；边数相等；度数相同的结点数相等．

( 对 )

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

7. 若图G=中具有一条汉密尔顿回路，则对于结点集V的每个非空子集S，在G中删除S中的所有结点得到的连通分支数为W，则S中结点数|S|与W满足的关系式为W|S|． ( 对 )

8. 汉密尔顿图一定是欧拉图． ( 错 )

9. 设G=是具有n个结点的简单图，若在G中每一对结点度数之和小于n-1，则在G中存在一条汉密尔顿路． ( 错 )

(应该大于等于n-1)

10. 设G是一个连通平面图，且有6个结点11条边，则G有7个面．( 对 )

11. 已知图G中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G的边数是15． ( 对 )

12. 设图G是有5个结点的连通图，结点度数总和为10，则可从G中删去6条边后使之变成树． ( 错 )

（应该删除5-4=1条边）

13. 设完全图Kn有n个结点（n2），m条边，当n为奇数时，Kn中存在欧拉回路 ( 对 )

14. 设G是一个图，结点集合为V，边集合为E，则degv2E ( 对 )

vV 15. 若图G=，其中V={ a, b, c, d }，E={ (a, b), (a, d),(b, c), (b,

d)}，则该图中的割边为(b, c)

( 对 )

16. 结点数v与边数e满足e=v的无向连通图就是树． ( 错 )

17. 无向图G的结点数比边数多1，则G是树． ( 错 )

18. 设连通平面图G的结点数为5，边数为6，则面数为4． ( 错 )

19. 如图八所示的图G存在一条欧拉回路． ( 错 )

20. 无向图G存在欧拉回路，当且仅当G连通且结点度数都是偶数．( 对 )