離散數(shù)學(xué)劉任任課后答案習(xí)題.ppt

離散數(shù)學(xué)習(xí)題集,第五章 圖與子圖,2、設(shè)G（p,q）是簡(jiǎn)單二分圖求證： 。,3、設(shè)G（p,q）是簡(jiǎn)單圖,求證:qp(p-1)/2，在什么情況下, q=p(p-1)/2?,證明：因 是簡(jiǎn)單圖。所以G中任意兩顆點(diǎn)之間最多只有一條邊。故 。 當(dāng)G為完全圖時(shí)，有q=p(p-1)/2 。,4、試畫出四個(gè)頂點(diǎn)的所有非同構(gòu)的簡(jiǎn)單圖.,共有11個(gè)。即,5、證明圖5.14中的兩個(gè)圖是同構(gòu)的, 圖5.15中的兩個(gè)圖不是同構(gòu)的.試問,圖5.16中的兩個(gè)圖是否同構(gòu)?,a,g,f,h,e,b,d,c,j,i,1. 令 ，,（2）如下圖，若(a)與(b)同構(gòu)，則對(duì)任何雙射， 必有 。于是推得 但d(b) d(v)，故(a)與(b)不同構(gòu)。,b,e,d,a,c,w,x,v,y,u,(3)下面兩個(gè)圖是同構(gòu)。令 ,f,g,a,b,c,d,e,6、設(shè)G（p,q）是簡(jiǎn)單二分圖，且 ,求證 .,G , 且 于是|E(G)|=p(p-1)/4。 顯然|E(G)|是整數(shù)。于是P或P-1是4的倍數(shù)。 因此， 或 。,或,7、構(gòu)造一個(gè)簡(jiǎn)單圖G,使得 .,如下圖，令 ， 則有 .,8、求證:對(duì)任何圖G（p,q）,有:, 而 因此 即,9 、設(shè)G（p,q）是簡(jiǎn)單圖,p2.求證:G中至少有兩個(gè)頂點(diǎn)的度數(shù)相等.,證明：假設(shè)G（p,q)中任何頂點(diǎn)的度均不相等, 則p個(gè)頂點(diǎn)的度分別為0,1,2,p-1。 （1）設(shè) ，則 中存在孤立點(diǎn) ； （2）設(shè) ，則 中無頂點(diǎn)v 滿 足 ，此與（1）矛盾。 總之，0和p-1不能同時(shí)出現(xiàn)。由抽屜原理知，必有， 使 。,10、求證:在圖G（p,p+1）中,至少有一個(gè)頂點(diǎn)v,滿足d(v) 3.,證明：若對(duì)任意 ，均有 ，則有 即 ， 也即 。 從而 ，矛盾。故存在 ， 使 。,11、求證:在任何有n(n2)個(gè)人的人群中,至少有兩個(gè)人在其中恰有相同個(gè)數(shù)的朋友.,證明：作一個(gè)n階簡(jiǎn)單圖，n個(gè)頂點(diǎn)分別表示n個(gè)人。兩個(gè)人是朋友當(dāng)且僅當(dāng)表示這兩個(gè)人的頂點(diǎn)鄰接。這樣，問題就轉(zhuǎn)化成中至少有兩個(gè)頂點(diǎn)的度數(shù)相等。此結(jié)論題9已證。,12、求證:每一個(gè)p階簡(jiǎn)單圖G,都與Kp的子圖同構(gòu).,證明：因任何一個(gè)P階簡(jiǎn)單圖GKp。又 。 故結(jié)論成立。,13、求證:任何完全圖的每個(gè)點(diǎn)導(dǎo)出子圖仍是完全圖.,證明：由點(diǎn)導(dǎo)出子圖的定義及完全圖的結(jié)構(gòu)即知結(jié)論成立。,14、求證:二分圖的每個(gè)頂點(diǎn)數(shù)不小于2的子圖仍是二分圖.,證明：設(shè) ，且 。 令 ， 顯然 ， 且 。 因此 。,15、設(shè)G（p,q）是簡(jiǎn)單圖，整數(shù)n滿足1< n <p 1,求證:若p 4,且G的所有n 個(gè)頂點(diǎn)的導(dǎo)出子圖均有相同的邊數(shù),則 或 .,證明：若 和 均不成立， 則存在 使得u與v鄰接，而w與x不鄰接。 于是取 n=2 ，則 與 邊數(shù)不相同，矛盾。 故 或 。,16.(1)設(shè)G（p,q）是連通圖，求證:G至少有p 1條邊;,證明：對(duì)p用歸納法 a) p=1時(shí)，顯然成立。 b) 假設(shè)對(duì)于小于p的自然數(shù)，結(jié)論成立。 c）在p階連通圖中任取一個(gè)頂點(diǎn)v。設(shè)G-v共有k個(gè)分支，且每個(gè)分支有Pi個(gè)頂點(diǎn)， Pi<P, 。 于是由歸納假設(shè)可知GVi至少有Pi-1條邊， ， 從而G-v至少有(P-1)-k條邊。故G至少有P-1條邊。,16.(2)設(shè)G（p,q）是連通圖，求證:若q p 1,則G 中必含回路;,證明：設(shè) 。 若G不含回路，則必有 滿足 。于是 仍連通且無回路，而 恰有 條邊。如此下去， 連通無回路且 恰含 條邊，一個(gè)頂點(diǎn) ，此時(shí) 是一個(gè)平凡圖。從而 即 。此與 矛盾。故G必含回路。,16.(3)設(shè)G（p,q）是連通圖，求證:若q = p 1,則G至少有兩個(gè)懸掛點(diǎn).,證明：設(shè) ，若對(duì)任何 ，均有 ， 則 ， 即 。 此與 矛盾。 故G中至少有一個(gè)懸掛點(diǎn).。又若G中最多只有一個(gè)懸掛點(diǎn)，則 即 。 從而得出 （矛盾）。故G中至少有兩個(gè)懸掛點(diǎn)。,17、求證:若邊e 在圖G的一條閉鏈中,則e 必在G 的一條回路中.,證明：設(shè) ，G中含e的閉鏈為 。 若E不是回路，則必有 。 （因?yàn)榛芈范x是 ：沒有重復(fù)點(diǎn)） 從E中去掉 ，得到 仍為閉鏈。如此下去，就可得到含 的回路。,18、求證:對(duì)于圖G(p,q),若 ,則G中必含回路.,證明： G中無懸掛點(diǎn)。任取 ，設(shè)v1與v0鄰接。如此下去，可得G中的一條鏈 又因G是有限圖,由此可得一條閉鏈，由第題的證明過程可知，故此鏈上必有回路。,19、設(shè)G（p,q）是簡(jiǎn)單圖，且 ,求證:G是連通圖.,證明：若G不連通，則可將V(G)劃分成V1,V2，使得V1中的頂點(diǎn)與V2中的頂點(diǎn)不鄰接。令 ， ，于是， ，且 ( ),即 矛盾！故連通。,另解：,考慮 。則有 （因?yàn)閜(p-1)/2是完全圖的邊數(shù)）即 不連通，于是，G 連通。,20、對(duì)于 p 1,作一個(gè) 的非連通圖 .,證明：令 。作如下 ，故G不連通。,21、（1）證明：若 (p,q) 是簡(jiǎn)單圖，且 ,則G 連通.,證明：（1）設(shè) 。 若G不連通，則G的頂點(diǎn)可劃分成兩個(gè)集合 ，使得V1與V2中的頂點(diǎn)互不鄰接。 不妨設(shè) ，則 。 由G是簡(jiǎn)單圖知， ( 因?yàn)?) 從而 矛盾。故G必連通。,21、（2）當(dāng)p 為偶數(shù)時(shí),作一個(gè)非連通的k 正則簡(jiǎn)單圖,其中,取p=6。則 。 作非連通圖G如下：,22、證明:若eE(G),則,證明：因G的任意一條邊e最多聯(lián)結(jié)G-e的兩個(gè)分支。 故,23、證明:對(duì)圖G中任意三個(gè)頂點(diǎn)u,v和w, d(u,v)+d(v,w)=d(u,w) 。,證明：若 d(u,v)+d(v,w)<d(u,w)， 則與距離的概念不符。（因?yàn)榫嚯x的定義是：連接兩點(diǎn)之間的最短路徑的長(zhǎng)度） 故結(jié)論成立。,24、設(shè)G是簡(jiǎn)單連通的非完全圖,求證:G中存在三個(gè)頂點(diǎn)u,v和w,使uv,vwE(G),但uw E(G)。,證明：反證法。 若不然，即對(duì)任意的 ， 只要 ， 就有 ，也即 且 . （1） 今任取 。由G連通知，存在 -通路：,于是由（1）可知： 且 且 且 從而推得簡(jiǎn)單圖G中任何兩個(gè)頂點(diǎn)均鄰接，即G是一個(gè)完全圖。此與題設(shè)矛盾。,25、證明:若G是簡(jiǎn)單圖,且 ,則G中有一條長(zhǎng)度至少是 的回路.,證明：不妨設(shè) 連通（否則可對(duì)其分支進(jìn)行討論）。于是 ，即G中至少有 個(gè)頂點(diǎn)。 設(shè) 是G中的一條極長(zhǎng)通路，則v1不與P以外的任何頂點(diǎn)鄰接。（如果存在就與P是極長(zhǎng)通路矛盾） 又因 。所以存在P上的 個(gè)頂點(diǎn) 均與v1鄰接。 于是有回路 ，顯然 。,26、求圖5.17的關(guān)聯(lián)矩陣和鄰接矩陣.,鄰接矩陣為：,27、設(shè)G是簡(jiǎn)單圖,M(G)和A(G)分別是G的關(guān)聯(lián)矩陣和鄰接矩陣.(1)求證: M(G)中每列各元素之和為2.（2）A(G)的各列元素之和是什么?,（1）證明：因每條邊 恰與兩個(gè)端點(diǎn)u,v關(guān)聯(lián)； （2）若 上無環(huán)，則 所在列（行）各元素之和為 ，否則 所在列（行）各元素之和為 。,28、設(shè)G是二分圖,求證:可以將G的頂點(diǎn)作適當(dāng)排列,使得G的鄰接矩陣M(G)形如其中:A21是A12的轉(zhuǎn)置.,證明：因?yàn)镚是二分圖，所以G中無環(huán)，設(shè) 。 令 則 其中 ; 且 。,29、設(shè)G是一個(gè)圖(1)如何從 得到 和 ?(2)如何從 得到 ?,解：（1）對(duì)每個(gè) ,將 中 所在列的元素全置為0，則得 ； （2）對(duì)每個(gè) ，將 中 所在行的元素全置為0，則得到 ； （3）對(duì)每個(gè) ，將 中 所在行與列的元素全置為0，則得到 ；,30、在圖5.18中,找出從U1到各個(gè)頂點(diǎn)的最短通路長(zhǎng)度,并給出從U1到U11的最短通路.,迭代 W D2 D3 D4 D5 D6 D7 D8 D9 D10 D11 初始 1 2 8 1 1 1,4 4 2 8 10 2 1,4,2 2 8 3 10 3 1,4,2,5 5 8 6 10 5 12 4 1,4,2,5,8 8 8 6 10 12 14 5 1,4,2,5,8,6 6 7 10 12 14 6 1,4,2,5,8,6,3 3 9 12 14 7 1,4,2,5,8,6,3,77 12 10 14 8 10 10 11 14 9 9 9 13,最后得D2=2，D3=7，D4=1，D5=3，D6=6，D7=9, D8=5，D9=11，D10=10，D11=13。 其中U1到U11的最短通路為： I 2 3 4 5 6 7 8 9 10 11 Pi 1 6 1 2 5 3 5 10 7 9,31、求圖5.19所示的圖G中任意兩個(gè)頂點(diǎn)的最短通路長(zhǎng)度,并給出從V1到V3的最短通路.,其中V1到V3的最短通路為： 。,