内容发布更新时间 : 2024/11/19 14:31:56星期一 下面是文章的全部内容请认真阅读。
离散数学图论部分综合练习
一、单项选择题
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, e)} 是边割集
C．{(a, e) ,(b, c)}是边割集 D．{(d, e)}是边割集
1
图三
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 ?
2
? c ?d
e ? 图四
集是 ．
3．若图G=
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＝
13．给定一个序列集合{000，001，01，10，0}，若去掉其中的元素 ，则该序列集合构成前缀码．
三、判断说明题
1．如图六所示的图G存在一条欧拉回路．
v1 a v2 e v5 f h b 图六
d g v4 n v3 c
2．给定两个图G1，G2（如图七所示）：
（1）试判断它们是否为欧拉图、汉密尔顿图？并说明理由． （2）若是欧拉图，请写出一条欧拉回路．
3
v1
v6
v4
v5
v2
v3
v1 ? v6 ? ? v5
v? 2
? v3
? v4
图八
图七
3．判别图G(如图八所示)是不是平面图， 并说明理由．
4．设G是一个有6个结点14条边的连 通图，则G为平面图．
四、计算题
1．设图G??V，E?，其中V??a1, a2, a3, a4, a5?,
E???a1, a2?，?a2, a4?，?a3, a1?，?a4, a5?，?a5, a2??
（1）试给出G的图形表示； （2）求G的邻接矩阵；
（3）判断图G是强连通图、单侧连通图还是弱连通图？
2．设图G=
（1）画出G的图形表示； （2）写出其邻接矩阵； （2）求出每个结点的度数； （4）画出图G的补图的图形． 3．设G=
（1）给出G的图形表示； （2）写出其邻接矩阵； （3）求出每个结点的度数； （4）画出其补图的图形． 4．图G=
（1）画出G的图形； （2）写出G的邻接矩阵；
（3）求出G权最小的生成树及其权值．
5.用Dijkstra算法求右图中A点到其它各点的最短路径。 6．设有一组权为2,3,5,7,11,13,17,19,23,29,31,试
（1）画出相应的最优二元树； （2）计算它们的权值． 7．给出右边所示二元有序树的
三种遍历结果．
g
4
a b d e c f i
h
五、证明题
1．若无向图G中只有两个奇数度结点，则这两个结点一定是连通的． 2．设G是一个n阶无向简单图，n是大于等于2的奇数．证明图G与它的补图G中的奇数度顶点个数相等．
3．设连通图G有k个奇数度的结点，证明在图G中至少要添加使其成为欧拉图．
参考解答
一、单项选择题
1．B 2．D 3．C 4．C 5．A 6．D 7．D 8．C 9．A 10．D 11．A 12．A
二、填空题
1．15 2．{f}，{c，e} 3．W?|S| 4．所有结点的度数全为偶数 5．等于出度 6．n为奇数 7．v-e+r =2 8．3 9．e=v-1 10．4 11．5
12．3 13．0
三、判断说明题
1．解：正确．
因为图G为连通的，且其中每个顶点的度数为偶数． 2．解：（1）图G1是欧拉图． 因为图G1中每个结点的度数都是偶数．
图G2是汉密尔顿图．
因为图G2存在一条汉密尔顿回路（不惟一）： a(a, b)b(b, e) e(e, f) f (f, g) g(g, d) d(d, c) c(c, a)a
问题：请大家想一想，为什么图G1不是汉密尔顿图，图G2不是欧拉图。
（2）图G1的欧拉回路为：（不惟一）：
v1(v1, v2) v2 (v2, v3) v3 (v3, v4) v4 (v4, v5)v5 (v5, v2) v2 (v2, v6)v6 (v6, v4) v4 (v4, v1)v1 3．解：图G是平面图．
因为只要把结点v2与v6的连线(v2, v6)拽 到结点v1的外面，把把结点v3与v6的连线
5
k条边才能2v1 ? v6 ? ? v5
v? 2
? v3
? v4 图九