圖論試卷及參考答案A-13級數(shù)學本科.doc

專業(yè)：_ 班級：_ 學號：_ 姓名：_密封線專業(yè)：_ 班級：_ 學號：_ 姓名：_密封線*學院20132014學年第二學期期末考試數(shù)學與應用數(shù)學專業(yè)2013級圖論試卷A（本試卷滿分100分，考試時間110分鐘）一、 填空題 （每小題2分，共20分）15階完全圖G的邊的個數(shù)是_2如果圖G的每個頂點的度數(shù)都相同，則稱圖G為_圖3當且僅當無向連通圖G的頂點個數(shù)比邊的個數(shù)多1時，圖 G是_4無向圖G為歐拉圖當且僅當G連通，并且所有頂點的度都是 5(p,q) 圖G的向量空間的維數(shù)是_6圖G的任意一個頂點的關(guān)聯(lián)集都是其余各頂點關(guān)聯(lián)集的_75階完全圖的邊連通度是 8已知M是圖G的一個 ，若從G中一個頂點到另一個頂點存在一條道路，此路徑由屬于M和不屬于M的邊交替出現(xiàn)組成的，則稱此路徑為M-交錯道路9圖G是2-色的當且僅當G是 10極大平面圖所有面的次數(shù)均為 二、判斷題（每小題2分，共20分）1圖的所有頂點的度數(shù)之和是邊數(shù)的2倍2連通圖的一個生成樹是邊數(shù)最少的連通生成子圖3若一個圖是歐拉圖，那它也一定是哈密頓圖4圖的秩等于圖的完全關(guān)聯(lián)矩陣的秩，也等于其關(guān)聯(lián)矩陣的秩5r一定是r正則圖的一個特征值6圖的點連通度小于等于圖的邊連通度7若一個圖G存在完美匹配，則該匹配必定是最大匹配8圖G的一個M可增廣道路未必是一個M交錯道路9圖的邊著色問題可以轉(zhuǎn)化成圖的點著色問題 10設(shè)G為p階、q條邊、f個面的連通平面圖，則 p-q+f=2三、解答題（每小題5分，共30分）1試判斷下列兩個圖是否同構(gòu)2寫出下圖G的一個生成樹T并寫出圖G關(guān)于T的基本圈組EABCDGF3求下圖的完全關(guān)聯(lián)矩陣并以v2為參考點寫出關(guān)聯(lián)矩陣和一個可逆大子陣v1v4v3v2e2e3e4e1e54簡述圖的點連通度、邊連通度、最小頂點的度數(shù)三者之間的關(guān)系，并舉例說明5下面的圖中加粗的邊構(gòu)成最大匹配嗎？如果不是請說明理由f1f2m1f3f4f5m2m3m4m56試寫出下圖的一個著色方案，并回答該圖的色數(shù)v2v3v4v1v5四、應用題（每小題5分，共10分）1下圖是一個公園的平面圖，能不能使游人走遍每一條路不重復？入口和出口又應設(shè)在哪兒？ 2試建立下列問題的數(shù)學模型：有兩組化學藥品X和Y，每組各三類，設(shè)和，已知不同組的化學藥品不能放在一起，否則會發(fā)生爆炸現(xiàn)在將這些物品存放在三個倉庫1，2，3中，但由于物品的特性及倉庫自身的物理條件（如有無空調(diào)、通風條件等），和只允許放在1號和2號倉庫內(nèi)，和只允許放在2號和3號倉庫內(nèi)，和只允許放在1號和3號倉庫內(nèi)，問：滿足要求的存放方案是否存在？若存在，如何存放？五、證明題（每小題10分，共20分）1設(shè)T是一個無向（p,q）圖，證明T是樹則T無圈且q=p-12設(shè)G為p階連通平面圖, 有q條邊, 且每個面的次數(shù)不小于l (l 3), 證明 *學院20132014學年第二學期期末考試數(shù)學與應用數(shù)學專業(yè)2013級圖論參考答案與評分標準A命題教師：*二、 填空題 （每小題2分，共20分）參考答案：1120；2正則圖；3樹；4偶數(shù)；5q ;6環(huán)和；74；8匹配；9二部圖；103評分標準：本部分每小題2分凡與答案一致或意義相同的得2分，不一致（含空白）的不得分三、 判斷題（每小題2分，共20分）參考答案：1-5. 6-10.評分標準：本部分每小題2分凡與答案一致的得2分，不一致（含未做判斷）的不得分三、解答題（每小題5分，共30分）參考答案：1.解：建立一一映射，可知兩圖同構(gòu) （5分）2.解：因為圖的生成樹即其連通無圈的生成子圖，因此，去掉圖的一些邊使其保持連通無圈即得其生成樹下圖是其中的一種做法 （2分）EABCDGF 關(guān)于這棵樹的基本圈有6個：AEG，ABG，EFG，BCE，DEF，CDF（5分）3.解： （3分）其中一個可逆的大子陣 （5分）4.解：圖的點連通度、邊連通度、最小頂點的度數(shù)三者之間的關(guān)系為k(G)l(G)d (G) （3分）下圖是無向連通圖，點連通度k(G)=1，邊連通度l(G)=2，最小度d(G)=3，此圖滿足k(G)l(G)d (G) （5分）5.解： f1f2m1f3f4f5m2m3m4m5不是最大匹配，因為該圖中存在M-可增廣道路 （5分）6.該圖是3色的，顏色1：v1，v5，顏色2：v2，v4，顏色3：v3 （5分）本部分每小題5分，由于某些題的結(jié)果不唯一，因此要求只要運用理論正確，結(jié)果與答案等價，即得滿分；如果有些偏差，酌情扣分；如果關(guān)鍵部分錯誤，該得分點不得分四、 應用題（每小題5分，共10分）參考答案：1.這個問題可以歸結(jié)為一筆畫問題，一個連通圖存在歐拉圈當且僅當圖的頂點的度數(shù)是偶數(shù)H點和B點是奇點，其余都是偶點，所以入口和出口應設(shè)在H點和B點 （5分）2.解：以藥品為點，兩藥品不能放在一起則連邊，則得到一個二部圖，然后再對圖中每個點，指定一個集合，用以表示允許存放的倉庫和集合，即令，如下圖所示，于是問題轉(zhuǎn)化為對的點著色，但要求對每個點的著色，應選用各自的中所羅列的“顏色”，如下圖所示： 實際上，本問題的著色不存在 （5分）評分標準：本部分每小題5分，考生每解出一個步驟，得相應的分數(shù)由于某一步單純計算錯誤而導致其后數(shù)據(jù)錯誤，但方法正確的，酌情給分五、 證明題（每小題10分，共20分）參考答案：1.證明:由樹的定義可知T無圈下證q=p-1對p進行歸納證明 當p=1時，q=0，顯然q=p-1 假設(shè)p=k時結(jié)論成立，現(xiàn)證明p=k+1時結(jié)論也成立 （2分）由于樹是連通而無圈的，所以至少有一個度數(shù)為1的頂點，在T中刪去及其關(guān)聯(lián)邊，便得到個頂點的連通無圈圖 （4分）由歸納假設(shè)它有k-1條邊再將頂點及其關(guān)聯(lián)邊加回得到原圖T，所以T中含有k+1個頂點和k條邊，故結(jié)論q=p-1成立所以樹是無圈且q=p-1的圖即q=k+1時結(jié)論成立 （10分）2.證明：由于在計算面數(shù)之和時，每個邊被計算了兩次，因此各面次數(shù)之