(离散数学习题答案ch10ch132015.docVIP

习题十 1、设G是一个（n,m）简单图；证明：m≤C(n,2)等号成立，当且仅当G是完全图 证明：此题有两个内容，第一方面证明简单图满足 m≤C(n,2)，第二证明 ，m=C(n,2)当且仅当G是完全图 (1): 因为在简单无向图中，每个结点的最大度数为n-1，所以图的总度数的上限为n(n-1),所以边的上限为n(n-1)/2，因此任意一个简单无像图G，其边数满足：m≤n(n-1)/2= C(n,2) (2)： m=C(n,2) ? G是完全图 因为，当m=C(n,2)时，全图的总度数为n(n-1),因此其平均点度为(n-1)，因为n阶简单无向图中点度的最大值为（n-1）,所以此时每个点的度数都相同并为（n-1）,根据完全图的定义，此图为完全图 G是完全图? m=C(n,2) 当G为完全图时，既每个结点都和其他结点相邻，所以全图的总边数 m = n(n-1)/2 = C(n,2) 4、证明：在（n,m）图中 δ≤2m/n≤Δ 证明：因为2m/n 代表简单无向图的平均点度值，所以平均值大于等于最小值，小于等于最大值，结论成立 6、设G是（n,m）简单二部图，证明：m≤n2/4 证明：设G的两个顶点集合中顶点个数分别为n1,n2，并有 n = n1 + n2 (1式)；同时，在简单二部图中，当其为完全二部图是，其边数最大，及max(m) = n1 × n2 (2式)；联立（1）（2）式，通过高等数学的知识，当n1=n2=1/2n时，max(m)取得最大值 n2/4 ，所以一般（n,m）简单二部图，其边数小于等于此最大值既 m≤n2/4 9、如果G ≌ G’，称G是自补图；确定一个图为自补图的最低条件：画出一个自补图 解：因为G和自己的补图同构，那么G和G’应该有相等条数的边，所以 m = m’，又因为m + m’= n(n-1)/2，所以G的边的条数必须满足m = n(n-1)/4.因此图G的阶数或阶数减一必需是4的倍数，这就是最低条件。图略（4阶或5阶这样的图都容易画出） 10、判断图10-29中的两个图是否同构，并说明理由 答：这两个图不同构，因为这两个图中，都有唯一的3度点，因此在同构映射中一定相互对应，但一个图中的3度点连接两个一度点，而在另一个图中其3度点只连接了一个一度点，不能相互映射。因此不同构 15、如果u和v是图G中仅有的两个奇数度结点，证明u和v必是连通的 证明：假设u,v分别在图G的两个分中G1,G2中，那么G1，G2各自的总结点度数就是奇数，与握手定理矛盾。因此，u,v必在一个连通分支中，所以是连通的 16、证明：G是二部图当且仅当G的回路都是偶长回路（非平凡图， n1） 证明：（1）先证明在二部图中，所有奇长道路的两个端点必定分别在两个顶点集合中 使用归纳方法： A）当道路长度L(P)=1时，就是图G的边和其两个端点，根据二部图的定义，两个端点分别在两个顶点集合中 B）假设道路长度L(P)=2n+1 (n0)时结论成立，及P=V1V2….V2n+2,其中V1,V2n+2分别属于两个顶点集合 C) 当L(P)=2(n+1)+1 （n0）时，P=V1V2….V2n+2V2n+3V2n+4；当我们删除此道路的最后两个结点，道路长度变为L(P’)=2n+1，根据(B)的假设，那么V1,V2n+2就分别在两个顶点集合。现在把V2n+3加入到道路中，因为V2n+3是V2n+2的邻结点，所以V2n+3在V2n+2的对集中，既和V1在一个顶点集合中；同理V2n+4就在V1的对集中，也就是V1,V2n+4在不同的顶点集合中 综上所述，（1）结论成立 （2）G是二部图 ? G的回路都是偶长的 设C是G中的任意回路，那么C = V1…..V1，假设L(C)为奇数，那么根据（1）的结论，V1,V1应该在不同的集合中，矛盾；所以L(C)必为偶数 G的回路都是偶长的 ? G是二部图 首先，按如下方式对G的连通分支进行着色，任选一个结点，着红色，然后将其所有邻结点着为黑色，（将红色结点标记），然后逐一对黑色结点的邻结点着为红色并标记黑结点，如此往复，值到全部结点着色标记完成，或遇到已着色的结点被重新着色为相反的颜色（此图有奇长度回路）。下面说明，如果是偶长的，那么就是二部图： 证明：从染色的顺序看，红点到黑点之间的距离为单数，红点到红点的距离为双数，并且相同颜色的点不会相邻。所以可以将图的顶点集合分成两个集合，每个集合的点的颜色一致。根据二部图的定义，这是一个二部图。 如果着色过程中出现已着色点被重新着色成相反颜色，例如：v1是开始的红点，如果现在有点为u1点为黑色，并且开始对他的邻结点进行早色，我们发现w1是u1的邻结点，但已经被着色成黑色，那么，我们就