《离散数学》第四部分---图论练习题答案
1、设G是一个哈密尔顿图，则G一定是( )。
(1) 欧拉图 (2) 树 (3) 平面图 (4) 连通图 答：(4)
2、下面给出的集合中，哪一个是前缀码？( )
(1) {0，10，110，101111} (2) {01，001，000，1}
(3) {b，c，aa，ab，aba} (4) {1，11，101，001，0011}
答：（2）
3、一个图的哈密尔顿路是一条通过图中( )的路。
4、在有向图中，结点v的出度deg+(v)表示( )，入度deg-(v)表示( )。
答：以v为起点的边的条数， 以v为终点的边的条数
5、设G是一棵树，则G 的生成树有( )棵。
(1) 0 (2) 1 (3) 2 (4) 不能确定
答：1
6、n阶无向完全图Kn 的边数是( )，每个结点的度数是( )。 答：, n-1
答：m=n-1
公共选择理论8、一个图的欧拉回路是一条通过图中( )的回路。
答：所有边一次且恰好一次
9、有n个结点的树，其结点度数之和是( )。
答：2n-2
10、下面给出的集合中，哪一个不是前缀码( )。
(1) {a，ab，110，a1b11} (2) {01，001，000，1}
(3) {1，2，00，01，0210} (4) {12，11，101，002，0011}
答：(1)
11、n个结点的有向完全图边数是( )，每个结点的度数是( )。
答：n(n-1),2n-2
12、一个无向图有生成树的充分必要条件是( )。
答：它是连通图
权责发生制原则
13、设G是一棵树，n,m分别表示顶点数和边数，则
(1) n=m (2) m=n+1 (3) n=m+1 (4) 不能确定。
答：（3）
14、设T=〈V,E〉是一棵树，若|V|>1，则T中至少存在( )片树叶。
答：2
15、任何连通无向图G至少有( )棵生成树，当且仅当G 是( )，G的生成树只有一棵。
答：1，树
16、设G是有n个结点m条边的连通平面图，且有k个面，则k等于:
(1) m-n+2 (2) n-m-2 (3) n+m-2 (4) m+n+2。
答：（1）
17、设T是一棵树，则T是一个连通且( )图。
答：无简单回路
18、设无向图G有16条边且每个顶点的度数都是2，则图G有( )个顶点。
(1) 10 (2) 4 (3) 8 (4) 16
答：（4）
19、设无向图G有18条边且每个顶点的度数都是3，则图G有( )个顶点。
(1) 10 (2) 4 (3) 8 (4) 12
答：(4)
20、设图G=<V，E>，V={a，b，c，d，e}，E={<a,b>,<a,c>,<b,c>,<c,d>,<d,e>},则G是有向图还是无向图？
答：有向图
21、任一有向图中，度数为奇数的结点有( )个。
答：偶数
22、具有6 个顶点，12条边的连通简单平面图中，每个面都是由( )条边围成？
(1) 2 (2) 4 (3) 3 (4) 5
答：（3）
23、在有n个顶点的连通图中，其边数（ ）。
(1) 最多有n-1条 (2) 至少有n-1 条
(3) 最多有n条 (4) 至少有n 条
答：（2）
24、一棵树有2个2度顶点，1 个3度顶点，3个4度顶点，则其1度顶点为（ ）。
(1) 5 (2) 7 (3) 8 (4) 9
答：（4）
25、若一棵完全二元（叉）树有2n-1个顶点，则它（ ）片树叶。
(1) n (2) 2n (3) n-1 (4) 2
答：（1）
26、下列哪一种图不一定是树（ ）。
(1) 无简单回路的连通图 (2) 有n个顶点n-1条边的连通图
(3) 每对顶点间都有通路的图 (4) 连通但删去一条边便不连通的图
答：（3）
27、连通图G是一棵树当且仅当G中（ ）。
(1) 有些边是割边 (2) 每条边都是割边
(3) 所有边都不是割边 (4) 图中存在一条欧拉路径
答：（2）
二、证明或解答题
1、证明在有王冶平简历n个结点的树中，其结点度数之和是2n-2。
证明：
设T=<V,E>是任一棵树，则|V|=n，且|E|=n-1。
由欧拉握手定理，树中所有结点的度数之和等于2|E|.
从而结点度数之和是2n-2。
2、任一图中度数为奇数的结点是偶数个。
证明：
设G=〈V,E〉是任一图。设|V|=n。
由欧拉握手定理可得 deg(v)=2|E|可得，图中所有结点度数之和是偶数。显然所有偶数度结点的度数之和仍为偶数，从而所有奇数度结点的度数之和也是偶数。因此，图中度数为奇数的结点一定为偶数个。
3、连通无向图G的任何边一定是G的某棵生成树的弦。这个断言对吗？若是对的请证明之，否则请举例说明。
证明：
不对。
反例如下：若G 本身是一棵树时，则G的每一条边都不可能是G的任一棵生成树（实际上只有惟一一棵）的弦。
女体解剖授业4、设T=<V,E>是一棵树，若|V|>1，则T中至少存在两片树叶。
证明：
（用反证法证明）设|V|=乙烯制乙醇n。
因为T=〈V,E〉是一棵树，所以|E|=n-1。
由欧拉握手定理可得 deg(yig滤波器v)=2|E|=2n-2。
假设T中最多只有1片树叶，则deg(v)2(n-1)+1>2n-2。
得出矛盾。
5、画一个使它分别满足：
(1)有欧拉回路和哈密尔顿回路；
(2)有欧拉回路，但无条哈密尔顿回路；
(3)无欧拉回路，但有哈密尔顿回路；
(4)既无欧拉回路，又无哈密尔顿回路。
解
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议