您好,欢迎访问三七文档
图论第二次作业一、第四章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)(1G,则1G含圈1C,在去掉)(11CEG的孤立点后,得图2G,显然2G仍无奇度点,且2)(2G,从而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的非平凡简单图,这里nddd21,证明:若不存在小于2)1(n的正整数m,使得mdm且mndmn1,则G有Hamliton路。证明:在G之外加上一个新点v,把它和G的其余各点连接,得图G1:G1的度序列为:),1,,1,1(21ndddn,由已知:不存在小于2)1(n的正整数m,使得mdm1且mnmndmn)1(111。于是由度序列判定定理知:G1是Hamilton路,则G有Hamliton路。二、第五章作业5.1(1)证明:每个k方体都有完美匹配(2k);(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。
本文标题:图论第二次作业
链接地址:https://www.777doc.com/doc-4935772 .html