離散數(shù)學(劉任任版)第5章答案.ppt

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