图论第二次作业-电子科技大学

图论第二次作业一、第四章4.3（1）画一个有Euler闭迹和Hamilton圈的图；（2）画一个有Euler闭迹但没有Hamilton圈的图；（3）画一个有Hamilton圈但没有Euler闭迹的图；（4）画一个既没有Euler闭迹也没有Hamilton圈的图；解：（1）一个有Euler闭迹和Hamilton圈的图形如下：（2）一个有Euler闭迹但没有Hamilton圈的图形如下：（3）一个有Hamilton圈但没有Euler闭迹的图形如下：（4）一个既没有Euler闭迹也没有Hamilton圈的图形如下：4.7证明：若G没有奇点，则存在边不重的圈C1,C1,....,Cm,使得E(G)=E(C1)E(C2).....E(Cm)。证明：将G中孤立点除去后的图记为G1,则G1也没有奇点，且(G1)2，则G1含圈C1，在去掉G1-E(C1)的孤立点后，得图G2，显然G2仍无奇度点，且(G2)2，从而G2含圈C2，如此重复下去，直到圈Cm，且Gm-E(Cm)全为孤立点为止，于是得到E(G)E(C1)E(C2)...E(Cm)。4.10证明：若（1）G不是二连通图，或者（2）G是具有二分类(X,Y)的偶图，这里|X||Y|，则G是非Hamilton图。证明：（1）因为G不是二连通图，则G不连通或者存在割点V，有w(GV)2，由相关定理得：若G是Hamilton图，则对于V(G)的任意非空顶点集S，有：w(GS)S，则该定理得逆否命题也成立，所以可得：若G不是二连通图，则G是非Hamilton图。（2）因为G是具有二分类(X,Y)的偶图，又因为|X||Y|，在这里假设|X||Y|，则有w(G-X)=YX，也就是说：对于V(G)的非空顶点集S，有：w(G-S)S成立，则可以得出G是非Hamilton图。4.12设G是有度序列(d1,d2,...,dn)的非平凡简单图，这里d1d2...dn，证明：若不存在小于(n+1)/2的正整数m，使得dmm且dn-m+1n-m，则G有Hamliton路。证明：在G之外加上一个新点V，把它和G的其余各点连接，得图G1：G1的度序列为：(d1+1,d2+1...dn+1,n)，由已知：不存在小于(n1)/2的正整数m，使得dm+1m且dn-m+1n-m+1=(n+1)-m。于是由度序列判定定理知：G1是Hamilton路，则G有Hamliton路。二、第五章作业5.1（1）证明：每个k方体都有完美匹配（k2）;（2）求K2n和Kn,n中不同的完美匹配的个数。证明：（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)!!；利用同样的方法可归纳出Kn,n的不同完美匹配个数为：n!。5.2证明：一棵树最多只有一个完美匹配。证明：若不然，设M1和M2是树T的两个不同的完美匹配，那么M1M2，容易知道：T[M1M2]每个非空部分顶点度数为2，即它存在圈，于是推出T中有圈，矛盾。所以一棵树最多只有一个完美匹配。5.6证明：K2n的1-因子分解的数目为(2n)!/2nn!。证明：由结论知：K2n不同完美匹配的个数为(2n-1)!!。所以，K2n的1-因子分解数目为(2n-1)!!个。即：(2n-1)!!=(2n)!/2nn!5.7将K9表示为四个生成圈之和。解：K4n+1=K2(2n)+1，所以，可以分解成2n个边不重的2因子之和。而K9=K2*4+1。所以K9可以表示为四个边不重的2因子之和，对于每个分解出的因子的路径为：Pi=ViVi-1+Vi+1Vi-2+Vi+2Vi-3...VinVin则K9的四条路径为：P1=V1V8V2V7V3V6V4V5P2=V2V1V3V8V4V7V5V6P3=V3V2V4V1V5V8V6V7P4=V4V3V5V2V6V1V7V8则生成圈Hi是V2n+1与Pi的两个端点连线生成的。所以可将K9表示为四个生成圈之和。5.13所谓n×n矩阵的一条对角线是指两两不同行不同列的n个矩阵元素组成的集。对角线的权是指它的n个元素的和。找出下列矩阵具有最小权的对角线：897547101366691258475671110854解：首先从第一行第一列开始，找出矩阵中的最小元素，发现为坐标是(1,1)的4，将其所在的行和列删除，得到的矩阵为4756691257101368975再从此矩阵的第一行第一列开始，找出矩阵中的最小元素，发现为原坐标是(2,5)的4。依次类推，继续得到坐标是(3,2)的5，(5,3)的7，(4,4)的10。所以最小权为：4+4+5+7+10=30。5.19证明:对n1,K4n+1有一个4-因子分解。证明:K4n+1=K2(2n)+1所以，可以分解为2n个边不重的2因子之和。而任意2个2因子可以并成一个4因子。所以，共可以并成n个4因子。即K4n+1可以分解为n个4因子的和。