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

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

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

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

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

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

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

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

8、是如果有結點度為0，那么就不存在有結點度數(shù)為1;同理，有結點度數(shù)為n1,那就不存在孤立結點，所以可能的點度只能有n1種，但有n個結點,所以必有兩個結點度數(shù)要相同30、略習題十一1、設一個樹中度為k的結點數(shù)是k（2）,求它的葉的數(shù)目解：設中葉結點數(shù)目為t,那么根據(jù)握手定理，及數(shù)的點邊關系可以得到：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中最長簡單道路的起點和終點必都是T的葉證明： 首先證明在中的任意最長道路中，其起

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

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

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

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

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

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