圖論考試(中法)

《圖論考試(中法)》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、山東科技大學(xué)2008—2009學(xué)年第一學(xué)期《圖論》考試試卷（A卷）班級姓名學(xué)號題號一二三四總得分評卷人審核人得分一、填空題（每空2分，共30分）1.條邊的圖中全部頂點的總次數(shù)是100。2.100個頂點的星的最大頂點次數(shù)是。3.個頂點的圖的生成子樹中有個頂點和100條邊。4.Peterson圖（是、否）Euler圖，（是、否）Hamilton圖。5.的每個頂點次數(shù)為，總共有條邊，有種完美匹配，它的平面嵌入的厚度下界為。6.對一個括號序列進行檢測，從左向右數(shù)到第99個括號時，記錄了右括號個，因此得出結(jié)論為壞括號序列。7.100個頂點的極大連通平

2、面圖中最多有條邊，個面。8.有向圖的底圖是連通的，則至少為一連通有向圖；若存在一個以的某個頂點為根的外向樹，則為一連通有向圖。矚慫潤厲釤瘞睞櫪廡賴。二、畫圖題（每題5分，共15分）1.畫出所有不同構(gòu)的5頂點樹。2.畫出5次正則完全圖，證明它是否為Euler圖。3.畫出面數(shù)最多的6頂點連通二分平面圖的平面嵌入，并指出它有幾個面。三、應(yīng)用題（10分）1.有把鑰匙和把鎖混在一起，確定知道每把鎖都能有一把鑰匙打開，鎖匠想把它們一對對的分開，那么有多少種分法是每對中的鑰匙都無法打開鎖的。聞創(chuàng)溝燴鐺險愛氌譴凈。①給出求解上述問題的遞歸公式，并證明之；②

3、算出時問題的解。四、算法題（第1、2、3每題10分，4題15分，共45分）2/41.寫出用Kruskal算法求圖1生成子樹的運行過程：圖1①按算法的運行順序?qū)懗雒恳惠喫x的邊；②寫出對所選的邊所進行的操作及其原因（指出算法如何判斷所選邊是否符合生成樹的條件）；③給出算法終止的條件。（設(shè)算法按照下標由小到大的順序遍歷所有邊，且對每條邊，都有。）2.若有5字符出現(xiàn)的概率表為字符abcde出現(xiàn)概率0.20.160.130.280.23寫出用Huffman算法求上表中5字符Huffman編碼的運行過程：①依“左子概率小于右子”的原則，按算法的運行順

4、序?qū)懗雒恳惠啒?gòu)造的由有序二元樹組成的森林；②給出算法終止的條件；③按照“左0右1”的原則給出這5個字符的Huffman編碼。圖23.寫出用Hungarian算法求圖2完備匹配的運行過程：①按算法的運行順序?qū)懗雒恳惠喫x擇的點，寫出從該點出發(fā)構(gòu)造的可增廣軌；②按①中所求的可增廣軌求出的本輪所得匹配；③給出算法終止的條件。（設(shè)初始匹配為，對算法中每條邊都表示為，對頂點的遍歷順序為）圖34.求圖3的中國郵路問題，設(shè)為郵局。①寫出求圖3的“倍邊”（重邊）的過程；②寫出用FE算法求Euler回路的過程；③給出算法終止的條件，列出最后所得的中國郵路。（

5、設(shè)算法按照下標由小到大的順序遍歷所有頂點，且對每條邊，都有。）2/4山東科技大學(xué)2008—2009學(xué)年第一學(xué)期《圖論》考試試卷（B卷）班級姓名學(xué)號題號一二三四總得分評卷人審核人得分一、填空題（每空2分，共30分）1.100個頂點的星中有條邊。2.100條邊的圖中全部頂點的總次數(shù)是。3.100個頂點的圖的生成子樹中有個頂點和條邊。4.Peterson圖（是、否）Euler圖，（是、否）Hamilton圖。5.的每個頂點次數(shù)為，總共有條邊，它種完美匹配，它的平面嵌入的厚度下界為。6.對一個好括號序列進行檢測，從左向右至少數(shù)到第個括號時，會記錄下

6、50個右括號。7.100個面的極大連通平面圖中最多有條邊，個頂點。8.對有向圖，若存在一個以的某個頂點為根的內(nèi)向樹，則為一連通有向圖；若存在一條有向Hamilton圈則為一連通有向圖。殘騖樓諍錈瀨濟溆塹籟。二、畫圖題（每題5分，共15分）1.畫出所有不同構(gòu)的只含一個圈的4頂點單圖。2.畫出3次正則完全二分圖，證明它是否為Euler圖。3.畫出面數(shù)最多的5頂點連通平面圖的平面嵌入，并指出它有幾個面。三、應(yīng)用題（10分）1.某次會議主席臺上有個座位，但會議組織者把入座名單搞丟了，于是他們又重新擺上名字，那么有多少種擺法是每個座位上的名字都錯了。

7、釅錒極額閉鎮(zhèn)檜豬訣錐。①給出求解上述問題的遞歸公式，并證明之；②給出時問題的解。四、算法題（第1、2、3每題10分，4題15分，共45分）2/4圖11.寫出用Dijkstra算法求圖1中從點出發(fā)的單源最短軌的運行過程：①按算法的運行順序?qū)懗雒恳惠唫溥x頂點集的變化和備選頂點的前驅(qū)；②寫出每一輪求出的最短軌；③給出算法終止的條件。（設(shè)算法按照下標由小到大的順序遍歷所有頂點，且對每條邊，都有。）2.若有5字符出現(xiàn)的概率表為字符abcde出現(xiàn)概率0.40.110.190.170.13寫出用Huffman算法求上表中5字符Huffman編碼的運行過程

8、：①依“左子概率小于右子”的原則，按算法的運行順序?qū)懗雒恳惠啒?gòu)造的由有序二元樹組成的森林；②給出算法終止的條件；③按照“左0右1”的原則給出這5個字符的Huffman編碼。圖23