離散數(shù)學(xué)第九章習(xí)題的答案ppt課件

1、第第9章習(xí)題答案章習(xí)題答案 6. 證明圖證明圖9.26中的無(wú)向圖中的無(wú)向圖G1和和G2不同構(gòu)。不同構(gòu)。證明：因?yàn)樵趫D證明：因?yàn)樵趫DG1中，每個(gè)中，每個(gè)3度頂點(diǎn)都有度頂點(diǎn)都有2個(gè)個(gè)3度頂點(diǎn)度頂點(diǎn)與之鄰接，而圖與之鄰接，而圖G2中，每個(gè)中，每個(gè)3度頂點(diǎn)只有一個(gè)度頂點(diǎn)只有一個(gè)3度頂點(diǎn)度頂點(diǎn)與之鄰接。所以兩圖不同構(gòu)。與之鄰接。所以兩圖不同構(gòu)。 7. 證明在證明在n個(gè)頂點(diǎn)的簡(jiǎn)單無(wú)向圖中個(gè)頂點(diǎn)的簡(jiǎn)單無(wú)向圖中(n2)，至少有兩個(gè)，至少有兩個(gè)頂點(diǎn)次數(shù)相同。頂點(diǎn)次數(shù)相同。證明：反證法，假設(shè)證明：反證法，假設(shè)n個(gè)頂點(diǎn)的次數(shù)互不相同。由于個(gè)頂點(diǎn)的次數(shù)互不相同。由于n個(gè)頂點(diǎn)的簡(jiǎn)單無(wú)向圖中，每個(gè)頂點(diǎn)的次數(shù)均小于個(gè)頂點(diǎn)的

2、簡(jiǎn)單無(wú)向圖中，每個(gè)頂點(diǎn)的次數(shù)均小于n，則則n個(gè)頂點(diǎn)的次數(shù)分別為個(gè)頂點(diǎn)的次數(shù)分別為0，1，2，n-1。次數(shù)為。次數(shù)為0的的頂點(diǎn)為孤立點(diǎn)，因而，圖中次數(shù)為頂點(diǎn)為孤立點(diǎn)，因而，圖中次數(shù)為0和和n-1的頂點(diǎn)不可的頂點(diǎn)不可能同時(shí)存在，故假設(shè)錯(cuò)誤。所以在能同時(shí)存在，故假設(shè)錯(cuò)誤。所以在n個(gè)頂點(diǎn)的簡(jiǎn)單無(wú)個(gè)頂點(diǎn)的簡(jiǎn)單無(wú)向圖中向圖中(n2)，至少有兩個(gè)頂點(diǎn)次數(shù)相同。，至少有兩個(gè)頂點(diǎn)次數(shù)相同。 12. 證明在有向圖證明在有向圖D中，任何一個(gè)回路總包含有一個(gè)中，任何一個(gè)回路總包含有一個(gè)基本回路?；净芈?。證明：設(shè)是有向圖證明：設(shè)是有向圖D中的任意一條回路。除外，若回中的任意一條回路。除外，若回路中無(wú)重復(fù)出現(xiàn)的頂點(diǎn)，則

3、它是一條基本回路，否則路中無(wú)重復(fù)出現(xiàn)的頂點(diǎn)，則它是一條基本回路，否則存在，使得。我們把從回路中刪去，所得結(jié)果仍為一存在，使得。我們把從回路中刪去，所得結(jié)果仍為一條回路。若這條新回路除外仍有重復(fù)出現(xiàn)的頂點(diǎn)，就條回路。若這條新回路除外仍有重復(fù)出現(xiàn)的頂點(diǎn)，就重復(fù)前邊的操作，直到無(wú)重復(fù)出現(xiàn)的頂點(diǎn)為止。最后重復(fù)前邊的操作，直到無(wú)重復(fù)出現(xiàn)的頂點(diǎn)為止。最后得到的回路就是一條基本回路。這表明，任何一條回得到的回路就是一條基本回路。這表明，任何一條回路中必包含有一條基本回路。路中必包含有一條基本回路。 17. 證明在一個(gè)連通無(wú)向圖中。任何兩條最長(zhǎng)的基本證明在一個(gè)連通無(wú)向圖中。任何兩條最長(zhǎng)的基本鏈必有公共頂點(diǎn)。鏈

4、必有公共頂點(diǎn)。證明：假設(shè)圖中兩條最長(zhǎng)的基本鏈分別為證明：假設(shè)圖中兩條最長(zhǎng)的基本鏈分別為P1=（a0，a1，a2，an，），），P2=（b0，b1，b2，bm，），），mn，P1與與P2沒(méi)有公共頂點(diǎn)。由于此圖沒(méi)有公共頂點(diǎn)。由于此圖是連通圖，則是連通圖，則P1中必有一頂點(diǎn)中必有一頂點(diǎn)ai，P2中必有一頂點(diǎn)中必有一頂點(diǎn)bj，ai和和bj連通，令連通，令ai到到bj的鏈為的鏈為P3=（ai，c1，c2，ck，bj），那么），那么P31，ai和和bj分別將鏈分別將鏈P1，P2分成分成兩部分，則兩部分，則P1的較長(zhǎng)部分與的較長(zhǎng)部分與P3和和P2的較長(zhǎng)部分構(gòu)成的較長(zhǎng)部分構(gòu)成的鏈長(zhǎng)度大于的鏈長(zhǎng)度大于m，這與，

5、這與P2是兩條最長(zhǎng)基本鏈中之一矛是兩條最長(zhǎng)基本鏈中之一矛盾。因而，任何兩條最長(zhǎng)的基本鏈必有公共頂點(diǎn)。盾。因而，任何兩條最長(zhǎng)的基本鏈必有公共頂點(diǎn)。18. 證明在一個(gè)無(wú)向圖證明在一個(gè)無(wú)向圖G中，如果有兩個(gè)且僅有兩個(gè)中，如果有兩個(gè)且僅有兩個(gè)奇頂點(diǎn)，則這兩個(gè)頂點(diǎn)是連通的。奇頂點(diǎn)，則這兩個(gè)頂點(diǎn)是連通的。證明：假設(shè)無(wú)向圖證明：假設(shè)無(wú)向圖G中恰有兩個(gè)奇度頂點(diǎn)中恰有兩個(gè)奇度頂點(diǎn)u和和v，若，若u和和v不連通，則不連通，則u和和v分別在分別在G 的兩個(gè)不同的連通分支的兩個(gè)不同的連通分支中，不妨把這兩個(gè)連通分支分別記為中，不妨把這兩個(gè)連通分支分別記為G1和和G2，于是，于是G1和和G2中各含一個(gè)奇數(shù)頂點(diǎn)。這與推論

6、：中各含一個(gè)奇數(shù)頂點(diǎn)。這與推論：“在任何在任何圖中，度數(shù)為奇數(shù)的頂點(diǎn)個(gè)數(shù)必定是偶數(shù)相矛盾。圖中，度數(shù)為奇數(shù)的頂點(diǎn)個(gè)數(shù)必定是偶數(shù)相矛盾。故故u和和v兩頂點(diǎn)必連通。兩頂點(diǎn)必連通。 19. 設(shè)設(shè)G是具有是具有n個(gè)頂點(diǎn)的簡(jiǎn)單無(wú)向圖，并且個(gè)頂點(diǎn)的簡(jiǎn)單無(wú)向圖，并且G中任中任何兩個(gè)頂點(diǎn)的次數(shù)之和大于或等于何兩個(gè)頂點(diǎn)的次數(shù)之和大于或等于n-1，證明，證明G為連為連通圖。通圖。證明證明: 假設(shè)假設(shè)G不是連通圖，有不是連通圖，有kk1個(gè)連通分支，個(gè)連通分支，令它們的頂點(diǎn)數(shù)分別為令它們的頂點(diǎn)數(shù)分別為n1，n2，nk，則第，則第i個(gè)個(gè)連通分支連通分支ni的每個(gè)頂點(diǎn)的次數(shù)至多為的每個(gè)頂點(diǎn)的次數(shù)至多為ni-1。設(shè)。設(shè)u，

7、v分別為任意兩個(gè)不同連通分支分別為任意兩個(gè)不同連通分支i和和j的頂點(diǎn)，則它們的頂點(diǎn)，則它們的 頂 點(diǎn) 次 數(shù) 之 和 至 多 為的 頂 點(diǎn) 次 數(shù) 之 和 至 多 為 n i + n j - 2 ， 因 為， 因 為n1+n2+nk=n，所以，所以ni+nj-2 n-1，這與，這與G中任中任何兩個(gè)頂點(diǎn)的次數(shù)之和大于或等于何兩個(gè)頂點(diǎn)的次數(shù)之和大于或等于n-1矛盾，故矛盾，故G必必為連通圖。為連通圖。 20. 設(shè)給定無(wú)向圖設(shè)給定無(wú)向圖G=，按如下方式構(gòu)造無(wú)向，按如下方式構(gòu)造無(wú)向圖圖G=，使得，使得V=V，E=(u,v)*uVvV(u,v)E，證明，證明: 如果如果G是不連通的，是不連通的，則則G是

8、連通的。是連通的。證明：因?yàn)樽C明：因?yàn)镚是不連通圖，不妨設(shè)是不連通圖，不妨設(shè)G有有k個(gè)連通分個(gè)連通分支，則支，則k2。由已知條件，在。由已知條件，在G圖中，圖中，G的不同連的不同連通分支中的兩個(gè)頂點(diǎn)之間有邊相連。若通分支中的兩個(gè)頂點(diǎn)之間有邊相連。若u和和v是是G的的同一連通分支中的兩個(gè)不同頂點(diǎn)，則在同一連通分支中的兩個(gè)不同頂點(diǎn)，則在G中，中，u和和v與與G的另一連通分支中的頂點(diǎn)的另一連通分支中的頂點(diǎn)w鄰接，故鄰接，故u和和v連連通。所以，通。所以，G是連通圖。是連通圖。 23. 設(shè)有設(shè)有2n個(gè)電話局，如果每一個(gè)電話局至少可以與另個(gè)電話局，如果每一個(gè)電話局至少可以與另外外n個(gè)電話局通話，證明在這

9、個(gè)電話局通話，證明在這2n個(gè)電話局的任何兩個(gè)電個(gè)電話局的任何兩個(gè)電話局之間都可以通話話局之間都可以通話(也可能要通過(guò)另外的電話局也可能要通過(guò)另外的電話局)證明：設(shè)電話局為頂點(diǎn)，在能通話的電話局之間連一條證明：設(shè)電話局為頂點(diǎn)，在能通話的電話局之間連一條邊，則得無(wú)向簡(jiǎn)單圖邊，則得無(wú)向簡(jiǎn)單圖G。由題意可知，。由題意可知，G有有2n個(gè)頂點(diǎn)，個(gè)頂點(diǎn)，G的每個(gè)頂點(diǎn)的度數(shù)大于等于的每個(gè)頂點(diǎn)的度數(shù)大于等于n，下面證明，下面證明G為連通圖。為連通圖。假設(shè)假設(shè)G不是連通圖，則不是連通圖，則G至少有兩個(gè)連通分支。由于至少有兩個(gè)連通分支。由于G有有2n個(gè)頂點(diǎn)，故必存在一個(gè)最多有個(gè)頂點(diǎn)，故必存在一個(gè)最多有n個(gè)頂點(diǎn)的連通分支，個(gè)頂點(diǎn)的連通分支，令其為令其為G1。由于。由于G是無(wú)向簡(jiǎn)單圖，因此其連通子圖是無(wú)向簡(jiǎn)單圖，因此其連通子圖G1中中的每個(gè)頂點(diǎn)的度數(shù)的每個(gè)頂點(diǎn)的度數(shù) n-1，這與，