图论第二次作业

图论第二次作业一、第四章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,使得)()()()(21mCECECEGE。证明：将G中孤立点除去后的图记为1G，则1G也没有奇点，且2)(1G，则1G含圈1C，在去掉)(11CEG的孤立点后，得图2G，显然2G仍无奇度点，且2)(2G，从而2G含圈2C，如此重复下去，直到圈mC，且)(mmCEG全为孤立点为止，于是得到)()()()(21mCECECEGE。4.10证明：若（1）G不是二连通图，或者（2）G是具有二分类),(YX的偶图，这里YX，则G是非Hamilton图。证明：（1）因为G不是二连通图，则G不连通或者存在割点v，有2)(vGw，由相关定理得：若G是Hamilton图，则对于v(G)的任意非空顶点集S，有：SSGw)(，则该定理得逆否命题也成立，所以可得：若G不是二连通图，则G是非Hamilton图。（2）因为G是具有二分类),(YX的偶图，又因为YX，在这里假设YX，则有XYXGw)(，也就是说：对于v(G)的非空顶点集S，有：SSGw)(成立，则可以得出G是非Hamilton图。4.12设G是有度序列),,,(21nddd的非平凡简单图，这里nddd21，证明：若不存在小于2)1(n的正整数m，使得mdm且mndmn1，则G有Hamliton路。证明：在G之外加上一个新点v，把它和G的其余各点连接，得图G1：G1的度序列为：),1,,1,1(21ndddn，由已知：不存在小于2)1(n的正整数m，使得mdm1且mnmndmn)1(111。于是由度序列判定定理知：G1是Hamilton路，则G有Hamliton路。二、第五章作业5.1（1）证明：每个k方体都有完美匹配（2k）;（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的两个不同的完美匹配，那么21MM，容易知道：][21MMT每个非空部分顶点度数为2，即它存在圈，于是推出T中有圈，矛盾。所以一棵树最多只有一个完美匹配。5.6证明：K2n的1-因子分解的数目为!2)!2(nnn。证明：由结论知：K2n不同完美匹配的个数为(2n-1)!!。所以，K2n的1-因子分解数目为(2n-1)!!个。即：5.7将K9表示为四个生成圈之和。解：K4n+1=K2(2n)+1，所以，可以分解成2n个边不重的2因子之和。而K9=K2*4+1。所以K9可以表示为四个边不重的2因子之和，对于每个分解出的因子的路径为：则K9的四条路径为：则生成圈Hi是V2n+1与Pi的两个端点连线生成的。所以可将K9表示为四个生成圈之和。5.13所谓nn矩阵的一条对角线是指两两不同行不同列的n个矩阵元素组成的集。对角线的权是指它的n个元素的和。找出下列矩阵具有最小权的对角线：解：首先从第一行第一列开始，找出矩阵中的最小元素，发现为坐标是(1,1)的4，将其所在的行和列删除，得到的矩阵为再从此矩阵的第一行第一列开始，找出矩阵中的最小元素，发现为原坐标是(2,5)的4。依次类推，继续得到坐标是(3,2)的5，(5,3)的7，(4,4)的10。所以最小权为：4+4+5+7+10=30。