離散數(shù)學(xué)習(xí)題答案-ch10-ch13-2015

1、6/6習(xí)題十1、設(shè)G是一個(gè)（n，)簡(jiǎn)單圖；證明：mC（n,2）等號(hào)成立,當(dāng)且僅當(dāng)是完全圖證明：此題有兩個(gè)內(nèi)容，第一方面證明簡(jiǎn)單圖滿足 C(n，）,第二證明 ，m=C（n，2)當(dāng)且僅當(dāng)是完全圖（): 因?yàn)樵诤?jiǎn)單無向圖中，每個(gè)結(jié)點(diǎn)的最大度數(shù)為1,所以圖的總度數(shù)的上限為n（n），所以邊的上限為(n-1)/,因此任意一個(gè)簡(jiǎn)單無像圖G，其邊數(shù)滿足：mn（n1)/2= C(，2）（2): m=（n,) G是完全圖因?yàn)?，?dāng)m=C(n,2)時(shí),全圖的總度數(shù)為(n1),因此其平均點(diǎn)度為(n1),因?yàn)閚階簡(jiǎn)單無向圖中點(diǎn)度的最大值為（n1）,所以此時(shí)每個(gè)點(diǎn)的度數(shù)都相同并為（n1）,根據(jù)完全圖的定義，此圖為完全圖G是

2、完全圖 =(n，2）當(dāng)為完全圖時(shí),既每個(gè)結(jié)點(diǎn)都和其他結(jié)點(diǎn)相鄰，所以全圖的總邊數(shù)m = n(1)/2=（,2)4、證明：在（，m）圖中2mn證明:因?yàn)?/ 代表簡(jiǎn)單無向圖的平均點(diǎn)度值，所以平均值大于等于最小值，小于等于最大值,結(jié)論成立6、設(shè)G是（n，m）簡(jiǎn)單二部圖,證明：m2/4證明:設(shè)的兩個(gè)頂點(diǎn)集合中頂點(diǎn)個(gè)數(shù)分別為n1，n2,并有 n =n+ n2 (1式)；同時(shí),在簡(jiǎn)單二部圖中，當(dāng)其為完全二部圖是，其邊數(shù)最大,及max(） = n n2 （式);聯(lián)立(）（2）式，通過高等數(shù)學(xué)的知識(shí)，當(dāng)n1=1/2n時(shí)，max（m）取得最大值 /，所以一般（n，m)簡(jiǎn)單二部圖,其邊數(shù)小于等于此最大值既 mn/

3、9、如果 G,稱G是自補(bǔ)圖；確定一個(gè)圖為自補(bǔ)圖的最低條件：畫出一個(gè)自補(bǔ)圖解:因?yàn)镚和自己的補(bǔ)圖同構(gòu)，那么和應(yīng)該有相等條數(shù)的邊,所以 m m，又因?yàn)閙 + = (n）/2,所以G的邊的條數(shù)必須滿足m = n()/4.因此圖G的階數(shù)或階數(shù)減一必需是4的倍數(shù),這就是最低條件。圖略（4階或5階這樣的圖都容易畫出）10、判斷圖12中的兩個(gè)圖是否同構(gòu)，并說明理由答：這兩個(gè)圖不同構(gòu)，因?yàn)檫@兩個(gè)圖中,都有唯一的3度點(diǎn),因此在同構(gòu)映射中一定相互對(duì)應(yīng),但一個(gè)圖中的度點(diǎn)連接兩個(gè)一度點(diǎn),而在另一個(gè)圖中其3度點(diǎn)只連接了一個(gè)一度點(diǎn),不能相互映射。因此不同構(gòu)15、如果和v是圖G中僅有的兩個(gè)奇數(shù)度結(jié)點(diǎn),證明u和必是連通的證明

4、:假設(shè)u，v分別在圖的兩個(gè)分中1，2中，那么G1,G各自的總結(jié)點(diǎn)度數(shù)就是奇數(shù)，與握手定理矛盾。因此,u，v必在一個(gè)連通分支中，所以是連通的16、證明:G是二部圖當(dāng)且僅當(dāng)G的回路都是偶長回路（非平凡圖,n)證明：（1）先證明在二部圖中,所有奇長道路的兩個(gè)端點(diǎn)必定分別在兩個(gè)頂點(diǎn)集合中使用歸納方法：）當(dāng)?shù)缆烽L度L（）=1時(shí)，就是圖G的邊和其兩個(gè)端點(diǎn)，根據(jù)二部圖的定義，兩個(gè)端點(diǎn)分別在兩個(gè)頂點(diǎn)集合中B）假設(shè)道路長度L（P)2n+ （n0）時(shí)結(jié)論成立，及V2.V2+2,其中V1，Vn2分別屬于兩個(gè)頂點(diǎn)集合C) 當(dāng)L（）=2（n+1） (n0）時(shí),P=V2.V+22n+32n+4;當(dāng)我們刪除此道路的最后兩個(gè)

5、結(jié)點(diǎn)，道路長度變?yōu)椋≒)=2n1，根據(jù)（B）的假設(shè)，那么V1,n+2就分別在兩個(gè)頂點(diǎn)集合。現(xiàn)在把V23加入到道路中，因?yàn)?n+3是V2n+2的鄰結(jié)點(diǎn)，所以Vn+3在V2n2的對(duì)集中，既和V1在一個(gè)頂點(diǎn)集合中；同理V2+4就在V1的對(duì)集中,也就是V1,V2n4在不同的頂點(diǎn)集合中綜上所述，(1)結(jié)論成立()G是二部圖 G的回路都是偶長的設(shè)C是G中的任意回路,那么C=V1V1,假設(shè)（)為奇數(shù)，那么根據(jù)（1)的結(jié)論，V1,V1應(yīng)該在不同的集合中,矛盾；所以L（C）必為偶數(shù) G的回路都是偶長的 G是二部圖首先,按如下方式對(duì)G的連通分支進(jìn)行著色，任選一個(gè)結(jié)點(diǎn)，著紅色，然后將其所有鄰結(jié)點(diǎn)著為黑色，(將紅色結(jié)

6、點(diǎn)標(biāo)記），然后逐一對(duì)黑色結(jié)點(diǎn)的鄰結(jié)點(diǎn)著為紅色并標(biāo)記黑結(jié)點(diǎn),如此往復(fù),值到全部結(jié)點(diǎn)著色標(biāo)記完成，或遇到已著色的結(jié)點(diǎn)被重新著色為相反的顏色（此圖有奇長度回路）.下面說明，如果是偶長的，那么就是二部圖:證明:從染色的順序看，紅點(diǎn)到黑點(diǎn)之間的距離為單數(shù)，紅點(diǎn)到紅點(diǎn)的距離為雙數(shù)，并且相同顏色的點(diǎn)不會(huì)相鄰。所以可以將圖的頂點(diǎn)集合分成兩個(gè)集合，每個(gè)集合的點(diǎn)的顏色一致。根據(jù)二部圖的定義,這是一個(gè)二部圖。如果著色過程中出現(xiàn)已著色點(diǎn)被重新著色成相反顏色，例如：v是開始的紅點(diǎn)，如果現(xiàn)在有點(diǎn)為u點(diǎn)為黑色，并且開始對(duì)他的鄰結(jié)點(diǎn)進(jìn)行早色,我們發(fā)現(xiàn)w是u的鄰結(jié)點(diǎn)，但已經(jīng)被著色成黑色,那么，我們就找到得到v1到1的距離為單數(shù)

7、的道路p1，v1到w1距離為單數(shù)的道路p2,如果p u1w1 + p，就形成一個(gè)回路，此回路為奇數(shù)，與前提矛盾。所以不可能出現(xiàn)這種情況。（注：對(duì)其他分支重復(fù)這種方法,如果遇到孤立結(jié)點(diǎn)，則交替著紅色和黑色)19、設(shè)=(,E)是點(diǎn)度均為偶數(shù)的連通圖，證明：對(duì)任何 uV, （-u） d(u)/證明:因?yàn)镚的點(diǎn)度都為偶數(shù)，因此Gu最多形成d(u）個(gè)奇數(shù)度點(diǎn),而奇數(shù)度點(diǎn)必須成對(duì)出現(xiàn)在連通分支中,所以（G-u）的最大值為d(u）/2，所以(Gu) d(u）/223、證明:在具有n（n2)個(gè)結(jié)點(diǎn)的簡(jiǎn)單無向圖G中,至少有兩個(gè)結(jié)點(diǎn)度數(shù)相同證明:在n個(gè)結(jié)點(diǎn)的簡(jiǎn)單無向圖中,每個(gè)結(jié)點(diǎn)的可能度數(shù)為0、1、21，共種，但

8、是如果有結(jié)點(diǎn)度為0，那么就不存在有結(jié)點(diǎn)度數(shù)為1;同理，有結(jié)點(diǎn)度數(shù)為n1,那就不存在孤立結(jié)點(diǎn)，所以可能的點(diǎn)度只能有n1種，但有n個(gè)結(jié)點(diǎn),所以必有兩個(gè)結(jié)點(diǎn)度數(shù)要相同30、略習(xí)題十一1、設(shè)一個(gè)樹中度為k的結(jié)點(diǎn)數(shù)是k（2）,求它的葉的數(shù)目解：設(shè)中葉結(jié)點(diǎn)數(shù)目為t,那么根據(jù)握手定理，及數(shù)的點(diǎn)邊關(guān)系可以得到：n t + n2+ 3 + + （)d（v）= = t 2 + 3n + + kn= 2（n1） (2)所以: n + 3n3 + nk = 2（+ n2+n3 + nk） = n3+2n4 +（k)nk + 2、證明：樹T中最長簡(jiǎn)單道路的起點(diǎn)和終點(diǎn)必都是T的葉證明： 首先證明在中的任意最長道路中，其起

9、點(diǎn)u和終點(diǎn)v的所有鄰結(jié)點(diǎn)必然在P中，否則此道路可以變長，與最長條件矛盾假設(shè)在T中存在最長道路P,其起點(diǎn)u或終點(diǎn)v不是葉結(jié)點(diǎn)(假設(shè)是u）,那么d（u），及u至少有兩個(gè)鄰結(jié)點(diǎn)1,u2，他們都將出現(xiàn)在道路中，既P uu1uv，因?yàn)閡2是的鄰結(jié)點(diǎn),所以在中就存在C=uu1。u2u的簡(jiǎn)單回路，與樹的基本性質(zhì)矛盾，所以u(píng)，必是葉結(jié)點(diǎn)10、設(shè)e是連通圖G的一條邊,證明：e是G的割邊當(dāng)且僅當(dāng)含于G的每個(gè)生成樹中證明：e是的割邊 含于的每個(gè)生成樹中假設(shè)e不包含在的生成樹T中，那么刪除e邊后，T依然包含在G中，因?yàn)門連通,所以G連通，與是割邊矛盾,所以必包含在的任何生成樹中e含于G的每個(gè)生成樹中 e是G的割邊假設(shè)

10、e不是割邊，那么G依然連通,所以存在生成數(shù)T,當(dāng)然T也是G的生成樹,但不包含在T中，與題設(shè)矛盾，因此e是G的割邊12、略23、略(參考課堂ppt)講解習(xí)題十二1、證明:圖1中的圖都是平面圖略（只需要畫處其平面圖的形式即可)(a多一條邊，多了一條邊）3、設(shè)是階數(shù)不小于1的圖，證明:G或G（代表G的補(bǔ)圖）中至少有一個(gè)是非平面圖證明：假設(shè)和G都是平面圖，因?yàn)閙（G） +m（)n(n1）/2，因此至少有一圖的邊至少為(n1)/4，根據(jù)平面圖邊與點(diǎn)的關(guān)系，n（n1)/4 3n ，得到n2 3n +24 0，因此 n 0,與題設(shè)矛盾;因此必有一圖為非平面圖5、證明：少于30條邊的簡(jiǎn)單平面圖至少有一個(gè)頂點(diǎn)的

11、度不大于4證明:（反證）假設(shè)少于30條邊的簡(jiǎn)單平面圖所有的頂點(diǎn)的度都大于等于5，那么根據(jù)握手定理和平面圖的性質(zhì)有：5n 2m (1） m n 6 （2） 5n 1 n 12根據(jù)(1)式, 2m,既 m 30與題設(shè)矛盾，因此至少有一個(gè)頂點(diǎn)的度不大于47、證明:對(duì)K3,3的任意一條邊e，3，3是平面圖;同樣，對(duì)K5的任何邊e,5-e也是平面圖證明:因?yàn)椋?的任意一條邊，ej,3，3ei，3，3-j都是同構(gòu)的，而根據(jù)題(a)的結(jié)論，我們可以平面嵌入它，因此3，3-e是平面圖；同理,K5e也是平面圖9、如果一平面圖與其對(duì)偶圖同構(gòu)，則稱這個(gè)平面圖為自對(duì)偶圖,推導(dǎo)自對(duì)偶圖必須滿足的結(jié)點(diǎn)數(shù)n與邊數(shù)m的關(guān)系，

12、并找出一些自對(duì)偶圖解：如果一個(gè)圖是平面圖,那么滿足歐拉公式：n m + f2 （1）其對(duì)偶圖也是平面圖，因此也應(yīng)滿足歐拉公式：n-m* + f* = 2 （2）因?yàn)閷?duì)偶關(guān)系,因此：n = f*f = 又因?yàn)榇硕D同構(gòu)，因此 n n*， = * 所以:n f, 并且 n = 2據(jù)此可以找到一些自對(duì)偶圖： K，G（2，2） 有兩種圖像, K4習(xí)題十三、構(gòu)造(，m）歐拉圖，使其滿足條件:（1)m，n奇偶性相同；(2）m，奇偶性相反答:略、設(shè)G=（V,E）是一個(gè)具有2k（k0)個(gè)奇數(shù)度結(jié)點(diǎn)的連通圖。證明：中必存在k條邊不相重的簡(jiǎn)單道路P1,2,Pk，使得E=(1） E（P2） E（P）證明:把2k個(gè)奇

13、數(shù)度結(jié)點(diǎn)分成兩兩一組的k組，然后每組結(jié)點(diǎn)新加一條邊，所得圖為歐拉圖,故存在歐拉回路C；然后去掉歐拉回路C中的k條新加入的邊，得到條互無重復(fù)邊的道路P，P，Pk， 即為所求5、在圖1310中求中國郵遞員問題的解解：v9v9v6v3v1v2v4v5v7v8v1022111133v1134415562如上圖標(biāo)號(hào)：圖中有4個(gè)奇數(shù)度結(jié)點(diǎn)v1，v6,9，3， 求兩兩之間最短長度:Pv1v6= （vv6）， vv= （v1vv3v4v9), P3=4 (vv2v3）， Pvv9=7 (6vv8v）, P3v= （3vv6）, Pvv93 (v3v4v9）,Pv1v6和3v9滿足最小性要求，復(fù)制1v和349的

14、邊，圖中歐拉回路即為所求解6、設(shè)G是有兩個(gè)奇數(shù)度點(diǎn)的連通圖，設(shè)計(jì)一個(gè)構(gòu)造G的歐拉道路的算法解：此算法只要在書中歐拉回路的算法中，添加起點(diǎn)為奇數(shù)結(jié)點(diǎn)即可,詳細(xì)描述略9、證明：凡有割點(diǎn)的圖都不是哈密頓圖證明：假設(shè)e為圖G的割點(diǎn),根據(jù)割點(diǎn)的定義，（G-e） 1，因此不滿足哈圖的必要條件；所以不是哈圖、假定在n（2）個(gè)人的團(tuán)體中,任何2人合起來認(rèn)識(shí)其余的n2個(gè)人,證明:(1）這n個(gè)人可以排成一排,使得站在中間的每個(gè)人的兩旁都是自己認(rèn)識(shí)的人,站在兩端的人旁邊各有個(gè)認(rèn)識(shí)的人（2）當(dāng)4時(shí)，這n個(gè)人可以圍成一個(gè)圓圈，使得每個(gè)人兩旁都是自己所認(rèn)識(shí)的人證明:如果團(tuán)體中的個(gè)人看成是結(jié)點(diǎn)，而人于人的關(guān)系看成是邊，那么就構(gòu)成一個(gè)認(rèn)識(shí)與否的圖，對(duì)于問題