下载文档原格式
第9章习题解答9. 1有5片树叶.分析设T有x个1度顶点(即树叶)•则T的顶点数n = 3 + 2 + x = 5 + x,T的边数m = n- \ =4 + x.由握手定理得方程.2m = 2(4 + x) = y^J(v f) = 3x3 + 2x2 + l- x = 13 + x./=1由方程解出*5.所求无向树T的度数列为1, 1, 1, 1, 1, 2, 2, 3, 3, 3.由这个度数列可以画多棵非同构的无向树，图9. 6给出的4棵都具有上述度数列，且它们是非同构的.9.2 T中有5个3度顶点.分析设T中有x个3度顶点，则T中的顶点数n = l + x,边数加= "-l = 6 + x,由握手定理得力程.2m = 12 + 2x =》d（片）=3x + 7/=!rtl方程解出x=5.所求无向树T的度数列为1, 1, 1, 1, 1, 2, 2, 3, 3, 3.由这个度数列可以画多棵非同构的无向树，图9.6给出的4棵都具有上述度数列，且它们是非同构的.9.2 T中有5个3度顶点.要析设T中有x个3度顶点，则T中的顶点数"7 +小边数加1=6 + .由握手定理得方程.由此解出"5,即T中有5个3度顶.T的度数列为1, 1, 1, 1, 1, 1, 1, 3, 3, 3, 3, 3.由于T中只有树叶和3度顶点, 因而3度顶点可依次相邻，见图9. 7所示.还有棵与它非同构的树，请读者自己i田i出.9. 3力肛-1条新边才能使所得图为无向树.分析设具有£个连通分支的森林为G,则G有k个连通分支人込，…八/全为树，心1,2,…&加新边不能在7；内部加，否则必产生回路.因而必须在不同的小树之间加新边.每加一条新边后，所得到的森林就减少一个连通分支.恰好加-1条新边，就使得图连通且无回路，因而是树•在加边过程屮，只需注意，不在同一人连通分支中加边.下面给出一种加边方法,取v,为7；中顶点，加新边(v,,v,+l)z = l,2,---J-l,则所得图为树, 见图9. 8给出的一个特例.图中虚线边为新加的边.9. 4不一定.分析n阶无向树T具有“-I条边，这是无向树T的必要条件，但不是充公条件•例如，阶圈(即“-1个顶点的初级回路) 和一个孤立点组成无向简单图具有”-1条边，但它显然不是树.图9.89. 5非同构的无向树共有2棵，如图9. 9所示.困9.9分析由度数列1, 1, 1, 1,2,2, 4不难看出，唯一的4度顶点必须与2度顶点相邻，它与1个2度顶点相邻，还是与两个2度顶点都相邻，所得树是非同构的，再没有其他情况. 因而是两棵非同构的树. o 、O O9.6有两棵非同构的生I ，——V(1) (2)成树，见图9. 10所示. 图9.10分析图9. 10是5阶图(5个顶点的图)，5阶非同构的无向树只有3棵，理由如下.5 阶无向树中，顶点数"=5,边数加=4,各顶点度数Z和为&度数分配方案有3种,分别为①1, 1, 1, 1,4;②1, 1, 1,2,3;③1, 1,2, 2. 2.每种方案只有一棵非同构的树•图9.10所示的5阶图的非同构的生成树的度数列不能超出以上3种，也就是说，它至多有3棵非同构的生成树，但由于图中无4度顶点，所示，不可能有度数列为①的生成树，于是该图最多有两棵非同构的生成树.但在图9. 10中已经找出了两个非同构的生成树, 其中(1)的度数列为③，(2)的度数列为②，因而该图准确地有两棵非同构的牛成树.9. 7 基本回路为：C c = cbad,C e = ead,C g = gfa,C h =hfab.基本回路系统为{C c,C e,C g,C h}.基本回路系统为{S a,S h,S d,S f}.分析1°注意基本回路用边的序列表示，而基本割集用边的集合表示.2°基本回路中，只含一条弦，其余的边全为树枝，其求法是这样的：设弦e = (fj),则％,Vj在生成树T中，且在T中, 之间存在唯一的路径「订与e = (v,,v y)组成的回路为G中对应弦e的基本回路.3°基本割集中，只含一条树枝，其余的边都是弦，其求法是这样的:设树枝e = (i;,Vj),则e为T中桥,于是T-e (将e从T 中支掉)，产生两棵小树7；和0，则={e \e在G中且e的两端点分别在7；和3中} S。
§5.2 图的连通性习题5.21．证明或否定：（1）简单图G 中有从点u 到点v 的两条不同的通路，则G 中有基本回路。
（2）简单图G 中有从点u 到点v 的两条不同的基本通路，则G 中有基本回路。
解：（1）简单图G 中有从点u 到点v 的两条不同的通道，则G 中有回路。
（2）简单图G 中有从点u 到点v 的两条不同的路，则G 中有回路。
解 （1）不一定：如下图，点1与点3之间有两条通道：（1、2、3）和（1、2、1、2、3），但图中没有回路。
（2）一定：设两条路分别为),,,,,(211v x x x u L m =和),,,,,(212v y y y u L n =。
若对m i ≤≤1，n j ≤≤1有j i y x ≠，则),,,,,,,,,,(12121u y y y y v x x x u n n m -是一条回路。
否则假设l k y x =且是离u 最近的一对（即对k i ≤≤1，l j ≤≤1，不存在j i y x =），则),,,,,,,,,(12121v y y y x x x u l k -是一条回路。
2．设G 是简单图，)(G δ≥2，证明G 中存在长度大于或等于1)(+G δ的基本回路。
证：以图G 中一点v 1出发，与之相邻的点设为v 2，由于)(G δ≥2，则v 2至少还有一个邻接点，设为v 3，若v 3与v 1邻接，则形成长度为1)(+G δ的基本回路，则若v 3不与v 1邻接，则至少还有一个邻接点，设为v 4，若v 4与v 1或v 2邻接，则形成长度为大于或等于1)(+G δ的基本回路，若v 4与v 1和v 2都不邻接，至少还有一个邻接点，设为v 5，…，依次类推，一定可以到达最后一个顶点v i ，由于)(G δ≥2，则除了v i -1外，一定会与前面的某个顶点邻接，就会形成长度为大于或等于1)(+G δ的基本回路。
3．证明：若连通图G 不是完全图，则G 中存在三个点w v u ，，，使E v u ∈)(，，E w v ∈)(，，E w u ∉)(，。
图论课后习题答案图论是数学中的一个分支，主要研究图的结构和性质。
图论的课后习题通常包括证明题、计算题和应用题。
下面给出一些典型的图论课后习题答案：1. 证明题：证明一个图是连通的当且仅当它的任意两个顶点都存在一条路径相连。
答案：首先定义连通图的概念：一个图是连通的，如果对于任意两个顶点，都存在一条路径将它们连接起来。
接下来，我们证明两个方向：- 如果一个图是连通的，那么对于任意两个顶点\( u \)和\( v \)，根据定义，必然存在一条路径\( P \)将它们连接起来。
- 反之，如果对于任意两个顶点\( u \)和\( v \)，都存在一条路径将它们连接起来，那么我们可以构造一个从任意顶点\( u \)出发，访问图中所有顶点的路径，这表明图是连通的。
2. 计算题：给定一个有\( n \)个顶点的完全图，计算它的边数。
答案：在完全图中，每个顶点都与其他所有顶点相连。
因此，对于一个顶点，它将与\( n-1 \)个其他顶点相连。
但是，每条边被计算了两次（因为它连接了两个顶点），所以边数应该是\( \frac{n(n-1)}{2} \)。
3. 应用题：在一个社交网络中，每个用户可以与其他人建立联系。
如果一个用户与至少一半的用户建立了联系，那么这个社交网络是连通的吗？答案：是的，这个社交网络是连通的。
假设社交网络中有\( n \)个用户，如果一个用户与至少\( \lceil \frac{n}{2} \rceil \)个用户建立了联系，那么我们可以构造一条从任意用户\( u \)到这个中心用户的路径。
由于中心用户与至少一半的用户建立了联系，我们可以继续通过这些联系到达其他用户，从而证明社交网络是连通的。
4. 证明题：证明在任何图中，边数至少是顶点数减一。
答案：考虑一个图的生成树，它是一个最小的连通子图，包含图中的所有顶点，并且没有环。
在生成树中，边数等于顶点数减一。
由于任何图都至少包含一个生成树，因此原图的边数至少与生成树的边数相同，即至少是顶点数减一。
第九章 图9.1设},,,,{y x w v u V =，画出图),(E V G =，其中：（1）)},(),,(),,(),,(),,{(y x y v w v x u v u E =（2）)},(),,(),,(),,(),,{(y x y w x w w v v u E =再求各个顶点的度数。
解（1）见图9.1(a )。
其中顶点u 的度数是2，顶点v 的度数是3，顶点x 的度数是2，顶点y 的度数是2，顶点w 的度数是1。
图9.1 习题1图（2）见图9.1(b )。
其中顶点u 的度数是1，顶点v 的度数是2，顶点x 的度数是2，顶点y的度数是2，顶点w 的度数是3。
9.2 设G 是具有4个顶点的完全图。
（1）画出图G 。
（2）画出G 的所有互不同构的生成子图？解（1）如图9.2(1)所示。
图9.2(1) 习题2图（2） 如图9.6(2)所示﹒ ﹒ ﹒ ﹒ ﹒ ﹒图9.2(2) 习题2图9.3 一个无向简单图，如果同构于它的补图，则称这个图为自互补图。
（1）试画出五个顶点的自互补图。
（2）证明一个自互补图一定只有k 4或14+k 个顶点（k 为整数）。
解（1）(a) (b)图9.3 习题3图 （2）因为n 个顶点的无向完全图有)1(21-n n 条边，所以自互补图有)1(41-n n 条边，因此，k n 4=或14+k 。
9.4 画出两个不同构的简单无向图。
每一个图都仅有6个顶点，且每个顶点都均是3度，并指出这两个图为什么不同构。
解图9.4 习题9.4图9.5 证明任意两个同构的无向图，一定有一个同样的顶点度序列。
顶点度序列是一组按大小排列的正整数。
每一个数对应某一个顶点的度数。
证明两个同构的无向图，度数相同的顶点数目一定相同，这样才能够建立起顶点之间的一一对应关系，进而建立起边的对应关系。
所以，任意二个同构的无向图，一定有一个同样的顶点度序列。
9.6图9.6中所给的图(a )与图(b )是否同构？为什么？(a )(b ) 图9.6 习题6图 解左图9.2（a ）中次数为4的点，与3个度数为1，一个度数为2的顶点相邻接，右图9.2（b ）中度数为4的点，却与3个度数为1，一个度数为3的顶点相邻接。
1、设简单图G所有结点的度数之和为12，则G一定有_____条边。
问题反馈【教师释疑】正确答案：【6 】62、设X={a,b,c},Ix是X上恒等关系，要使Ix∪{〈a,b〉，〈b,c〉，〈c,a〉，〈b,a〉}∪R为X 上的等价关系，R应取_______. 问题反馈【教师释疑】正确答案：【{〈a,c〉,〈c,b〉} 】{〈a,c〉,〈c,b〉}3、命题公式的任意两个不同极小项的合取式一定为_________. 问题反馈【教师释疑】正确答案：【永假式】永假式4、一个公式在等价意义下，_______范式写法是唯一的。
问题反馈【教师释疑】正确答案：【主析取】主析取5、若P：他聪明；Q：他用功；则“他虽聪明，但不用功”，可符号化为_______ 问题反馈【教师释疑】正确答案：【P∧┐Q 】P∧┐Q6、设R是A上的二元关系,且RRR为R的子集,可以肯定R应是_____关系。
问题反馈【教师释疑】正确答案：【传递】传递7、设集合A＝{1, 2, 3, 4}，A上的二元关系R＝{(1,1),(1,2),(2,3)}, S＝{(1,3),(2,3),(3,2)}。
则R×S ＝__________________, 问题反馈【教师释疑】正确答案：【{(1,3),(2,2)} 】{(1,3),(2,2)}8、设谓词的定义域为{a, b},将表达式"任意xR(x)→彐xS(x)"中量词消除，写成与之对应的命题公式是__________________. 问题反馈【教师释疑】正确答案：【(R(a)∧R(b))→(S(a)∨S(b)) 】(R(a)∧R(b))→(S(a)∨S(b))9、设集合A,B，其中A＝{1,2,3}, B= {1,2}, 则A - B＝____________________; 问题反馈【教师释疑】正确答案：【{3} 】{3}10、设G是完全二叉树，G有7个点，其中4个叶点，则G的总度数为__________ 问题反馈【教师释疑】正确答案：【12 】1211、设A、B为两个集合, A= {1,2,4}, B = {3,4}, 则从A∩B＝_________________________; 问题反馈【教师释疑】正确答案：【{4} 】{4}12、设A={a, b, {a, b}}，B={a, b}，则B－A =________ 问题反馈【教师释疑】正确答案：【Φ】Φ13、设G是具有8个顶点的树，则G中增加_________条边才能把G变成完全图。
离散数学图论答案【篇一：离散数学图论习题】综合练习一、单项选择题1．设l是n阶无向图g上的一条通路，则下面命题为假的是( )． (a) l可以不是简单路径，而是基本路径 (b) l可以既是简单路径,又是基本路径 (c) l可以既不是简单路径，又不是基本路径 (d) l可以是简单路径，而不是基本路径答案：a2．下列定义正确的是( )．(a) 含平行边或环的图称为多重图(b) 不含平行边或环的图称为简单图 (c) 含平行边和环的图称为多重图(d) 不含平行边和环的图称为简单图答案：d3．以下结论正确是 ( )．(a) 仅有一个孤立结点构成的图是零图 (b) 无向完全图kn每个结点的度数是n (c) 有n(n1)个孤立结点构成的图是平凡图(d) 图中的基本回路都是简单回路答案：d4．下列数组中，不能构成无向图的度数列的数组是( )． (a)(1,1,1,2,3) (b) (1,2,3,4,5) (c) (2,2,2,2,2) (d) (1,3,3,3) 答案：b5．下列数组能构成简单图的是( )． (a) (0,1,2,3)(b) (2,3,3,3)(c) (3,3,3,3)(d) (4,2,3,3) 答案：c6．无向完全图k3的不同构的生成子图的个数为（）． (a) 6 (b)5(c) 4 (d) 3 答案：c7．n阶无向完全图kn中的边数为（）．(a)n(n?1)n(n?1)(b) (c) n (d)n(n+1) 22答案：b8．以下命题正确的是( )．(a) n(n?1)阶完全图kn都是欧拉图(b) n(n?1)阶完全图kn都是哈密顿图(c) 连通且满足m=n－1的图v,e(?v?=n,?e?=m)是树 (d) n(n?5)阶完全图kn都是平面图答案：c10．下列结论不正确是( )．(a) 无向连通图g是欧拉图的充分必要条件是g不含奇数度结点(b) 无向连通图g有欧拉路的充分必要条件是g最多有两个奇数度结点 (c) 有向连通图d是欧拉图的充分必要条件是d的每个结点的入度等于出度(d) 有向连通图d有有向欧拉路的充分必要条件是除两个结点外，每个结点的入度等1于出度答案：d11．无向完全图k4是（）．（a）欧拉图（b）哈密顿图（c）树答案：b12．有4个结点的非同构的无向树有 ( )个．(a) 2 (b) 3(c) 4(d) 5 答案：a13．设g是有n个结点，m条边的连通图，必须删去g的( )条边，才能确定g的一棵生成树．(a) m?n?1 (b) n?m (c) m?n?1 (d) n?m?1 答案：a14．设g是有6个结点的完全图，从g中删去( )条边，则得到树． (a) 6 (b) 9 (c) 10 (d) 15 答案：c二、填空题1．数组{1，2，3，4，4}是一个能构成无向简单图的度数序列，此命题的真值是 . 答案：02．无向完全图k3的所有非同构生成子图有个．答案：43．设图g??v,e?，其中?v??n,?e??m．则图g是树当且仅当g是连通的，且m?．答案：n－14．连通图g是欧拉图的充分必要条件是答案：图g无奇数度结点 5．连通无向图g有6个顶点9条边，从g中删去g的一棵生成树t．答案：46．无向图g为欧拉图，当且仅当g是连通的，且g中无答案：奇数度7．设图g??v,e?是简单图，若图中每对结点的度数之和，则g一定是哈密顿图．答案：?8．如图1所示带权图中最小生成树的权是．答案：12三、化简解答题1．设无向图g＝v,e，v={v1，v2，v3，v4，v5，v6}， e={( v1，v2), ( v2，v2), ( v4，v5), ( v3，v4), ( v1，v3),( v3，v1), ( v2，v4)}． (1) 画出图g的图形；2图15图22(2) 写出结点v2, v4，v6的度数； (3) 判断图g是简单图还是多重图．解：(1) 图g的图形如图5所示．(2) deg(v2)?4,deg(v4)?3,deg(v6)?0．(3) 图g是多重图．作图如图2. 2．设图g＝v，e，其中v＝{a,b,c,d,e}, e={(a,b),(b,c),(c,d), (a,e)}试作出图g的图形，并指出图g是简单图还是多重图？是连通图吗？说明理由.b e解：图g如图8所示．. 图g中既无环，也无平行边，是简单图． cd 图g是连通图．g中任意两点都连通.图3所以，图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?23x?24?21?18?27x＝9 故图g有9个结点．图4满足该条件的简单无向图如图4所示2．设图g(如图5表示)是6个结点a,b,c, d,e,f的图，试求，图g的最小生成树，并计算它的权．c 解：构造连通无圈的图，即最小生成树，用克鲁斯克尔算法：第一步：取ab＝1；第二步：取af=4第三步：取fe＝3；第四步：取ad=9图5 第五步：取bc=23如图6．权为1+4+3+9+23=403．一棵树t有两个2度顶点，1个3度顶点；3个4问它有几片树叶？解：设t有n顶点，则有n－1条边．t中有2个 2度顶点，1个3度顶点，3个4度顶点，其余n－2－1-3个1度顶点．五、证明题1．若无向图g中只有两个奇数度结点，则这两个结点一定是连通的．证：用反证法．设g中的两个奇数度结点分别为u和v．假若u和v不连通．即它们之间无任何通路，则g至少有两个连通分支g1，g2，且u和v分别属于g1和g2，于是g1和g2各含有一个奇数度结点．这与握手定理的推论矛盾．因而u和v一定是连通的．3【篇二：离散数学图论练习题】题1、设g是一个哈密尔顿图，则g一定是()。
习题91. 设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)将奇数3，3 对应的结点v 2,v 3一组，画一条连线其他序列可以类式作图，当然大家也可以画图其它不同的图形。
第8章 习题参考答案1. 在一次10周年同学聚会上，想统计所有人握手的次数之和，应该如何建立该问题的图论模型？解：将每个同学分别作为一个节点，如果两个人握过一次手就在相应的两个节点之间画一条无向边，于是得到一个无向图。
一个人握手的次数就是这个节点与其他节点所连接的边的条数，进而可得出所有人握手的次数之和。
2. 在一个地方有3户人家，并且有3口井供他们使用。
由于土质和气候的关系，有些井中的水常常干枯，因此各户人家要到有水的井去打水。
不久，这3户人家成了冤家，于是决定各自修一条路通往水井，打算使得他们在去水井的路上不会相遇。
试建立解决此问题的图论模型。
解：将3户人家分别看做3个节点且将3口井分别看做另外3个节点，若1户人家与1口井之间有一条路，则在该户人家与该口井对应的节点之间连一条无向边，这样就得到一个无向图。
3. 某人挑一担菜并带一条狼和一只羊要从河的一岸到对岸去。
由于船太小，只能带狼、菜、羊中的一种过河。
由于明显的原因，当人不在场时，狼要吃羊，羊要吃菜。
通过建立图论模型给出问题答案。
解：不妨认为从北岸到南岸，则在北岸可能出现的状态为24=16种，其中安全状态有下面10种：（人，狼，羊，菜），（人，狼，羊），（人，狼，菜），（人，羊，菜），（Φ），（人，羊），（菜），（羊），（狼），（狼，菜）；不安全的状态有下面6种：（人）（人，菜）（人，狼）（狼，羊，菜）（狼，羊）（羊，菜）。
线将北岸的10种安全状态看做10个节点，而渡河的过程则是状态之间的转移，这样就得到一个无向图，如图8-1所示。
图8-1从上述无向图可以得出安全的渡河方案有两种：第1种：（人，狼，羊，菜）→（狼，菜）→（人，狼，菜）→（狼）→（人，狼，羊）→（羊）→（人，羊）→（Φ）。
(人，狼，羊，菜)(人，狼，羊)(人，狼，菜)(人，羊，菜)(人，羊) (狼，菜) (羊) (狼) (菜) (Φ)第2中：（人，狼，羊，菜）→（狼，菜）→（人，狼，菜）→（菜）→（人，羊，菜）→（羊）→（人，羊）→（Φ）。
