内容发布更新时间 : 2024/12/25 11:05:10星期一 下面是文章的全部内容请认真阅读。

. . .

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

一、单项选择题

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）若是欧拉图，请写出一条欧拉回路．

..........