电子科大图论第二次作业(45章)答案

《电子科大图论第二次作业(45章)答案》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

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中的孤立点去掉后的图为G1,则G1也是没

2、有奇度点的，且G1的最小度大于等于2.则G1存在一个圈S1,在G1-S1中去除孤立的点，得到一个新的图G2,显然G2也没有奇度的点，且G2的最小度大于等于2.这样G2中也存在一个圈S2,这样一直下去，指导Gm中有圈Sm,且Gm-Sm都是孤立的点。这样玖G)=玖G1)并E(G2)・・・并E(Gm).命题得证。10・证明：若：(1)G不是二连通图，或者(2)G是具有二分类(XtJ的偶图,这里I却建

3、£

4、,则G是非Hamilton图。证明：(1)G不是二连通图，贝IJG不连通或者存在割点y有w(G-v)>2,由于课本上的相关定理：

5、若G是Hamilton图，则对于v(G)的任意非空顶点集S,有：伙(G-S)£

6、S

7、,则该定理的逆否命题也成立，所以可以得岀：若G不是二连通图,则G是非Hamilton图(2)因为G是具有二分类(齐¥)的偶图，又因为

8、X

9、

10、¥

11、,在这里假设

12、X

13、V肌则有w(G-X)=

14、Y

15、>凶,也就是说：对于¥(G)的非空顶点集S,有：

16、S

17、成立，则可以得出则G是非Hamilton图。习题五1.(1)证明：每个k方体都有完美匹配(k大于等于2)(2)求心和Kg屮不同的完美匹配的个数。证明一：证明每个k方体都是k正则偶图。事实上，由k方体的构

18、造：k方体有2*个顶点，每个顶点可以用长度为k的二进制码来表示，两个顶点连线当且仅当代表两个顶点的二进制码只有一位坐标不同。如果我们划分k方体的2*个顶点，把坐标之和为偶数的顶点归入X,否则归入Y。显然，X中顶点互不邻接，Y屮顶点也如此。所以k方体是偶图。又不难知道k方体的每个顶点度数为k,所以k方体是k正则偶图。由推论：k方体存在完美匹配。证明二：直接在k方体中找出完美匹配。设k方体顶点二进制码为(X],X2,・・・,Xk),我们取(X1,X2,…,Xk・l,0),和(X

19、,X2,・・・,Xk」,l)Z间的全体边所成Z集为

20、M.显然，M屮的边均不相邻接，所以作成k方体的匹配，又容易知道:

21、M

22、=2k-!.所以M是完美匹配。(2)我们用归纳法求K2n和K"中不同的完美匹配的个数。K2n的任意一个顶点有2n-l种不同的方法被兀配。所以K"的不同完美匹配个数等于(2n・l)K2n・2,如此推下去，可以归纳岀K2n的不同完美匹配个数为：(2n-l)!!同样的推导方法可归纳出Kn,n的不同完美匹配个数为：n!6・证明：K2n的1■因子分解的数目为(2n)!/(2An*n!)o因为K2n的不同完美匹配的个数为(2ml)!!。所以，K2n的一因子分解数目为(

23、2n-l)!!个，即2n)!/(2An*n!),命题得证。7・将K今表示为四个生成圈Z和。证明：K4n+1=K2(2n)+i,所以，可以分解为2n个边不重的2因子之和。而K爭=所以心可以表示为四个边不重的2因子之和，对于每个分解出的因子的路径为:X=叩7出勺小就Vg7"¥附,则K》的四条路径为：%=耳险巾丹VgV声4%,叫=V2¥1VaY9¥4¥7¥&¥6,%=勺巾勺勺％y尹弘=耳巾％巾％勺片V8，则生成圈Ht是％相与R的两个端点连线生成的。所以可以将K号表示为四个生成圈Z和。13.P?V2・玄卩因・致扌"％升力二二.gvw

24、币&戈玄丫壬丸“用头匕・;支丁为毎7%杀弋勺勺I3r%A用/

25、“灯迈爲盘彳）金夕郦&门RQO0一Io=m戶紅G艸处一乜叽川缺元竜方沖了汐％知冬匕」沏'心7、，薦扌孑加们3金勺7必列部Q^P9型移古2仏皿丿二T.匚二）叩处乘/n金s呻歹门RQ厲久棗农彳呈&»二丿、仍"严忤中镐（I小‘4上2、2,1），心"（上）弭星7了罕小和紡Z

26、?丙迢'所以最小的权值之和为30