离散图论部分习题课

图论练习题一.选择题1、设G是一个哈密尔顿图，则G一定是( )。

(1) 欧拉图(2) 树(3) 平面图(4)连通图2、下面给出的集合中，哪一个是前缀码？()(1) {0，10，110，101111}(2) {01，001，000，1}(3) {b，c，aa，ab，aba}(4) {1，11，101，001，0011}3、一个图的哈密尔顿路是一条通过图中()的路。

4、设G是一棵树，则G 的生成树有( )棵。

(1) 0(2) 1(3) 2(4) 不能确定5、n阶无向完全图Kn 的边数是( )，每个结点的度数是( )。

6、一棵无向树的顶点数n与边数m关系是()。

7、一个图的欧拉回路是一条通过图中( )的回路。

8、有n个结点的树，其结点度数之和是()。

9、下面给出的集合中，哪一个不是前缀码( )。

(1) {a，ab，110，a1b11} (2) {01，001，000，1}(3) {1，2，00，01，0210} (4) {12，11，101，002，0011}10、n个结点的有向完全图边数是( )，每个结点的度数是( )。

11、一个无向图有生成树的充分必要条件是( )。

12、设G是一棵树，n,m分别表示顶点数和边数，则(1) n=m (2) m=n+1 (3) n=m+1 (4) 不能确定。

13、设T=〈V,E〉是一棵树，若|V|>1，则T中至少存在( )片树叶。

14、任何连通无向图G至少有( )棵生成树，当且仅当G 是( )，G的生成树只有一棵。

15、设G是有n个结点m条边的连通平面图，且有k个面，则k等于:(1) m-n+2 (2) n-m-2 (3) n+m-2 (4) m+n+2。

16、设T是一棵树，则T是一个连通且( )图。

17、设无向图G有16条边且每个顶点的度数都是2，则图G有( )个顶点。

(1) 10 (2) 4 (3) 8 (4) 1618、设无向图G有18条边且每个顶点的度数都是3，则图G有( )个顶点。

1 第4章 图论综合练习一、 单项选择题1．设L 是n 阶无向图G 上的一条通路，则下面命题为假的是( )． (A) L 可以不是简单路径，而是基本路径可以不是简单路径，而是基本路径 (B) L 可以既是简单路径,又是基本路径又是基本路径 (C) L 可以既不是简单路径，又不是基本路径可以既不是简单路径，又不是基本路径 (D) L 可以是简单路径，而不是基本路径可以是简单路径，而不是基本路径 答案：A 2．下列定义正确的是( )． (A) 含平行边或环的图称为多重图含平行边或环的图称为多重图 (B) 不含平行边或环的图称为简单图不含平行边或环的图称为简单图 (C) 含平行边和环的图称为多重图含平行边和环的图称为多重图 (D) 不含平行边和环的图称为简单图不含平行边和环的图称为简单图 答案：D 3．以下结论正确是．以下结论正确是 ( )．(A) 仅有一个孤立结点构成的图是零图仅有一个孤立结点构成的图是零图 (B) 无向完全图K n 每个结点的度数是n (C) 有n (n >1)个孤立结点构成的图是平凡图个孤立结点构成的图是平凡图 (D) 图中的基本回路都是简单回路图中的基本回路都是简单回路 答案：D 4．下列数组中，不能构成无向图的度数列的数组是( )． (A) (1,1,1,2,3) (B) (1,2,3,4,5) (C) (2,2,2,2,2) (D) (1,3,3,3) 答案：B 5．下列数组能构成简单图的是( )． (A) (0,1,2,3) (B) (2,3,3,3) (C) (3,3,3,3) (D) (4,2,3,3) 答案：C 6．无向完全图K 3的不同构的生成子图的个数为（的不同构的生成子图的个数为（ ）．）． (A) 6 (B) 5 (C) 4 (D) 3 答案：C 7．n 阶无向完全图K n 中的边数为（中的边数为（）．）． (A) 2)1(+n n (B) 2)1(-n n (C) n (D)n (n +1) 答案：B 8．以下命题正确的是( )．(A) n (n ³1)阶完全图K n 都是欧拉图都是欧拉图 (B) n (n ³1)阶完全图K n 都是哈密顿图都是哈密顿图(C) 连通且满足m =n －1的图<V ,E >(½V ½=n ,½E ½=m )是树是树(D) n (n ³5)阶完全图K n 都是平面图都是平面图 答案：C 10．下列结论不正确是( )．(A) 无向连通图G 是欧拉图的充分必要条件是G 不含奇数度结点不含奇数度结点(B) 无向连通图G 有欧拉路的充分必要条件是G 最多有两个奇数度结点最多有两个奇数度结点 (C) 有向连通图D 是欧拉图的充分必要条件是D 的每个结点的入度等于出度的每个结点的入度等于出度(D) 有向连通图D 有有向欧拉路的充分必要条件是除两个结点外，每个结点的入度等2 于出度于出度 答案：D 11．无向完全图K 4是（是（）．）． （A ）欧拉图）欧拉图 （B ）哈密顿图）哈密顿图 （C ）树）树 答案：B 12．有4个结点的非同构的无向树有个结点的非同构的无向树有 ( )个．个． (A) 2 (B) 3 (C) 4 (D) 5 答案：A 13．设G 是有n 个结点，m 条边的连通图，必须删去G 的( )条边，才能确定G 的一棵生成树．一棵生成树．(A) 1+-n m (B) m n - (C) 1++n m (D) 1+-m n 答案：A 14．设G 是有6个结点的完全图，从G 中删去( )条边，则得到树．条边，则得到树． (A) 6 (B) 9 (C) 10 (D) 15 答案：C 二、 填空题1．数组{1，2，3，4，4}是一个能构成无向简单图的度数序列，是一个能构成无向简单图的度数序列， 此命题的真值是此命题的真值是 . 答案：0 2．无向完全图K 3的所有非同构生成子图有的所有非同构生成子图有个．个． 答案：4 3．设图G =<V ,E >，其中|V |=n ,|E |=m ．则图G 是树当且仅当G 是连通的，且m = ． 答案：n －1 4．连通图G 是欧拉图的充分必要条件是是欧拉图的充分必要条件是 ． 答案：图G 无奇数度结点无奇数度结点5．连通无向图G 有6个顶点9条边，从G 中删去中删去 条边才有可能得到G 的一棵生成树T ． 答案：4 6．无向图G 为欧拉图，当且仅当G 是连通的，且G 中无中无 结点．结点． 答案：奇数度答案：奇数度7．设图>=<E V G ,是简单图，若图中每对结点的度数之和是简单图，若图中每对结点的度数之和 ，则G 一定是哈密顿图．一定是哈密顿图． 答案：V ³8．如图1所示带权图中最小生成树的权是所示带权图中最小生成树的权是 ．答案：12三、化简解答题1．设无向图G ＝<V ,E >，V ={v 1，v 2，v 3，v 4，v 5，v 6}， E ={( v 1，v 2), ( v 2，v 2), ( v 4，v 5), ( v 3，v 4), ( v 1，v 3), ( v 3，v 1), ( v 2，v 4)}． (1) 画出图G 的图形；的图形；v 1 v 2v 6 v 5v 3v 4图2 ·2 2 3 · 1 · 7 9 2 · 8 · 6 图1 3 (2) 写出结点v 2, v 4，v 6的度数；的度数； (3) 判断图G 是简单图还是多重图．是简单图还是多重图． 解：(1) 图G 的图形如图5所示．所示． (2) 0)deg(,3)deg(,4)deg(642===v v v ．(3) 图G 是多重图．作图如图2. 2．设图G ＝<V ，E >，其中，其中V ＝{a ,b ,c ,d ,e }, E ={(a ,b ),(b ,c ),(c ,d ), (a ,e )} 试作出图G 的图形，并指出图G 是简单图还是多是简单图还是多重图？是连通图吗？说明理由. 解：图G 如图8所示．. 图G 中既无环，也无平行边，是简单图．中既无环，也无平行边，是简单图． 图G 是连通图．G 中任意两点都连通.所以，图G 有9个结点．作图如图3．四、计算题1．设简单连通无向图G 有12条边，G 中有2个1度结点，2个2度结点，3个4度结点，其余结点度数为3．求G 中有多少个结点．试作一个满足该条件的简单无向图．中有多少个结点．试作一个满足该条件的简单无向图．解：设图G 有x 个结点，由握手定理个结点，由握手定理2´1+2´2+3´4+3´（x -2-2-3）＝12´2 271821243=-+=xx ＝9 故图G 有9个结点．个结点． 满足该条件的简单无向图如图4所示所示2．设图G (如图5表示)是6个结点a ,b ,c , d ,e ,f的图，试求，图G 的最小生成树，并计算它的权．的最小生成树，并计算它的权．解：构造连通无圈的图，即最小生成树，用解：构造连通无圈的图，即最小生成树，用克鲁斯克尔算法：克鲁斯克尔算法： 第一步：第一步： 取ab ＝1；第二步：；第二步： 取af =4 第三步：第三步： 取fe ＝3；第四步：；第四步： 取ad =9 第五步：第五步： 取bc =23 如图6．权为1+4+3+9+23=40 3．一棵树T 有两个2度顶点，1个3度顶点；3个4度顶点，度顶点， 问它有几片树叶？问它有几片树叶？解：设T 有n 顶点，则有n －1条边．T 中有2个 2度顶点，1个3度顶点，3个4度顶点，度顶点， 其余n －2－1-3个1度顶度顶点．点．由握手定理：由握手定理： 2·2+12+1··3+3·4+ (n －2－1-3)=2(n －1) 解得解得 n =15．于是T 有15-6=9片树叶片树叶五、证明题1．若无向图G 中只有两个奇数度结点，则这两个结点一定是连通的．中只有两个奇数度结点，则这两个结点一定是连通的．证：用反证法．设G 中的两个奇数度结点分别为u 和v ．假若u 和v 不连通．不连通．即它们之间无任何通路，则G 至少有两个连通分支G 1，G 2，且u 和v 分别属于G 1和G 2，于是G 1和G 2各含有一个奇数度结点．各含有一个奇数度结点．这与握手定理的推论矛盾．这与握手定理的推论矛盾．这与握手定理的推论矛盾．因而因而u 和v 一定是连通的．通的．a hb h h ec h hd 图3 图4 b · 23 1 c · · a 4 · f 9 3 d · ·e 图6 b · 23 1 15 c · 25 ·a 4 · f 28 9 16 3 d · 15 ·e 图5 。

离散数学习题解答 习题六 （第六章 图论）1．从日常生活中列举出三个例子，并由这些例子自然地导出两个无向图及一个向图。

[解] ①用V 代表全国城市的集合，E 代表各城市间的铁路线的集合，则所成之图G=（V ，E ）是全国铁路交通图。

是一个无向图。

②V 用代表中国象棋盘中的格子点集，E 代表任两个相邻小方格的对角线的集合，则所成之图G=（V ，E ）是中国象棋中“马”所能走的路线图。

是一个无向图。

③用V 代表FORTRAN 程序的块集合，E 代表任两个程序块之间的调用关系，则所成之图G+（V ，E ）是FORTRAN 程序的调用关系图。

是一个有向图。

2．画出下左图的补图。

[解] 左图的补图如右图所示。

3．证明下面两图同构。

a v 2 v 3 v 4图G图G ′[证] 存在双射函数ϕ:V →V ′及双射函数ψ : E →E ′ϕ (v 1)=v 1′ ϕ (v 1，v 2)=(v 1′，v 2′) ϕ (v 2)=v 2′ ϕ (v 2，v 3)=(v 2′，v 3′) ϕ (v 3)=v 3′ ϕ (v 3，v 4)=(v 3′，v 4′) ϕ (v 4)=v 4′ ϕ (v 4，v 5)=(v 4′，v 5) ϕ (v 5)=v 5′ ϕ (v 5，v 6)=(v 5′，v 6′) ϕ (v 6)=v 6′ϕ (v 6，v 1)=(v 6′，v 1′) ϕ (v 1，v 4)=(v 1′，v 4′) ϕ (v 2，v 5)=(v 2′，v 5′) ϕ (v 3，v 6)=(v 3′，v 6′)显然使下式成立：ψ (v i ，v j )=(v i ,v j ′)⇒ ϕ (v i )=v i ′∧ϕ (v j )=v j ′ (1≤i ·j ≤6) 于是图G 与图G ′同构。

4．证明（a ），（b ）中的两个图都是不同构的。

图G 中有一个长度为4的圈v 1v 2v 6v 5v 1，其各顶点的度均为3点，而在图G ′中却没有这样的圈，因为它中的四个度为3的顶点v 1'，v 5'，v 7'，v 3'不成长度的4的圈。

作业答案：图论部分P165:习题九1、 给定下面4个图（前两个为无向图，后两个为有向图）的集合表示，画出它们的图形表示。

（1）111,G V E =<>，112345{,,,,}V v v v v v =，11223343345{(,),(,),(,),(,),(,)}E v v v v v v v v v v = （2）222,G V E =<>，21V V =，11223344551{(,),(,),(,),(,),(,)}E v v v v v v v v v v = （3）13331,,,D V E V V =<>=31223324551{,,,,,,,,,}E v v v v v v v v v v =<><><><><> （4）24441,,,D V E V V =<>=31225523443{,,,,,,,,,}E v v v v v v v v v v =<><><><><> 解答： （1） （2）10、是否存在具有下列顶点度数的5阶图？若有，则画出一个这样的图。

（1）5，5，3，2，2；（2）3，3，3，3，2；（3）1，2，3，4，5；（4）4，4，4，4，4 解答：（1）（3）不存在，因为有奇数个奇度顶点 。

14、设G 是(2)n n ≥阶无向简单图，G 是它的补图，已知12(),()G k G k δ∆==，求()G ∆，()G δ。

解答：2()1G n k ∆=--；1()1G n k δ=--。

15、图9.19中各对图是否同构？若同构，则给出它们顶点之间的双射函数。

解答：（c ）不是同构，从点度既可以看出，一个点度序列为4，3，3，3，3而另外一个为4，4，3，3，1（d ）同构，同构函数为16、画出所有3条边的5阶简单无向图和3条边的3阶简单无向图。

离散数学（图论部分）1-4章习题课1. 证明：在10个人中，或有3人互相认识，或有4人互不认识。

证：设x为10人中之任意某人，则在余下9人中：(1) x至少认识其中4人，或(2) x至多认识其中3人（即至少不认识其中6人），两者必居其一。

(1) 若此x认识的4人互不相识，命题得证；否则，互相认识的2人加上x构成互相认识的3人，命题得证。

(2) 若此x不认识的6人中有3人互相认识，命题得证；否则，由Ramsey(3,3)=6知，此6人中至少有3人互不认识，此3人加上x为互不认识的4人，命题得证。

2. 设(a) V={a,b,c,d}，A={<a,b>,<a,c>,<b,c>,<b,d>,<c,d>}(b) V={a,b,c,d,e}，E={(a,b),(a,c),(b,c),(d,e)}画出上述图的图解。

解：略。

3. 试找出K3的全部子图，并指出哪些是生成子图。

解：K3共有17个子图。

其他略。

4. 证明：在至少有2人的团体中，总存在2个人，他们在这个团体中恰有相同数目的朋友。

解：在n个人的团体中，各人可能有的朋友数目为0, 1, 2, 3, …, n-1，共n个数，但其中0和n-1 不能共存，故n个人事实上可能的朋友数目只有n-1个。

由鸽巢原理，命题得证。

5.某次宴会上许多人互相握手。

证明：必有偶数个人握了奇数次手。

证：以人为顶点，握手关系为邻接关系构造一个无向图。

由图的性质，奇数度的顶点必为偶数个，即握了奇数次手的人数必为偶数。

6. 证明：Ramsey(3,4)=9。

（提示：题1的推广）证：在9个人中，不可能每个人都恰好认识其他的3个人（即图的9个顶点不可能每个顶点的度都为3，否则违反图的奇数度的顶点必为偶数个的性质）。

设x不会恰好认识其他的3个人（即deg(x)≠3），则在余下8人中：：(1) x至少认识其中4人，或(2) x至多认识其中2人（即至少不认识其中6人），两者必居其一。

习题十1. 设G 是一个(n ，m)简单图。

证明：，等号成立当且仅当G 是完全图。

证明：（1）先证结论：因为G 是简单图，所以G 的结点度上限 max(d(v)) ≤ n-1, G 图的总点度上限为 max(Σ(d(v)) ≤ n ﹒max(d(v)) ≤ n(n-1) 。

根据握手定理，G 图边的上限为 max(m) ≤ n(n-1)/2,所以。

（2） =〉G 是完全图 因为G 具有上限边数，假设有结点的点度小于n-1,那么G 的总度数就小于上限值，边数就小于上限值，与条件矛盾。

所以，G 的每个结点的点度都为n-1，G 为完全图。

G 是完全图 =〉 因为G 是完全图，所以每个结点的点度为n-1, 总度数为n(n-1)，根据握手定理，图G 的边数 。

■2. 设G 是一个（n ，n +1）的无向图，证明G 中存在顶点u ，d （u ）≥3。

证明：反证法，假设,则G 的总点度上限为max(Σ(d(u)) ≤2 n ，根据握手定理，图边的上限为max(m) ≤ 2n/2=n 。

与题设m = n+1，矛盾。

因此，G 中存在顶点u ，d （u ）≥3。

■3．确定下面的序列中哪些是图的序列，若是图的序列，画出一个对应的图来: （1）（3，2，0，1，5）； （2）（6，3，3，2，2） （3）（4，4，2，2，4）； （4）（7，6，8，3，9，5）解：除序列（1）不是图序列外，其余的都是图序列。

因为在（1）中，总和为奇数，不满足图总度数为偶数的握手定理。

可以按如下方法构造满足要求的图：序列中每个数字ai 对应一个点，如果序列数字是偶数，那么就在对应的点上画ai/2个环，如果序列是奇数，那么在对应的点上画(ai-1)/2个环。

最后，将奇数序列对应的点两两一组，添加连线即可。

下面以（2）为例说明：(6 , 3, 3, 2, 2 ) 对应图G 的点集合V= { v 1,v 2,v 3,v 4,v 5}每个结点对应的环数(6/2, (3-1)/2, (3-1)/2, 2/2,2/2) = (3,1,1,1,1)v 1v 5v 3v 4v 2将奇数3，3 对应的结点v 2,v 3一组，画一条连线其他序列可以类式作图，当然大家也可以画图其它不同的图形。

1、一个7阶无向简单图，其结点的最大度数为（）A、5B、6C、7D、82、设G为7阶无向简单图，下列命题成立的是（）A、G的每个结点度数均为3B、G的每个结点度数均为5C、G的每个结点度数均为6D、G的每个结点度数均为73、由4个点3条边构成的无向简单图中，结点的最大度数为（）A、1B、2C、3D、44、(多选题)下列度数列，可以简单图化的是（）A、5,5,4,4,2,1B、5,5,4,1,1C、5,4,4,2,1D、5,4,3,2,2E、4,4,3,3,2,2F、4,3,2,1G、3,3,2,2,1,1H、3,3,3,1I、3,3,1,15、下列可作为4阶无向简单图的结点度数序列是（）A、1,2,3,4B、0,2,2,3C、1,1,2,2D、1,3,3,38、下列关于图的命题正确的是（）A、欧拉图都是哈密顿图B、哈密顿图都是欧拉图C、4阶以上的完全图都是欧拉图D、4阶以上的完全图都是哈密顿图9、下列关于欧拉图的描述正确的是（）A、K4是欧拉图B、K5是欧拉图C、完全图都是欧拉图D、K6是欧拉图13、一棵无向树有5片树叶，3个2度结点，其余都是3度结点，这棵树的结点数是（）A、10B、11C、12D、1314、G是有n个结点，m条边的连通图，要确定G的一棵生成树，必须删去G的多少条边（）A、m-n+1B、m-nC、m+n+1D、n-m+115、一个n阶图不一定是树的是（）A、无回路的连通图B、无回路且有n-1条边C、n阶连通图D、有n-1条边的连通图16、下列6阶无向树的度数序列，对应不止一棵同构树的是（）A、1,1,1,1,2,4B、1,1,1,2,2,3C、1,1,2,2,2,2D、1,1,1,1,3,31、设5阶简单连通图G所有结点的度数之和为18，则G的结点的最大度数为_____，最小度数为______2、4阶完全图K4是平面图，其面数r为_____，记结点数为n，边数为m，则n-m+r=_______3、一个简单无向连通图，有n个结点，m条边，则边数m的最大值为_________，最小值为_______4、7阶无向简单图G，最多有________条边5、连通平面图G的每个面至少由5条边围成，则G的边数m与顶点数n满足的不等式关系为______________6、连通平面图G共有8个顶点，其平面表示中共有6个面，则边数为______7、如题的9阶无向图，需要添加边使其称为欧拉图，至少需要添加_____________和______________8、一棵n(n>2)阶无向树T，其最大度数⊿(T)的最小值为_____，最大值为________9、一棵7阶树T，其分支点最多有____个，最多有____片树叶10、无向完全图K8，需要删掉______条边才能得到生成树；无向完全图K9，需要删掉______条边才能得到生成树11、无向树有4个3度分支点，2个2度分支点，其余为树叶，则树叶数为______12、设无向树有8片树叶，1个4度分支点，其余都是3度分支点，则该树共有______个结点1、研究4阶完全图K4，判断其是否存在欧拉回路？是否存在哈密顿回路？如果存在，共有多少个非同构的回路？2、9阶无向图G中，每个结点的度数不是5就是6，证明：G中至少有5个6度结点或至少有6个5度结点。

第6-7章一．选择/填空1、设图G 的邻接矩阵为0101010010000011100000100，则G 的边数为( D )． A ．5 B ．6 C ．3 D ．42、设有向图（a ）、（b ）、（c ）与（d ）如下图所示，则下列结论成立的是( A )．A ．（a ）是强连通的B ．（b ）是强连通的C ．（c ）是强连通的D ．（d ）是强连通的3、给定无向图G 如下图所示，下面给出的结点集子集中，不是点割集的为（ B ）．A ．{b , d }B ．{d }C ．{a , c }D ．{b , e }4、图G 如下图所示，以下说法正确的是 ( D ) ．A ．{(a , c )}是割边B ．{(a , c )}是边割集C ．{(b , c )}是边割集D ．{(a, c ) ,(b, c )}是边割集5、无向图G 存在欧拉通路，当且仅当(D )．A ．G 中所有结点的度数全为偶数B ．G 中至多有两个奇数度结点C ．G 连通且所有结点的度数全为偶数D ．G 连通且至多有两个奇数度结点6、设G 是有n 个结点，m 条边的连通图，必须删去G 的( A )条边，才能确定G 的一棵生成树．A ．1m n −+B ．m n −C ．1m n ++D ．1n m −+7、已知一棵无向树T 中有8个结点，4度，3度，2度的分支点各一个，T 的树叶数为（B ）．A ．8B ．5C ．4D ．38、已知图G 中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G 的边数是 15 ． 9、连通无向图G 有6个顶点9条边，从G 中删去 4 条边才有可能得到G 的一棵生成树T ．10、如右图 相对于完全图K 5的补图为（A ）。

11、给定无向图，如下图所示，下面哪个边集不是其边割集（ B ）。

A 、；B 、{<v1,v4>,<v4,v6>};C 、；D 、。

12、设D 是有n 个结点的有向完全图,则图D 的边数为( A ) (A))1(−n n (B))1(+n n (C)2/)1(+n n (D)2/)1(−n n 13、无向图G 是欧拉图,当且仅当( C )(A) G 的所有结点的度数都是偶数 (B)G 的所有结点的度数都是奇数(C)G 连通且所有结点的度数都是偶数 (D) G 连通且G 的所有结点度数都是奇数。