電子科技大學(xué)研究生試題《圖論及其應(yīng)用》參考

1、電子科技大學(xué)研究生試題圖論及其應(yīng)用參照答案電子科技大學(xué)研究生試題圖論及其應(yīng)用參照答案電子科技大學(xué)研究生試題圖論及其應(yīng)用參照答案電子科技大學(xué)研究生試題圖論及其應(yīng)用(參照答案)考試時(shí)間：120分鐘一填空題(每題3分，共18分)14個(gè)極點(diǎn)的不同樣構(gòu)的簡(jiǎn)單圖共有_11_個(gè)；2設(shè)無(wú)向圖G中有12條邊，已知G中3度極點(diǎn)有6個(gè)，其余極點(diǎn)的度數(shù)均小于3。則G中極點(diǎn)數(shù)最少有_9_個(gè)；3設(shè)n階無(wú)向圖是由k(k2)棵樹(shù)構(gòu)成的森林，則圖G的邊數(shù)m=_n-k_;4以下列圖G是否是平面圖？答_是_;可否可1-因子分解？答_是_.圖G5以下列圖G的點(diǎn)色數(shù)(G)_,邊色數(shù)(G)_5_。圖G二單項(xiàng)選擇(每題3分，共21分)1下

2、面給出的序列中，是某簡(jiǎn)單圖的度序列的是(A)(A)(11123);(B)(233445);(C)(23445);(D)(1333).2已知圖G以下列圖，則它的同構(gòu)圖是（D）d121234bc434312a圖(G)ABCD3以下列圖中，是歐拉圖的是（D）ABCD4以下列圖中，不是哈密爾頓圖的是（B）ABCD5以下列圖中，是可平面圖的圖的是（B）ABCD6以下列圖中，不是偶圖的是（B）ABCD7以下列圖中，存在圓滿般配的圖是（B）ABCD三作圖(6分)1畫(huà)出一個(gè)有歐拉閉跡和哈密爾頓圈的圖；2畫(huà)出一個(gè)有歐拉閉跡但沒(méi)有哈密爾頓圈的圖；3畫(huà)出一個(gè)沒(méi)有歐拉閉跡但有哈密爾頓圈的圖；解：123四(10分)求以

3、下列圖的最小生成樹(shù)，并求其最小生成樹(shù)的權(quán)值之和。v1167v22v6435810v39v564v4解：由克魯斯克爾算法的其一最小生成樹(shù)以以下列圖：v11v7v22v643v346v5v4最小生成樹(shù)權(quán)和為：20.五(8分)求以下列圖G的色多項(xiàng)式Pk(G).圖G解：用公式Pk(Ge)Pk(G)Pk(G?e)，可得G的色多項(xiàng)式：Pk(G)(k)53(k)4(k)3k(k1)2(k2)(k3)。六(10分)一棵樹(shù)有n2個(gè)極點(diǎn)的度數(shù)為，3個(gè)極點(diǎn)的度數(shù)為，2n3nk個(gè)極點(diǎn)的度數(shù)為k，而其余極點(diǎn)的度數(shù)為1，求1度極點(diǎn)的個(gè)數(shù)。解：設(shè)該樹(shù)有n1個(gè)1度極點(diǎn)，樹(shù)的邊數(shù)為m.一方面：2m=n1+2n2+knk另一方面

4、：m=n1+n2+nk-1由上面兩式可得：n1=n2+2n3+(k-1)nk七證明：(8分)設(shè)G是擁有二分類(X,Y)的偶圖，證明(1)G不含奇圈；（2）若|X|Y|，則G是非哈密爾頓圖。證明：(1)若不然，設(shè)C=v12vmv1為G的一個(gè)奇圈，不如設(shè)v1X,v則：vmX,這樣推出v1與m毗鄰，與G是偶圖矛盾。v(2)若|X|Y|，設(shè)|X|Y|，則(G-Y)Y,由H圖的必要條件，為非哈密爾頓圖。八（8分）設(shè)G是邊數(shù)m小于30的簡(jiǎn)單連通平面圖，證明:G中存在極點(diǎn)v，使d(v)4.證明：若不然，則對(duì)任意的vV(G),有d(v)5，這樣，一方面有：2m=d(v)5n(1)另一方面，G為簡(jiǎn)單連通平面圖，有：m3n-6(2)由(1),n2m,把該式代入(2)得：m30,與題設(shè)矛盾。5九(8分)證明：每個(gè)沒(méi)有割邊的3正則圖都有圓滿般配。證明：設(shè)G是沒(méi)有割邊的3正則圖，S是V的真子集，用G1,G2,Gn表示G-S的奇分支，并設(shè)mi是一個(gè)極點(diǎn)在Gi中，另一個(gè)端點(diǎn)在S中的那些邊的條數(shù)。由于G是3正則圖，因此d(v)3V(Gi),vV(G)且d(v)3S1in(1)（2）vS由(1)式，mid(v)2E(Gi)是奇數(shù)。又由于