图论作业(1).doc

第三章1.证明：必要性：v是连通图G的割边， 则 ， 至少有两个连通分支。设其中一个连通分支顶点集合为V1,另外连通分支顶点集合为V2,即V1与V2构成V的划分。对于任意的uV1, v V2，如果割边e不在某一条（u，v）路上，那么，该路也是连接G-e中的u与v的路，这与u,v处于G-v的不同分支矛盾。“充分性”若e不是图G的割边，那么G-v连通，因此在G-v中存在u,v路，当然也是G中一条没有经过边e的u,v路。矛盾。7. 证明： v是单图G的割点，则G-v至少两个连通分支。现任取 , 如果x,y在G-v的同一分支中，令u是与x,y处于不同分支的点，那么，通过u，可说明，x与y在G-v的补图中连通。若x,y在G-v的不同分支中，则它们在G-v的补图中邻接。所以，若v是G的割点，则v不是其补图的割点。9.连通图G的一个子图B称为是G的一个块，如果(1), 它本身是块；(2), 若没有真包含B的G的块存在。 又由于对于阶数至少是3的图G是块当且仅当G无环并且任意两点都位于同一圈上。根据题意，对于阶数至少是3的图G，由于G没有偶圈，所以G的每个块的点可以在奇圈上，如果不在奇圈上，则块只能是K2，否则如果不是K2的话，该子图将存在割点，该子图就不是块。 得证。16.（1）（2）（3）第四章3. （1）既是欧拉闭迹又是哈密尔顿圈 （2）（3）（4）7.由于图没有奇度顶点，所以是欧拉图，又定理1可得，图G的边集可以划分为圈C1，C2，。Cm，所以E（G）可以表示成C1，C2.。Cm的并。10.若图不是二连通，则存在割点，由于哈密尔顿图不存在割点，因而G是非哈密尔顿图。若G是具有二分类（X,Y）的偶图，且|X|不等于|Y|，设X中所有点为x1，x2.。xm，Y中的所有点为y1，y2.。yn，若存在哈密尔顿图，则在哈密尔顿圈中必然存在X中的点与Y中的点相互交替出现，但是|X|不等于|Y|，则必然出现某两个点同属于|X|或者|Y|，但是G是偶图，属于同一集合的这样的两个点不可以相连，所以存在哈密尔顿圈矛盾，因而不存在哈密尔顿圈。12. 证明：在G之外加上一个新点v,把它和G的其余各点连接得图G1G1的度序列为： (d1+1,d2+1,dn+1, n)由条件：不存在小于(n+1)/2的正整数m,使得dm+1m,且dn-m+1+1n-m+1=(n+1)-m。于是由度序列判定定理知：G1是H图，得G有H路。第五章1.（1）证明一：证明每个k方体都是k正则偶图。事实上，由k方体的构造：k方体有2k个顶点，每个顶点可以用长度为k的二进制码来表示，两个顶点连线当且仅当代表两个顶点的二进制码只有一位坐标不同。如果我们划分k方体的2k个顶点，把坐标之和为偶数的顶点归入X，否则归入Y。显然，X中顶点互不邻接，Y中顶点也如此。所以k方体是偶图。又不难知道k方体的每个顶点度数为k,所以k方体是k正则偶图。由推论：k方体存在完美匹配。（2）我们用归纳法求K2n和Kn,n中不同的完美匹配的个数。K2n的任意一个顶点有2n-1种不同的方法被匹配。所以K2n的不同完美匹配个数等于(2n-1)K2n-2,如此推下去，可以归纳出K2n的不同完美匹配个数为：(2n-1)!同样的推导方法可归纳出K n, n的不同完美匹配个数为：n!2. 证明：若不然，设M1与M2是树T的两个不同的完美匹配，那么M1M2,且TM1M2每个非空部分顶点度数为2，即它存在圈，于是推出T中有圈，矛盾。6. 证明：由习题5第一题知：K2n的不同完美匹配的个数为(2n-1)!。所以，K2n的一因子分解数目为(2n-1)!个。即：7.将K9进行2因子分解，四个圈为C1=p9 p1 p8 p2 p7 p3 p6 p4 p5 p9C2=p9 p2 p1 p3 p8 p4 p7 p5 p6 p9 C3=p9 p3 p2 p4 p1 p5 p8 p6 p7 p9 C4=p9 p4 p3 p5 p2 p6 p1 p7 p8 p913. 最小权值和是3019. 证明：K4n+