图论作业.docVIP

第三章 1.证明： 必要性： v是连通图G的割边， 则 ， 至少有两个连通分支。设其中一个连通分支顶点集合为V1,另外连通分支顶点集合为V2,即V1与V2构成V的划分。 对于任意的u∈V1, 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的其余各点连接得图G1 G1的度序列为： (d1+1,d2+1,…,dn+1, n) 由条件：不存在小于(n+1)/2的正整数m,使得dm+1≦m,且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的两个不同的完美匹配，那么M1ΔM2≠Φ,且T[M1ΔM2]每个非空部分顶点度数为2，即它存在圈，于是推出T中有圈，矛盾。 6. 证明：由习题5第一题知：K2n的不同完美匹配的个数为(2n-1)!!。所以，K2n的一因子分解数目为(2n-1)!!个。即： 7.将K9进行2因子分解，四个圈为 C1=p9 p1 p8 p2 p7 p3 p6 p4 p5 p9 C2=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 p9 13. 最小权值和是30 19. 证明：K4n+1= K 2(2n)+1 , 所以，可以分解为2n个边不重的2因子之和。而任意2个2因子可以并成一个4因子。所以，共可以并成n个4因子。即K4n+1可以分解为n个4因子的和。