资源描述：
《王博图论第二次作业(电子科技大学)》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、习题四3.(1)画一个有Euler闭迹和Hamilton圈的图;(2)画一个有Euler闭迹但没有Hamilton圈的图；(3)画一个有Hamilton圈但没有Euler闭迹的图；(4)画一个即没有Hamilton圈也没有Eulei•闭迹的图;解：找到的图如下：(1)—*个有Euler闭迹和Hamilton圈的图；⑵一*个有Euler闭迹但没有Hamilton圈的图;⑶一个有Hamilton圈但没有Euler闭迹的图;(4)一个即没有Hamilton圈也没有Euler闭迹的图.7•证明：将G中的孤立点去掉后的
2、图为G1,则G1也是没有奇度点的，且G1的最小度大于等于2.则G1存在一个圈S1,在G1-S1中去除孤立的点，得到一个新的图G2,显然G2也没有奇度的点，且G2的最小度大于等于2.这样G2中也存在一个圈S2,这样一直下去，指导Gm中有圈Sm,且Gm・Sm都是孤立的点。这样玖G)=E(G1)并E(G2)・・・并E(Gm).命题得证。10・证明：若：(1)错误!未找到引用源。不是二连通图，或者(2)错误!未找到引用源。是具有二分类错误!未找到引用源。的偶图，这里错误!未找到引用源。，则错误!未找到引用源。是非Ha
3、milton图。证明：(1)错误!未找到引用源。不是二连通图，则错误!未找到引用源。不连通或者存在割点错误!未找到引用源。，有错误!未找到引用源。，由于课木上的相关定理：若错误!未找到引用源。是Hamilton图，则对于错误!未找到引用源。的任意非空顶点集错误!未找到引用源。，有：错误!未找到引用源。，则该定理的逆否命题也成立，所以可以得出：若错误!未找到引用源。不是二连通图，则错误!未找到引用源。是非Hamilton图(2)因为错误!未找到引用源。是具有二分类错误!未找到引用源。的偶图，又因为错误!未找到引
4、用源。，在这里假设错误味找到引用源。，则有错误味找到引用源。,也就是说：对于错误!未找到引用源。的非空顶点集错误!未找到引用源。，有：错误!未找到引用源。成立，则可以得出则错误味找到引用源。是非Hamilton图。习题五1.(1)证明：每个k方体都有完美匹配(k大于等于2)(2)求心和K“中不同的完美匹配的个数。证明一：证明每个k方体都是k正则偶图。事实上，由k方体的构造：k方体有2*个顶点，每个顶点可以用长度为k的二进制码來表示，两个顶点连线当且仅当代表两个顶点的二进制码只有一位坐标不同。如果我们划分k方体
5、的2*个顶点，把坐标之和为偶数的顶点归入X,否则归入Y。显然，X中顶点互不邻接，Y中顶点也如此。所以k方体是偶图。又不难知道k方体的每个顶点度数为k,所以k方体是k正则偶图。由推论：k方体存在完美匹配。证明二：直接在k方体屮找出完美匹配。设k方体顶点二进制码为(X1,X2,…,Xk),我们取(X1,X2,・・・,Xk_l,0),和(X!,X2,…,Xk",l)之间的全体边所成之集为M.显然，M中的边均不相邻接,所以作成k方体的匹配，乂容易知道:所以M是完美匹配。(2)我们用归纳法求K"和Kn,中不同的完美匹配
6、的个数。K2n的任意一个顶点有2nd种不同的方法被匹配。所以K2n的不同完美匹配个数等于(2n・l)K2n_2,如此推下去，可以归纳岀K2n的不同完美匹配个数为：(2n-l)!!同样的推导方法可归纳出Kn,n的不同完美匹配个数为：n!6・证明：K2n的1■因子分解的数目为(2n)!/(2An*n!)o因为K2n的不同完美匹配的个数为(2n-l)!!o所以，K2n的一因子分解数冃为(2n-l)!!个,即2n)!/(2An*n!),命题得证。7・将错误!未找到引用源。表示为四个生成圈Z和。证明：K4n+1=K2(
7、2n)+l,所以，可以分解为2n个边不重的2因子之和。而错误!未找到引用源。。所以错误!未找到引用源。可以表示为四个边不重的2因子之和，对于每个分解岀的因子的路径为：错误!未找到引用源。，则错误!未找到引用源。的四条路径为：错误!未找到引用源。，错误!未找到引用源。，错误!未找到引用源。，错误!未找到引用源。，则牛成圈错误!未找到引用源。是错误!未找到引用源。与错误!未找到引用源。的两个端点连线生成的。所以可以将错误!未找到引用源。表示为四个生成圈之和。13.■ILV2-・致扌"％升二*£V。丙&叹K7壬之庐
8、国头在吸・w0"育讣与•平.N—牛rJ/〕一/习/V■纽右“一/SsTOaS。%r%6o6它苛I:/兀总嗚*z-宅卜冋s用Is"-/“ssmws习厶向可:■1n1grrvq.J?Q1■-l"°<£y一（-）O，&吝Gvfg-P励方旳T袖讪、57、，屜扌3穴门5崗勺7必以丿那^^仏卩!生心卩（s丿二7.ob一（■#o$亀各GvfX-p甌皿估?元％方鬥•了汐杯/V脩叼垃心7、‘爲弓q佔竹、3鹿勺7处句辭
