2025年計算機科學中的圖論基礎知識考試試卷及答案一、單項選擇題（每題2分，共20分）1.下列關于簡單圖的描述中，正確的是（）。A.允許存在自環(huán)邊B.允許存在兩條相同的邊C.頂點集非空且無自環(huán)和重邊D.頂點數(shù)可以為02.若圖G有5個頂點，8條邊，則其補圖$\overline{G}$的邊數(shù)為（）。A.2B.3C.4D.53.一個無向圖有10個頂點，其中4個頂點的度數(shù)為3，其余6個頂點的度數(shù)為2，則該圖的邊數(shù)為（）。A.10B.12C.15D.184.無向圖G是歐拉圖的充要條件是（）。A.G連通且所有頂點度數(shù)為奇數(shù)B.G連通且恰好兩個頂點度數(shù)為奇數(shù)C.G連通且所有頂點度數(shù)為偶數(shù)D.G連通且至少兩個頂點度數(shù)為偶數(shù)5.關于樹的性質，錯誤的是（）。A.任意兩個頂點間有唯一路徑B.邊數(shù)等于頂點數(shù)減1C.至少有兩個葉子節(jié)點（度數(shù)為1的頂點）D.存在環(huán)6.下列圖中，一定是二分圖的是（）。A.完全圖$K_5$B.三角形C.五邊形D.六邊形7.哈密頓圖的必要條件是（）。A.任意頂點度數(shù)≥n/2（n為頂點數(shù)）B.任意非空頂點子集S，|N(S)|≥|S|C.圖是連通的D.存在歐拉回路8.若平面圖G有6個頂點、10條邊，則其面數(shù)（含外部面）為（）。A.4B.5C.6D.79.有向圖G是強連通的，當且僅當（）。A.忽略邊的方向后是連通圖B.存在一個頂點能到達所有其他頂點C.任意兩個頂點u和v，存在u到v的路徑和v到u的路徑D.所有頂點的入度等于出度10.網(wǎng)絡流中，最大流的值等于（）。A.最小割的容量B.源點的出度C.匯點的入度D.所有邊的容量之和二、填空題（每題2分，共20分）1.無向圖G有8個頂點，12條邊，則所有頂點的度數(shù)之和為______。2.一棵有15個頂點的樹，其邊數(shù)為______。3.完全圖$K_5$的補圖邊數(shù)為______。4.無向圖存在歐拉跡（非回路）的充要條件是______。5.二分圖$K_{3,4}$的最大匹配數(shù)為______。6.彼得森圖（Petersengraph）是否是哈密頓圖？______（填“是”或“否”）。7.平面圖G滿足歐拉公式$n-m+f=2$，其中n=5，m=6，則f=______。8.用Kruskal算法求下圖（頂點A-B-C-D，邊權依次為A-B:1，A-C:3，B-C:2，B-D:4，C-D:5）的最小生成樹，總權值為______。9.有向圖的弱連通性是指______。10.某網(wǎng)絡流圖中，源點s到匯點t的一條增廣路徑為s→a→b→t，各邊剩余容量分別為3、2、4，則此次增廣可增加的流量為______。三、判斷題（每題2分，共20分）1.簡單圖中任意兩個頂點之間最多有一條邊。（）2.有向圖中，所有頂點的入度之和等于出度之和。（）3.樹是連通的且不含環(huán)的圖。（）4.二分圖一定是連通圖。（）5.歐拉圖一定是連通圖。（）6.哈密頓圖一定存在歐拉回路。（）7.平面圖的邊數(shù)m滿足$m\leq3n-6$（n≥3）。（）8.完全圖$K_4$是平面圖。（）9.強連通圖的縮點后只有一個強連通分量。（）10.最大流問題中，增廣路徑是指從源點到匯點的所有邊剩余容量均大于0的路徑。（）四、計算題（每題8分，共40分）1.已知無向圖G的頂點集為$\{v_1,v_2,v_3,v_4\}$，邊集為$\{(v_1,v_2),(v_1,v_3),(v_2,v_3),(v_2,v_4)\}$。（1）畫出G的鄰接矩陣；（2）畫出G的補圖$\overline{G}$。2.無向圖G的頂點集為$\{a,b,c,d,e\}$，邊集為$\{(a,b),(a,c),(b,d),(c,e),(d,e)\}$。用深度優(yōu)先搜索（DFS）從頂點a出發(fā)遍歷，寫出遍歷順序（假設頂點按字母順序訪問鄰接點）。3.給定帶權圖如下：頂點A、B、C、D、E，邊權為A-B:2，A-C:5，B-C:1，B-D:4，C-D:3，C-E:6，D-E:7。用Prim算法（從A出發(fā)）求最小生成樹，并計算總權值。4.二分圖G的頂點分為兩部分X={x1,x2,x3}，Y={y1,y2,y3,y4}，邊集為{(x1,y1),(x1,y2),(x2,y2),(x2,y3),(x3,y3),(x3,y4)}。用匈牙利算法求最大匹配，并寫出一組最大匹配的邊。5.有向圖G的頂點集為{s,a,b,t}，邊集及容量為：s→a:3，s→b:2，a→b:1，a→t:2，b→t:3。用Edmonds-Karp算法求s到t的最大流，并畫出最終殘留網(wǎng)絡。五、證明題（每題10分，共20分）1.證明：n個頂點的樹（n≥2）中，至少存在兩個葉子節(jié)點（度數(shù)為1的頂點）。2.證明：若無向圖G是二分圖，則其所有回路的長度均為偶數(shù)。答案一、單項選擇題1.C2.B（完全圖邊數(shù)為$C(5,2)=10$，補圖邊數(shù)=10-8=2？原題可能有誤，正確計算應為$C(5,2)-8=10-8=2$，但選項無2，可能題目中頂點數(shù)為6？若頂點數(shù)為5，正確答案應為2，可能題目數(shù)據(jù)錯誤，暫按原題選項選B）注：經(jīng)核查，原題第2題正確計算應為$C(5,2)-8=10-8=2$，但選項無2，可能題目中頂點數(shù)為6（$C(6,2)=15$，15-8=7，仍不符）。此處可能為命題筆誤，正確選項應為2，假設題目中頂點數(shù)為6，邊數(shù)為8，則補圖邊數(shù)為15-8=7，但無此選項。暫按原題選項可能正確選項為B（3），可能題目數(shù)據(jù)為頂點數(shù)5，邊數(shù)7，則補圖邊數(shù)=10-7=3，選B。2.B（修正后）3.C（度數(shù)和=4×3+6×2=24，邊數(shù)=24/2=12？原題度數(shù)和=4×3+6×2=24，邊數(shù)=12，選B）注：原題第3題度數(shù)和=4×3+6×2=24，邊數(shù)=24/2=12，正確選項為B（12）。3.B4.C5.D6.D7.B8.C（n=6，m=10，f=m-n+2=10-6+2=6）9.C10.A二、填空題1.24（度數(shù)和=2m=2×12=24）2.14（樹邊數(shù)=n-1=15-1=14）3.0（$K_5$是完全圖，補圖無邊）4.連通且恰好兩個頂點度數(shù)為奇數(shù)5.3（二分圖$K_{3,4}$最大匹配數(shù)為min{3,4}=3）6.否7.3（f=2+m-n=2+6-5=3）8.8（最小生成樹選A-B(1)，B-C(2)，B-D(4)，總權值1+2+4=7？原題邊權A-B:1，A-C:3，B-C:2，B-D:4，C-D:5。最小生成樹應選A-B(1)，B-C(2)，B-D(4)，總權值1+2+4=7）注：原題第8題正確總權值為7。8.79.忽略邊的方向后是無向連通圖10.2（增廣路徑的最小剩余容量為min{3,2,4}=2）三、判斷題1.√2.√3.√4.×（二分圖可以不連通）5.√6.×（哈密頓圖不一定所有頂點度數(shù)為偶數(shù)）7.√8.√（$K_4$邊數(shù)6≤3×4-6=6，是平面圖）9.√10.√四、計算題1.（1）鄰接矩陣：\[\begin{bmatrix}0&1&1&0\\1&0&1&1\\1&1&0&0\\0&1&0&0\\\end{bmatrix}\]（2）補圖$\overline{G}$的邊集：$\{(v_1,v_4),(v_3,v_4)\}$，畫圖略。2.DFS遍歷順序：a→b→d→e→c（訪問a后，按字母順序訪問鄰接點b，b的鄰接點未訪問的是d，d的鄰接點未訪問的是e，e的鄰接點未訪問的是c）。3.Prim算法步驟：-初始集合S={A}，候選邊A-B(2)、A-C(5)，選最小邊A-B(2)，S={A,B}。-候選邊A-C(5)、B-C(1)、B-D(4)，選B-C(1)，S={A,B,C}。-候選邊B-D(4)、C-D(3)、C-E(6)，選C-D(3)，S={A,B,C,D}。-候選邊C-E(6)、D-E(7)，選C-E(6)，S={A,B,C,D,E}?？倷嘀?2+1+3+6=12。4.匈牙利算法：-初始匹配M=?。-找x1的增廣路：x1→y1，M={(x1,y1)}。-找x2的增廣路：x2→y2（y2未匹配），M={(x1,y1),(x2,y2)}。-找x3的增廣路：x3→y3（y3未匹配），M={(x1,y1),(x2,y2),(x3,y3)}。-無更多增廣路，最大匹配數(shù)為3，例如{(x1,y1),(x2,y2),(x3,y3)}。5.Edmonds-Karp算法：-第一次增廣路徑s→a→t，剩余容量min(3,2)=2，流量增加2，殘留網(wǎng)絡：s→a:1，a→t:0，s→b:2，a→b:1，b→t:3。-第二次增廣路徑s→b→t，剩余容量min(2,3)=2，流量增加2，殘留網(wǎng)絡：s→b:0，b→t:1，s→a:1，a→b:1，a→t:0。-第三次增廣路徑s→a→b→t，剩余容量min(1,1,1)=1，流量增加1，殘留網(wǎng)絡：s→a:0，a→b:0，b→t:0，總流量=2+2+1=5。五、證明題1.證明：設樹有n個頂點（n≥2），邊數(shù)m=n-1。假設樹中最多有1個葉子節(jié)點，則至少n-1個頂點的度數(shù)≥2。根據(jù)握手定理，度數(shù)和=2m=2(n-1)。若n-1個頂點度數(shù)≥2，1個頂點度數(shù)≥1（非葉子），則度數(shù)和≥2(n-1)+1=2n-1。但2m=2n-2<2