一．填空題每空3分，共15分)1.不同構的3階簡單圖的個數為__4___。．圖1中的最小生成樹的權值為__20____。3.基于圖2的最優歐拉環游的總權值為。4.圖3中塊的個數為。461543683232126242733162圖1圖3圖25.圖4中強連通分支的個數為。圖4二．單項選擇每題3分，共15分)．關于圖的度序列，下列命題錯誤的是(D)(A)同構的兩個圖的度序列相同；(B)非負整數序列是圖的度序列當且僅當是偶數；n(d,d,,d)d12nii1(C)如果非負整數序列是一棵樹的度序列，那么序列(d,d,,d)(n12n1中至少有兩個整數的值為；(D).如果非負整數序列是簡單圖的度序列，那么在同構意(d,d,,d)12n義下只能確定一個圖。．關于階簡單圖的鄰接矩陣，下列說法錯誤的是（C）A(a)nijnn(A)矩陣的行和等于該行對應頂點的度數；A(B)矩陣所有元素之和等于該圖邊數的2倍；(C)不同構的兩個圖，它們的鄰接矩陣特征譜一定不同；(D)非連通圖的鄰接矩陣一定可以表示為準對角矩陣形式。3.關于歐拉圖，下面說法正確的是(B)(A)歐拉圖存在唯一的歐拉環游；(B)非平凡歐拉圖中一定有圈；(C)歐拉圖中一定沒有割點；(D)度數為偶數的圖一定是歐拉圖。4.關于哈密爾頓圖，下列命題錯誤的是(B)(A)設是的簡單圖，若其閉包是完全圖，則是哈密爾頓圖；Gn3G(B)若階單圖的閉包不是完全圖，則它一定是非哈密爾頓圖；n(C)若G是哈密爾頓圖，則對于的每個非空頂點子集，均有VS；GS)S(D)若G是的非H單圖，則G度弱于某個圖。n3Cm,n5.關于偶圖，下列說法錯誤的是(B)(A)偶圖中不存在奇圈；2(B)非平凡偶圖的最大匹配是唯一的；(C)正則偶圖存在完美匹配；k(k(D)偶圖中，最大匹配包含的邊數等于最小點覆蓋包含的頂點數。三、(20分在一個賦權完全圖中找到一個具有最小權值的哈密爾頓圈，稱這種圈為最優哈密爾頓圈。5中基于初始圈LTPPNML的近似最優哈密爾頓圈；(2)、如何獲取最優哈密爾頓eayc圈權值的一個下界？以圖5為例進行說明。LT2Pe圖5LL22解：(1)TTLL232TT由此獲得的一個近似最優解的權值為192.(2)設，必vCvC然是GvGvT是Gv的一棵最小生成樹，同時是中與點相關聯的兩條邊，使得,fGv它們的權值之和盡可能小，則WC)WT)W(e)W(f)，即獲得最優圈的一個下界。例如，在圖5中，取頂點，求出的一棵最小生成樹為GTPe而與Ny點相關聯的兩條權值之和盡可能小的邊是LNy與LMc,其權值之4和為35+21=56.由此獲取最優解的一個下界為178.四，(10分”的最少數目，等于具有性質“任意兩個1都不在同一條線上的1注：哥尼定理：在偶圖中，最大匹配包含的邊數等于最小點覆蓋包含的頂點數）證明：設布爾陣是n行m列矩陣，把它模型為一個偶圖如下：每行每列分別用一個點表示，X表示行點集合，Y表示列點集合，兩點連線。當且僅當該行該列元為1.于是，包含了所有1”的線的最少數目對應偶圖中的最小點覆蓋數。而具有性質任意兩個1都不在同一條線上的1的最大數目”對應偶圖的最大匹配包含的邊數。由哥尼定理，命題得到證明。五．(10分)求證：設是n階的具有m條邊的簡單連通平面圖，則：Gm3n6。證明：由于是n階的具有m條邊的簡單連通平面圖，所以每個面的Gf23次數f)3。由得到：。deg(f)2mmf2由連通平面圖的歐拉公式：nm2，將代入歐拉公式得到m3m3n6。六.(20分)一家公司計劃建造一個動物園，他們打算飼養下面這些動物：狒狒(b)、狐貍(f)(g)(h)(k)(l)(p)(r)鼩鼱(s)(w)和斑馬(z)狒狒喜歡吃山羊、非洲大羚羊(幼年)鼩鼱山羊、非洲大羚羊、羚羊和斑馬；獅子喜歡吃山羊、非洲大羚羊、羚羊和斑馬；豪豬喜歡吃鼩鼱和兔子；而其余的則喜歡吃蟲子、蚯蚓、草或其它植物。公司將飼養這些動5物，希望它們能自由活動但不能相互捕食。求這些動物的一個分組，使得需要的圍欄數最少。(要求用圖論方法求解)解：將動物模型為點，兩點連線當且僅當兩動物相克有捕食關系，根據題目描述，所作圖形如下：bzfghwskrlp問題轉化為求出圖的點色數，并用點色數種顏色對其正常點作色。下面求點色數：一方面，圖中存在K，所以(G)3，另一方面，我們用3種3顏色實現了對圖的正常頂點作色：1b1zf1ghw1332s3k3rl2p23狒狒(b)(f)、羚羊(w)和斑馬(z)；土狼(h)(l)、豪豬(p)；山羊(g)、非洲大羚羊(k)、兔子(r)、鼩鼱(s)。七．(10分求下圖G的色多項式P(G).并求出點色數。k6圖G解：圖G的補圖為：H12H的伴隨多項式為：H(x)xx211對于：，，，Hr0r1r4r121234所以：H(x)x4xx2342x35x所以：補圖的伴隨多項式為G(x)xxx4xx5x