圖論試題中法

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

2、面。8.有向圖回的底圖囚是連通的，則區(qū)至少為一連通有向圖；若存在一個以回的某個頂點 w 為根的外向樹，則區(qū)為一連通有向圖。b5E2RGbCAP二、畫圖題每題 5 分，共 15 分）1.畫出所有不同構(gòu)的 5 頂點樹。2.畫出 5 次正則完全圖，證明它是否為 Euler 圖。3.畫出面數(shù)最多的 6 頂點連通二分平面圖的平面嵌入，并指出它有幾個面。三、應(yīng)用題10 分）1.有回把鑰匙和回把鎖混在一起，確定知道每把鎖都能有一把鑰匙打開，鎖匠想把它們一對對的分開， 那么有多少種分法是每對中的鑰匙都無法打開鎖的。plEanqFDPw給出求解上述問題的遞歸公式，并證明之；算出三時問題的解。四、算法題第 1、2

3、、3 每題 10 分，4 題 15 分，共 45 分）1.寫出用 Kruskal 算法求圖 1 生成子樹的運(yùn)行過程：按算法的運(yùn)行順序?qū)懗雒恳惠喫x的邊；寫出對所選的邊所進(jìn)行的操作及其原因指出算法如何判斷所選邊是否符合生成樹的條件）；給出算法終止的條件。設(shè)算法按照下標(biāo)由小到大的順序遍歷所有邊，且對每條邊2.若有 5 字符出現(xiàn)的概率表為字符abcde出現(xiàn)概率0.20.160.130.280.23寫出用 Huffman 算法求上表中 5 字符 Huffman 編碼的運(yùn)行過程： 依“左子概率小于右子”的原則， 按算法的運(yùn)行順序?qū)懗雒恳惠啒?gòu)造的由有序二元樹組成的森林；給出算法終止的條件；按照“左 0 右

4、 1”的原則給出這 5 個字符的 Huffman 編碼。3.寫出用 Hungarian 算法求圖 2 完備匹配的運(yùn)行過程：按算法的運(yùn)行順序?qū)懗雒恳惠喫x擇的圖 1點，寫出從該點出發(fā)構(gòu)造的可增廣軌；按中所求的可增廣軌求出的本輪所得匹配；給出算法終止的條件。設(shè)初始匹配為,對算法中每條邊都表示為巴，對頂點的遍歷順序為一.）4,求圖 3 的中國郵路問題，設(shè)可為郵局。寫出求圖 3 的“倍邊”重邊）的過程；寫出用 FE 算法求 Euler 回路的過程；給出算法終止的條件，列出最后所得的中國郵路。設(shè)算法按照下標(biāo)由小到大的順序遍歷所有頂點，且對每條邊回，都有山。）個人收集整理資料，僅供交流學(xué)習(xí)，勿作商業(yè)用途山

5、東科技大學(xué)2008200820092009學(xué)年第一學(xué)期圖論考試試卷B 卷）班級姓名學(xué)號題號一二三四總得分評卷人審核人得分一、填空題每空 2 分，共 30 分）1.100 個頂點的星中有條邊。2.100 條邊的圖中全部頂點的總次數(shù)是。3.100 個頂點的圖的生成子樹中有個頂點和條邊。4.Peterson 圖是、否）Euler 圖，是、否）Hamilton 圖。5.m 的每個頂點次數(shù)為，總共有條邊，它種完美匹配，它的平面嵌入的厚度下界為。6.對一個好括號序列進(jìn)行檢測，從左向右至少數(shù)到第個括號時，會記錄下 50 個右括號。7.100 個面的極大連通平面圖中最多有條邊，個頂點。8.對有向圖回，若存在一

6、個以習(xí)的某個頂點回為根的內(nèi)向樹，則區(qū)為一連通有向圖；若存在一條有向 Hamilton 圈則回為一連通有向圖。DXDiTa9E3d二、畫圖題每題 5 分，共 15 分）1.畫出所有不同構(gòu)的只含一個圈的 4 頂點單圖。2.畫出 3 次正則完全二分圖，證明它是否為 Euler 圖。3.畫出面數(shù)最多的 5 頂點連通平面圖的平面嵌入，并指出它有幾個面。三、應(yīng)用題10 分）個人收集整理資料，僅供交流學(xué)習(xí)，勿作商業(yè)用途1.某次會議主席臺上有勻個座位，但會議組織者把入座名單搞丟了,于是他們又重新擺上名字，那么有多少種擺法是每個座位上的名字都錯了。RTCrpUDGiT給出求解上述問題的遞歸公式，并證明之；給出三

7、時問題的解。四、算法題第 1、2、3 每題 10 分，4 題 15 分，共 45 分）1.寫出用 Dijkstra 算法求圖 1 中從 w 點出發(fā)的單源最短軌的運(yùn)行過程：按算法的運(yùn)行順序?qū)懗雒恳惠唫溥x頂點集的變化和備選頂點的前驅(qū)；寫出每一輪求出的最短軌；給出算法終止的條件。設(shè)算法按照下標(biāo)由小到大的順序遍歷所有頂點，且對每條邊回，都有句。）2.若有 5 字符出現(xiàn)的概率表為字符abcde出現(xiàn)概率0.40.110.190.170.13寫出用 Huffman 算法求上表中 5 字符 Huffman 編碼的運(yùn)行過程：依“左子概率小于右子”的原則，按算法的運(yùn)行順序?qū)懗雒恳惠啒?gòu)造的由有序二元樹組成的森林；給出算法終止的條件；按照“左 0 右 1”的原則給出這 5 個字符的 Huffman 編碼。3.寫出用 Hungarian 算法求圖 2 完備匹配的運(yùn)行過程：|按算法的運(yùn)行順序?qū)懗雒恳惠喫x擇的XI點，寫出從該點出發(fā)構(gòu)造的可增廣軌；按中所求的可增廣軌求出的本輪所得匹配；給出算法終止的條件。圖2設(shè)初始匹配為 W1,對算法中每條邊都表示為回，對頂點的遍圖 1歷順序為）個人收集整理資料，僅供交流學(xué)習(xí),4,求圖 3 的中國郵路問題，設(shè)因為郵局,寫出求圖 3 的“倍邊”重邊）