【正文】 12. ，并求其前綴編碼。10. 由有向圖G的鄰接矩陣如何確定G是不是有向樹(shù)。9. 證明n階二叉樹(shù)有個(gè)葉，其高度h滿(mǎn)足log2(n+1)1163。7. 設(shè)計(jì)一個(gè)“破圈法”求最小生成樹(shù)的算法。5. 證明或以反例反駁以下命題：任意連通無(wú)向圖的任何一條邊都是它的某個(gè)生成樹(shù)的枝，并且也是另一個(gè)生成樹(shù)的弦。證明dT(n)=dT (n′)=1。2. 如何由無(wú)向圖G的鄰接矩陣確定G是不是樹(shù)。1. ，由鄰接矩陣求出路徑矩陣和距離矩陣，并確定圖的直徑。6. 設(shè)G是非平凡的連通無(wú)向圖，證明G是歐拉圖當(dāng)且僅當(dāng)G是若干個(gè)邊不相交的回路之并。試證明G是哈密頓圖。 3，對(duì)于n階簡(jiǎn)單無(wú)向圖G的任意兩個(gè)不同節(jié)點(diǎn)n和n′，只要它們不鄰接就有dG(n) + dG (n′) 179。3. 設(shè)n是大于2的奇數(shù)，證明n階完全無(wú)向圖有(n1)/2個(gè)邊不相交的哈密頓回路。G2仍是歐拉有向圖。習(xí)題 1. ，歐拉有向圖，哈密頓圖，哈密頓有向圖，找出其中的一條歐拉閉路，所有的哈密頓回路和哈密頓有向回路（如果存在的話(huà)）。14. 證明：對(duì)于小于或等于n的任意正整數(shù)k，n階連通無(wú)向圖有k階連通子圖。12. 證明非連通簡(jiǎn)單無(wú)向圖的補(bǔ)圖必定連通。試證明之。10. 設(shè)G是弱連通有向圖。9. 設(shè)圖G=V,E,y，其中V={1, 2, 3, 4, 5, 6, 7, 8}，E={a, b, c, d, e, f, g, h, i, j, k, l, m, n, p}，y={a,1,6,b,1,8,c,1,7,d,7,6,e,8,7,f ,6,4,g,7,5,h,8,3,i,5,8, j,4,5,k,5,3, l ,4,3, m ,4,2, n,5,2, p ,3,2}。6. 有向圖的每個(gè)節(jié)點(diǎn)（每條邊）是否恰處于一個(gè)強(qiáng)分支中？是否恰處于一個(gè)單向分支中？7. 證明無(wú)向圖是連通的當(dāng)且僅當(dāng)G的直徑是自然數(shù)。 d (n1, n3)。b) d (n1, n2) = d (n2, n1)。a) d(n1, n2) 179。b) 找出所有強(qiáng)分支，單向分支，弱分支。2. 證明圖中的基本路徑必為簡(jiǎn)單路徑。e) 求出該圖的直徑。c) 找出從A至F所有基本路徑。習(xí)題 1. .a) 從A至F的路徑有多少條？找出所有長(zhǎng)度小于6的從A至F的路徑。證明每個(gè)自補(bǔ)圖的階能被4整除或被4除余數(shù)為1。證明G或者必有一個(gè)子圖是3階完全無(wú)向圖。3. 、并和環(huán)和。2. 設(shè)G=V, E, y是完全有向圖。11. 設(shè)n階無(wú)向圖G有m條邊，其中nk個(gè)結(jié)點(diǎn)的度為k，其余結(jié)點(diǎn)的度為k+1，證明nk=(k+1)n2m。9. ？說(shuō)明理由。7. 證明：在任意六個(gè)人中，若沒(méi)有三個(gè)人彼此都認(rèn)識(shí)，則必有三個(gè)人彼此都不認(rèn)識(shí)。試證明與奇數(shù)個(gè)人握手的人數(shù)是偶數(shù)。4. 證明3度正則圖必有偶數(shù)個(gè)結(jié)點(diǎn)。a) V={n1, n2, n3, n4, n5} E={e1,e2,e3,e4,e5,e6,e7}y={ e1, {n2}}, e2,{n2, n4}, e3,{n1, n2}, e4, {n1, n3}, e5, {n1, n3}, e6, {n3, n4}, e7, {n4, n5}}b) V={n1, n2, n3, n4, n5}E={ e1,e2,e3,e4,e5,e6,e7,e8,e9,e10}y={ e1, {n1, n3}}, e2,{n1, n4}, e3,{n4, n1}, e4, {n1, n2}, e5, {n2, n2}, e6,{ n3, n4}, e7, { n5, n4}, e8,{n5, n3}, e9,{n5, n3}, e10,{n5, n3}}c) V={n1, n2, n3, n4, n5, n6, n7, n8}E={ e1,e2,e3,e4,e5,e6,e7,e8,e9,e10,e11}y={ e1, {n2, n1}}, e2,{n1, n2}, e3,{n1, n3}, e4, {n2, n4}, e5, {n3, n4}, e6,{n4, n5}, e7, {n5, n3}, e8,{n3, n5}, e9,{n6, n7}, e10,{n7, n8}, e11,{n8, n6}}2. 。=2192。證明192。設(shè)A為集合，(A)= a，證明(A)=2a。g≤b0。證明全體從N到N的嚴(yán)格單調(diào)遞增函數(shù)組成的集合和基數(shù)大于。a) ∑*，其中∑={a}。某工人在夜校學(xué)習(xí)，他打算用37天準(zhǔn)備考試，并決定復(fù)習(xí)60小時(shí)，每天至少用1小時(shí)，證明他必定在接連的一些天內(nèi)恰好共復(fù)習(xí)了13小時(shí)。設(shè)n∈I+，證明在能被n整除的正整數(shù)中必存在只由數(shù)字7和0組成的數(shù)。從小于201的正整數(shù)中任意選取101個(gè)，證明其中必有一個(gè)數(shù)能整除另一個(gè)數(shù)。a) A=R,B=(0,∞)；b) A=(0,1),B=[0,1)；c) A=[0,1),B=(1/4,1/2]；d) A=[0,1],B=(0,1)。；c) (AB)= A；d) A∩B=A∪B。問(wèn)共有多少個(gè)從A到B的內(nèi)射?用特征函數(shù)求下列各式成立的充分必要條件。證明f是可逆的當(dāng)且僅當(dāng)f有唯一的左(右)逆。設(shè)f:A→B和g:B→C。a) 找出它們的一個(gè)共同的左逆。有多少滿(mǎn)足以下條件的從A到A的函數(shù)f:a) fof= fb) fof= IAc) fofof= IA設(shè)f:X→Y且g:Y→Za) 若gof為滿(mǎn)射，g為內(nèi)射，則f為滿(mǎn)射b) 若gof為內(nèi)射，f為滿(mǎn)射，則g為內(nèi)射設(shè)f是從X到Y(jié)的雙射，證明(f1)1= f。設(shè)A={1,2,3}。domg。設(shè)f是從A到A的滿(mǎn)射且fof= f，證明f= IA。a) f:R→Rf(x)=2 xs={1}b) f:N→NNf(n)=n+n+1s={2,2}c) f:N→Nf(n)=2n+1s={2,3}d) f:I→Nf(x)=|x|s={1,0}e) f:[0,1]→[0,1]f(x)=2/x+1/4s=[0,1/2]f) f:[0,∞]→Rf(x)=1/(1+ x)s={0,1,2}g) f:{a,b}*→{a,b}*f(x)= xas={e,b,ba}h) f:(0,1)→(0,∞)f(x)=1/xs=(0,1)設(shè)n∈I+，f:A→A。試求fof, hog, goh及它們的定義域和值域。對(duì)于x∈R, g(x)= x 2。試求gof, fog, fof, gog, foh, hog, hof, goh和fohog。設(shè)f,g,h是從R到R的函數(shù)，對(duì)每個(gè)x206。c) 有多少個(gè)和f具有相同的定義域和值域的函數(shù)g:A2→I?設(shè)A和B為有限集，n(A)=m且n(B)=n。b) 寫(xiě)出f173。設(shè)A={－1,0,1}，則定義函數(shù)f:A2→I如下：寫(xiě)出f的全部序偶。195。 f[A]－f[B]，并舉例說(shuō)明不能用“=”代替其中的“202。195。(A)上的二元函數(shù)。(A)195。195。a) {1,2,3,2,3,4,3,1,4,4,1