四川大学离散数学(冯伟森版)课后习题答案习题参考解答(图论部分)

习题十

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,所以。

每个结点对应的环数(6/2, (3-1)/2, (3-1)/2, 2/2,2/2) = (3,1,1,1,1)

证明：本题目，我们是需要说明n阶的简单二部图的边数的最大值 = 即可。

设n阶的简单二部图，其两部分结点集合分别为V1，V2,那么|V1| + |V2| = n。此种情况下，当G为完全二部图时，有最多的边数，即max(m) = |V1||V2|,变形为，max(m) =( n-|V2|)|V2|.此函数的最大值及为n阶二部图的边的上限值，其上限值为当|V2|=n/2 时取得。及max(max(m)) = ,所以n阶二部图(n,m), ■

7. 无向图G有21条边，12个3度数结点，其余结点的度数均为2，求G的阶数n。

解：根据握手定理有： 21 =( 3Χ12 + 2(n-12))/2, 解此方程得n = 15■

8．证明：完全图的点诱导子图也是完全图。

证明：方法1

为证明此结论，我们先证两个引论：

3度点只有1个1度点为其邻接点。因此这两个图不可能同构■

11．证明： 图10.30中的两个图是同构的。

图10.30

解：略■

12. 求具有4个结点完全图K4的所有非同构的生成子图。

解：我们可以把生成子图按总度数不同进行分类，同的子图类中，再去找出不同购的子图。因此求解如下： Σd(v) = 0: (0,0,0,0) =2: (1,1,0,0)

=4: (2,1,1,0) (1,1,1,1)

=6: (3,1,1,1) (2,2,1,1)(2,2,2,0) =8: (2,2,2,2) (3,2,2,1) =10: (3,3,2,2) =12: (3,3,3,3)

总共10个不同构生成子图■

13. 设有向图D=<V,E>

(1) 1，2，3，4的圈 (至少用一种表示法写出它们，并以子图形式画出它们)。

(2) 在图中找出所有长度分别为3，4，5，6

的回路，并以子图形式画出它们。

解：(1)

充分性：

先证明在二部图中，奇长路的道路的两个端节点一定分别在两个顶点集合中，对道路长度使用归纳法，

（1） 当道路长度为1是，根据二部图的定义，每条边的两个顶点分别在两个点集合中，

结论成立

（2） 假设道路长度为2n-1 ( n≥2)时结论成立

（3） 当道路长度为2n+1时，设P=v1v2…v2n-1v2nv2n+1,在此路径上删除最后两个结点，那

么道路P将变为长度为2n-1的奇长道路，根据假设，v1,v2n-1分别在两个顶点集合中，那么v2n和v1在同一顶点集合中，而v2n+1和v1在不同顶点集合，结论成立

因为G中的任何回路，写成道路的形式，起点和终点时一个结点，当然在同一个顶点集合中，因此长度必为偶数； 必要性：（仅对连通分支证明） 在图中任意取一点着色为白色，将和此点最短距离为奇数的点着色为黑点，为偶数的着色为白点，那么将结点分为白色和黑色连个点集，任何同色点之间没有边相连。否则将形成奇数长度的回路，例如同色结点v1，v2 相邻，那么从初始着色点v开始通过最短路径可以形成如下回路v…v1v2…v,因为v…v1,v2…v长度和为偶数，那么回路v…v1v2…v与题设矛盾。所以是二部图

17.设(n, m)简单图G满足,证明G必是连通图。单图。

证明：假设GG2Σ（ｎｉ－１）ｎｉ（ｎ－（ｎｉ－１）＝（ｎ－１）当k=1时，G是连通图。|V1|=1，（1，0），G2=Kn-1,满足题设条

18. 设G是阶数不小于3的连通图。证明下面四条命题相互等价: (1）G无割边；

(2) G中任何两个结点位于同一回路中；

(3) G中任何一结点和任何一边都位于同一回路中； (4) G中任何两边都在同一回路中。

证明：（1）=〉（2）

因为G连通，且G无割边，所以任意两个结点u,v，都存在简单道路p=u…wv.又因为G无割边，所以，删除边wv后，子图依然连通，即w,v存在简单道路p’,以此类推，可以找到一条核p每条边都不相同的p’’=v…u,这样p和p’’就构成了一条回路。 （2）=〉（3）

因为G中任意两个结点都位于同一回路中，所以任意结点u,和任意边e的两个端点v1,v2都分别在两个回路C1，C2中，如果C1=C2=u…v1…v2…u,那么将回路中v1…v2,用v1v2=e替换，就得到新的新的回路，并满足要求。如果C1≠C2，C1=u…v1…u,C2=u…v2…u,那么构成新的道路P=u…v1…u…v2…u,在其中将重复边剔出掉，得到新的回路C3，其中包含v1,v2结点，可以将回路中v1…v2用v1v2=e替换，就得到新的新的回路，并满足要求. （3）=〉（4）

对任意两条边e1,e2其端点分别为u1,u2,v1,v2。根据（3）存在路C1 = u1…v1v2…u1,C2=u2…v1v2…u2。那么可以形成新的闭道路P=u1…v1v2…u2……重复边剔出到，得到新的回路C3，其中包含e2和u1,u2结点，可以将回路中替换，就得到新的新的回路，包含e1,e2,满足要求. (4)=>(1)

因为任意两条边都在同一回路中，所以不存在割边。假设边e图不G中无割边■

19. 设G=(V,E)是点度均为偶数的连通图。证明:

证明：G-v最多产生d(v)G-vvd(v)/2■

20. 证明:

证明：（1）d(u,v)≥0,0

，两个结点之间的最短距离相等

p=u…v ，即使u到v的最短道路，也是v到u的最短道路。 （3） 假设，那么最短道路P=u…w ,就不是最短道路，因为另一条道路p’■

G中,e为割边的充要条件是它不包含于G的任何圈中。

证明： 1） e为割边 =〉e不包含于G的任何圈中

假设e包含在某一圈Ci中，那么删除此边，但边关联的两个邻接点依然连通，所以没有破坏原图的连通性。因此不是割边，矛盾。所以假设不成立，既e不包含于G的任何圈中；

2）e不包含于G的任何圈中 =〉e为割边

假设e为割边，那么删除此边，生成子图依然连通。e关联的两个邻接点有基本道路存在，此基本道路连同e构成一个圈。与题设矛盾。所以假设不成立，既e为割边。 根据1），2)可知，题设结论成立■

22. 证明:若G是3度正则的简单图,则。（请冯老师帮助解答下）

证明：

23. 证明:在具有n（n≥2）个结点的简单无向图G中，至少有两个结点的度数相同。

证明：此题可用鸽笼原理，因为n个结点的简单无向图G中，结点的度数只可能是0，1，2…n-1

当ｋ为偶数时，道路可扩充为v1…vk/2…u…vk/2+1…vk,而当ｋ为奇数时，不管ｖｋ＋１／２与ｕ之间是如何单向可达的，都可以构造出更长的有向道路，矛盾，所以Ｇ中一定存在包含所有结点的有向道路■

26. 无向图G如图10.32所示，先将此图顶点和边标出，然后求图中的全部割点和割边。

解：将图重新标记如下：

图10.34

解：对图的结点和边进行编号如下：

习题十一

1. 设一个树中度为k的结点数是nk（2≤k），求它的叶的数目。

解：设T的节点总数为n，叶节点数目为t ，根据题意及握手定理有： t + n2 + n3 + …+ nk = n (1)

t + 2n2 + 3n3 + …k(nk) = 2(n-1) (2) 握手定理 (1),(2)联立求解得：

t = n3 + 2n4 + … (k-2)nk + 2■

2. 证明：树T中最长道路的起点和终点必都是T的叶。

证明：假设T中最长道路P=vi1vik或终点不是T的叶结点，设d(vi1vi1的

12l

所有邻接点(v‘,v’…,v’)T,P, 得到

l

回路C= vi1 …’ vi1 .d(vik)>1假设不成立，即最长道路 …… 此处隐藏：4250字，全部文档内容请下载后查看。喜欢就下载吧 ……