2017圖論電子科技大學(xué)研究生試卷答案

……效……………無(wú)……………題………電子科技大學(xué)研究生試卷至日一．填空題(每空5分，共25分)1.圖1中頂點(diǎn)到頂點(diǎn)的距離。d(a,b)_________ab院學(xué)……答……………內(nèi)……………以……………線……………封……………密12492348126ab29圖1名姓01101101002.已知圖G的鄰接矩陣，則G中長(zhǎng)度為2的途徑A110100010110010總條數(shù)為。3.圖2中最小生成樹(shù)的權(quán)值。WT)_______T4號(hào)學(xué)371121156……810圖214.圖3的最優(yōu)歐拉環(huán)游的權(quán)值為。526422331圖35.樹(shù)葉帶權(quán)分別為1,2,4,5,6,8的最優(yōu)二元樹(shù)權(quán)值為WT)二．單項(xiàng)選擇(每題3分，共15分)。1．關(guān)于圖的度序列，下列說(shuō)法正確的是()(A)對(duì)任意一個(gè)非負(fù)整數(shù)序列來(lái)說(shuō)，它都是某圖的度序列；(B)如果非負(fù)整數(shù)序列列；滿足n(d,d,,d)d12nii1(C)若圖G度弱于圖H，則圖G的邊數(shù)小于等于圖H的邊數(shù)；(D).如果圖G的頂點(diǎn)總度數(shù)大于或等于圖HG度優(yōu)于圖2．關(guān)于圖的割點(diǎn)與割邊，下列說(shuō)法正確的是（）(A)有割邊的圖一定有割點(diǎn)；(B)有割點(diǎn)的圖一定有割邊；(C)有割邊的簡(jiǎn)單圖一定有割點(diǎn)；(D)割邊不在圖的任一圈中。23.設(shè)kG)，，分別表示圖G的點(diǎn)連通度，邊連通度和最小度。()()GG下面說(shuō)法錯(cuò)誤的是()(A)存在圖G，使得kG)(B)存在圖G，使得==；()()GG；kG)G)G)(C)設(shè)G是n階簡(jiǎn)單圖，若n，則G連通，且2；G)G)()G(D)圖G是連通的，則G的連通度為。kk4.關(guān)于哈密爾頓圖，下列命題錯(cuò)誤的是()(A)彼得森圖是非哈密爾頓圖；(B)若圖G的閉包是哈密爾頓圖，則其閉包一定是完全圖；(C)若圖G的閉包是完全圖，則圖G是哈密爾頓圖；(D)設(shè)G是三階以上簡(jiǎn)單圖，若G中任意兩個(gè)不鄰接點(diǎn)與，滿足uv，則G是哈密爾頓圖。du)d(v)n5.下列說(shuō)法錯(cuò)誤的是()(A)有完美匹配的三正則圖一定沒(méi)有割邊；(B)沒(méi)有割邊的三正則圖一定存在完美匹配；(C)任意一個(gè)具有哈密爾頓圈的三正則圖可以1因子分解；(D)完全圖是個(gè)哈密爾頓圈的和。nK2n1三、(10分)設(shè)無(wú)向圖G有10度與4度頂點(diǎn)各2個(gè)，其余頂點(diǎn)度數(shù)均小于3，問(wèn)G中至少有幾個(gè)頂點(diǎn)？在最少頂點(diǎn)數(shù)的情況下，寫(xiě)出G的度序列，該度序列是一個(gè)圖序列嗎？。3解：要使得G中頂點(diǎn)數(shù)最少，度數(shù)小于3的頂點(diǎn)度數(shù)必須取2.設(shè)度數(shù)為2的頂點(diǎn)個(gè)數(shù)為，由握手定理：x32422x20，解得：x3所以，G中至少頂點(diǎn)個(gè)數(shù)為7.G的度序列由于，12所以，度序列為圖序列。四、(6分)求完全圖的鄰接譜。Kn解：完全圖的鄰接矩陣為Kn0111110111(K)n111011111011111111EA11nn1111111111n1所以：(K)n11n五，(6分)求證：一棵非平凡樹(shù)至少有兩片樹(shù)葉。證明設(shè)P=vvv是非平凡樹(shù)T中一條最長(zhǎng)路，則v與v在T中的12k1k鄰接點(diǎn)只能有一個(gè)，否則，要么推出P不是最長(zhǎng)路，要么推出T中存在圈，這都是矛盾！即說(shuō)明v與v是樹(shù)葉。124六，(6分)求證對(duì)于1mn的圖是非哈密爾頓圖。CK(KK)2m,nmmn2m證明：取S=V(k),則ω(G-S)=m+1>|S|=m,所以，由H圖的性質(zhì)知，mG是非H圖。七.(6是賦權(quán)完全偶圖Gl存在完美匹配，則是G的最優(yōu)匹配。GM*M*ll(v)證明：設(shè)M*是G的完美匹配，則：(M*)(e)lM*V(G)又設(shè)M是G的任一完美匹配，則：()wM()we()lvMV(G)ww即是的最優(yōu)匹配。G八.(6分)設(shè)簡(jiǎn)單可平面圖有10個(gè)4度頂點(diǎn)和8個(gè)5度頂點(diǎn)，其余頂G點(diǎn)度數(shù)均為7。求7度頂點(diǎn)的最大可能數(shù)量。解：設(shè)7度頂點(diǎn)有個(gè)。x一方面，由握手定理：410587x2m7即m40x2另一方面：由于圖G是可平面簡(jiǎn)單圖，因此：mn6于是得到：m3(108x)6483x7即得到：m40x483x2解得x16即7度頂點(diǎn)的最大可能數(shù)量為16.5九．(10分)求下圖G的色多項(xiàng)式P(G).并求出點(diǎn)色數(shù)。k解：圖G的補(bǔ)圖是圖4.H1H2圖G圖4對(duì)于對(duì)于因此：所以：由于:,,所以，Hr1r1h(H,x)xx21121：。所以，r0,r2,1Hh(H,x)2x2x322123hG,x)xx2xx2x3xx223345p(G)k]k][k]k345，所以，G)3。p(G)0,p(G)6236十.(10分)兔子(r)、鼩鼱(s)、羚羊(w)和斑馬(z)。根據(jù)經(jīng)驗(yàn)，動(dòng)物的飲食習(xí)慣為：狒狒喜歡吃山羊、非洲大羚羊、兔子和鼩鼱；狐貍喜歡吃山羊、豪豬、兔子和鼩鼱；土狼喜歡吃山羊、非洲大羚羊、羚羊和斑馬；獅子喜歡吃山羊、非洲大羚羊、羚羊和斑馬；豪豬喜歡吃鼩鼱和兔子；而其余的則喜歡吃蟲(chóng)子、蚯蚓、草或其它植物。公司將飼養(yǎng)這些動(dòng)物，希望它們能自由活動(dòng)但不能相互捕食。求這些動(dòng)物的一個(gè)分組，使得需要的圍欄數(shù)最少。(要求用圖論方法求解)解：每個(gè)動(dòng)物作為頂點(diǎn)，如果動(dòng)物要吃，則該兩點(diǎn)連線。xy()種顏色對(duì)圖G()GG進(jìn)行正常頂點(diǎn)作色。則色組即為動(dòng)物分組。z2w21b