《離散數(shù)學(xué)》劉任任版第七章.doc
《《離散數(shù)學(xué)》劉任任版第七章.doc》由會(huì)員分享，可在線閱讀，更多相關(guān)《《離散數(shù)學(xué)》劉任任版第七章.doc（7頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。
習(xí)題七 1．對圖7.7中的兩個(gè)圖，各作出兩個(gè)頂點(diǎn)割。 （a） （b） 圖7.7 解： 對圖7.7增加加節(jié)點(diǎn)標(biāo)記如下圖所示， 則(a)的兩個(gè)頂點(diǎn)割為： V11={a,b} ； V12={c,d} (b)的兩個(gè)頂點(diǎn)割為： V21={u,v} ； V12={y} 2．求圖7.7中兩個(gè)圖的和. 解：如上兩個(gè)圖，有 k(G1)=λ(G1)=2, k(G2)=1, λ(G2)=2 3．試作出一個(gè)連通圖, 使之滿足： 解：做連通圖G如下，于是有 ： 4．求證, 若是邊連通的, 則. 證明：設(shè)G是k—邊連通的，由定義有λ(G)≧k. 又由定理7.1.2知λ(G)≦ ，因此有 k≦λ(G) ≦ ≦ 即 k≦ ，從而 5．求證, 若是階簡單圖, 且, 則. 分析：由G是簡單圖，且，可知G中的δ(G)只能等于 p-1或p-2； 如δ(G)= p-1,則G是一個(gè)完全圖，根據(jù)書中規(guī)定，有k(G)=p-1=δ(G)； 如δ(G)= p-2,則從G中任取V（G）的子集V1，其中|V1|=3，則V(G)-V1的點(diǎn)導(dǎo)出子圖是連通的，否則在V1中存在一個(gè)頂點(diǎn)v，與其他兩個(gè)頂點(diǎn)都不連通。則在G中，頂點(diǎn)v最多與G中其他p-3個(gè)頂點(diǎn)鄰接，所以d(v)≤p-3，與δ(G)= p-2矛盾。這說明了在G中，去掉任意p-3個(gè)頂點(diǎn)后G還是連通的，按照點(diǎn)連通度的定義有k(G)>k-3，又根據(jù)定義7.1.1，，有k(G)=k-2。 證明：因?yàn)镚是簡單圖 ,所以d(v)≦p-1,v∈V(G),已知δ(G)≧p-2 （?。┤籀?G)= p-1,則G=Kp（完全圖），故k(G)=p-1=δ(G)。 （ⅱ）若δ(G)= p-2, 則 G≠Kp,設(shè)u,v不鄰接，但對任意的w∈V(G),有 uw,vw ∈E(G).于是，對任意的V1V(G), | V1|=p-3 ,G-V1必連通. 因此必有k(G) ≧p-2=δ(G),但k(G) ≦δ(G)。 故k(G) =δ(G)。 6．找出一個(gè)階簡單圖, 使, 但. 解： 7．設(shè)為正則簡單圖, 求證. 分析：G是一個(gè)正則簡單圖，所以δ(G)=3，根據(jù)定理7.1.1有，所以只能等于0，1，2，3這四種情況。下面的證明中分別討論了這四種情況下的關(guān)系。 證明：(1)若=0，則G不連通,所以λ(G)=K(G). (2) 設(shè) K(G)=1,且u 是G中的一個(gè)割點(diǎn)，G-u不連通,由于d(u)=3,從而至少存在一個(gè)分支僅一邊與u相連,顯然這邊是G的割邊,故λ(G)＝１，所以λ(G)=K(G) (３) 設(shè)K(G)=2,且{v1,v2}為G的一個(gè)頂點(diǎn)割。G1=G-v1連通,則v2是G1的割點(diǎn)且v2在G1中的度小于等于３，類似于(2)知在G1中存在一割邊e2(關(guān)聯(lián)v2)使得G1-e2不連通．另一方面由于λ(G)>=K(G)=2故G-e2連通．由于G1-e2= (G-e2)-v1，故v1是G-e2的割點(diǎn)，且v1在G-e2中的度小于等于３，于是類似于(2)知，在G-e2中存在一割邊e1，即(G-e2)-e1=G-{e1,e2}不連通，故λ(G)=2.所以λ(G)=K(G). (４) 設(shè)k(G) =3,于是， 有3 =k（G） ≦ ≦δ(G)=3 ,知 8．證明：一個(gè)圖是邊連通的當(dāng)且僅當(dāng)?shù)娜我鈨蓚€(gè)頂點(diǎn)由至少兩條邊不重的通路所連通. 分析：這個(gè)題的證明關(guān)鍵是理解邊連通的定義。 證明：（必要性）因?yàn)镚是邊連通的，所以G沒有割邊。設(shè)u，v是G中任意兩個(gè)頂點(diǎn)，由G的連通性知u，v之間存在一條路徑P1，若還存在從u到v的與P1邊不重的路徑P2，設(shè)C=P1∪P2，則C中含u,v的回路，若從u到v的任意另外路徑和P1都有一條（或幾條）公共邊，也就是存在邊e在從u到v的任何路徑中，則從G中刪除e，G就不連通了，于是e成了G中一割邊，矛盾。 （充分性）假設(shè)G不是一個(gè)2-邊連通的，則G中有割邊，設(shè)e=(u,v)為G中一割邊，由已知條件可知，u與v處于同一簡單回路C中，于是e處在C中，因而從G中刪除e后G仍然連通，這與G中無割邊矛盾。 v V1 V2 u G 9．舉例說明：若在連通圖中, 是一條通路, 則不一定包含一條與內(nèi)部不相交的通路。 解 如右圖G，易知G是2—連通的， 若取P為uv1v2v， 則G中不存在Q了。 10．證明：若中無長度為偶數(shù)的回路, 則的每個(gè)塊或者是, 或者是長度為奇數(shù)的回路. 分析：塊是G的一個(gè)連通的極大不可分子圖，按照不可分圖的定義，有G的每個(gè)塊應(yīng)該是沒有割點(diǎn)的。因此，如果能證明G的某個(gè)塊如果既不是，也不是長度為奇數(shù)的回路，再由已知條件G中無長度為偶數(shù)的回路，則可得出G的這個(gè)塊肯定存在割點(diǎn)，則可導(dǎo)出矛盾。本題使用反證法。 證明： 設(shè)K是G的一個(gè)塊，若k既不是 K2也不是奇回路，則k至少有三個(gè)頂點(diǎn)，且存在割邊e=uv,于是u,v中必有一個(gè)是割點(diǎn)，此與k是塊相矛盾。 11．證明：不是塊的連通圖至少有兩個(gè)塊, 其中每個(gè)塊恰含一個(gè)割點(diǎn). 分析：一個(gè)圖不是塊，按照塊的定義，這個(gè)圖肯定含有割點(diǎn)v，對圖分塊的時(shí)候也應(yīng)該以割點(diǎn)為標(biāo)準(zhǔn)進(jìn)行，而且分得的塊中必定含這個(gè)割點(diǎn)，否則所得到的子圖一定不是極大不可分子圖，從而不會(huì)是一個(gè)塊。 證明：由塊的定義知，若圖G不是塊且連通，則G有割點(diǎn)，依次在有割點(diǎn)的地方將G分解成塊，一個(gè)割點(diǎn)可分成兩塊，每個(gè)塊中含G中的一個(gè)割點(diǎn)。如下圖G。 易知 u,v是割點(diǎn)，G可分成四個(gè)塊K1 ～K4 。其中每個(gè)塊恰含一個(gè)割點(diǎn)。 12．證明：圖中塊的數(shù)目等于 其中, 表示包含的塊的數(shù)目. 分析：一個(gè)圖G的非割點(diǎn)只能分布在G的一個(gè)塊中，即=1（當(dāng)v是G的非割點(diǎn)時(shí)），且每個(gè)塊至少包含一個(gè)割點(diǎn)。因此下面就從G的割點(diǎn)入手進(jìn)行證明。證明中使用了歸納法。 證明：先考慮G是連通的情況（），對G中的割點(diǎn)數(shù)n用歸納法。 由于對G的非割點(diǎn)v，b(v)=1，即b(v)-1 =0，故對n=0時(shí)，G的塊數(shù)為1結(jié)論成立。 假設(shè)G中的割點(diǎn)數(shù)n≤k（k≥0）時(shí)，結(jié)論成立。 對n=k+1的情況，任取G的一個(gè)割點(diǎn)a，可將G分解為連通子圖Gi，使得a在Gi中不是割點(diǎn)，a又是Gi的公共點(diǎn)。這樣，每一個(gè)Gi，有且僅有一個(gè)塊含有a，若這些Gi共有r個(gè)，則b(a)=r，又顯然Gi的塊也是G的塊，且Gi的割點(diǎn)數(shù)≤k。故由歸納法假設(shè)Gi的塊的塊數(shù)為1，這里是Gi中含v的塊的塊數(shù)，注意到Gi中異于a的v，b(v)= ，而a在每一個(gè)Gi中均為非割點(diǎn)，故。于是Gi的塊數(shù)為1 將所有Gi的塊全部加起來，則得到G的塊數(shù)為： r=r=1+(r-1) =1 由歸納法可知，當(dāng)G連通時(shí)，結(jié)論成立。 當(dāng)G不連通時(shí)，對每個(gè)連通分支上述結(jié)論顯然成立。 因此有圖中塊的數(shù)目等于 13． 給出一個(gè)求圖的塊的好算法。 分析：設(shè)G是一個(gè)具有p個(gè)頂點(diǎn)，q條邊，w個(gè)連通分支的圖。求圖G的塊可先求圖G的任一生成森林F，且對每一邊eF，求F+e中的唯一回路，設(shè)這些回路C1，C2，…，Cq-p+w都已求得，（這些都有好算法）。在此基礎(chǔ)上，我們注意到，兩個(gè)回路（或一個(gè)回路與一個(gè)塊）若有多于1個(gè)公共點(diǎn)，則它們屬于同一塊。此外，由割邊的定義知，G的任一割邊不含于任何回路中，且它們都是G的塊。基于這些道理，可得如下求圖G的塊的好算法。 解： 求圖的塊的算法： （1）令s=1，t=1，n=q-p+w （2）若n>0，輸入C1，C2，…，Cn；否則，轉(zhuǎn)第4步。 （3）若且對i=s+t，…，n-1，令，轉(zhuǎn)第4步；否則，t=t+1，轉(zhuǎn)第5步。 （4）若s下載提示(請認(rèn)真閱讀)
- 1.請仔細(xì)閱讀文檔，確保文檔完整性，對于不預(yù)覽、不比對內(nèi)容而直接下載帶來的問題本站不予受理。
- 2.下載的文檔，不會(huì)出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入（下載+內(nèi)容+預(yù)覽）歸上傳者、原創(chuàng)作者；如果您是本文檔原作者，請點(diǎn)此認(rèn)領(lǐng)！既往收益都?xì)w您。
文檔包含非法信息？點(diǎn)此舉報(bào)后獲取現(xiàn)金獎(jiǎng)勵(lì)！
下載文檔到電腦，查找使用更方便
9.9 積分
| 下載 |
還剩頁未讀，繼續(xù)閱讀
- 配套講稿：
如PPT文件的首頁顯示word圖標(biāo)，表示該P(yáng)PT已包含配套word講稿。雙擊word圖標(biāo)可打開word文檔。
- 特殊限制：
部分文檔作品中含有的國旗、國徽等圖片，僅作為作品整體效果示例展示，禁止商用。設(shè)計(jì)者僅對作品中獨(dú)創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞：
- 離散數(shù)學(xué) 劉任任版 第七
裝配圖網(wǎng)所有資源均是用戶自行上傳分享，僅供網(wǎng)友學(xué)習(xí)交流，未經(jīng)上傳用戶書面授權(quán)，請勿作他用。
相關(guān)資源
更多
正為您匹配相似的精品文檔
相關(guān)搜索
鏈接地址：http://kudomayuko.com/p-6724972.html