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

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