1、電子科技大學研究生試題圖論及其應用參考答LOGODocument number SA80SAB-SAA9SYT-SAATC-SA6UT-SA18電子科技大學研究生試題圖論及其應用(參考答案)考試時間：120分鐘 一.填空題(每題3分，共18分)1 . 4個頂點的不同構的簡單圖共有_11_個；2 .設無向圖G中有12條邊，已知G中3度頂點有6個，其余頂點的度數均小于3o則G中頂點數至少有_9一個;3 .設n階無向圖是由k(k2)棵樹構成的森林，則圖G的邊數m=_n-k.4 .下圖G是否是平面圖答是；是否可1-因子分解答是5 .下圖G的點色數7(G)=,邊色數/(G)=_5-o二.單項選擇(每題3

2、分，共21分)1 .下面給出的序列中，是某簡單圖的度序列的是(A )(A) (11123); (B) (233445); (C) (23445); (D) (1333).2 .已知圖G如圖所示，則它的同構圖是(D )3 .下列圖中，是歐拉圖的是(D)4 .下列圖中，不是哈密爾頓圖的是(B )5.下列圖中，是可平面圖的圖的是(B )ABCD6 .下列圖中，不是偶圖的是（B ）7 .下列圖中，存在完美匹配的圖是（B ）三.作圖（6分）1 .畫出一個有歐拉閉跡和哈密爾頓的圖;2 .畫出一個有歐拉閉跡但沒有哈密爾頓的圖;的圖;4 .（10分）求下圖的最小生成樹，并求其最小生成樹的權值之和。解：由克魯斯

3、克爾算法的其一最小生成樹如下圖：權和為：20.5 .（8分）求下圖G的色多項式R（G）.解：用公式6（G-c）=）07型多 可得G的色多項式：PJG） = （Zb + 3（口 +2）（攵-3） o6 .（10分）一棵樹有m細點的度數為2, m個頂點的度數為3,，取個頂點的 度數為k,而其余頂點的度數為1,求1度頂點的個數。解：設該樹有m個1度頂點，樹的邊數為m.一方面：2m=ni+2n2+, , +knk另一方面：m= ni+n2+>*,+nk-l由上面兩式可得：ni=n2+2n3+ (k-1) nk七.證明：(8分)設G是具有二分類(X,Y)的偶圖，證明(1)G不含奇圈；(2)若 X

4、Y I，則G是非哈密爾頓圖。證明：(1)若不然，設C=v,2Va vi為G的一個奇圈，不妨設ViX, 則：vX,這樣推出V1與v.鄰接，與G是偶圖矛盾。(2)若XY,設|X|r|,則(G-Y)Y,由H圖的必要條件，G為非哈密爾頓圖。八.(8分)設G是邊數m小于30的簡單連通平面圖，證明:G中存在頂點v,使 d (v)4.證明：若不然，則對任意的vV(G),有d(v)5,這樣，一方面有:2m=d (v) 5n另一方面，G為簡單連通平面圖,有:1113n-6由，屋1?,把該式代入得:m30,與題設矛盾。九.(8分)證明：每個沒有割邊的3正則圖都有完美匹配。證明：設G是沒有割邊的3正則圖，S是V的真子集，用G, G%,或表示G-S的 奇分支，并設n是一個頂點在G中，另一個端點在S中的那些邊的條數。由于G是 3正則圖，所以日一)=3眸)|, lin由式,ve