數(shù)學(xué)競(jìng)賽圖論試題及答案一、單項(xiàng)選擇題（每題2分，共40分）1.設(shè)G是一個(gè)具有n個(gè)頂點(diǎn)的簡(jiǎn)單圖，若G中不存在長(zhǎng)度為3的環(huán)，則G中最多可以有多少條邊？A.n(n-1)/2

B.n(n-2)/2

C.n(n-3)/2

D.n(n-4)/22.下列關(guān)于二分圖的描述中，正確的是：A.二分圖一定包含偶數(shù)個(gè)頂點(diǎn)B.二分圖中任意兩個(gè)頂點(diǎn)之間都有邊相連

C.二分圖的頂點(diǎn)集可以劃分為兩個(gè)不相交的子集，使得每條邊的兩個(gè)頂點(diǎn)分別屬

于這兩個(gè)子集D.二分圖中不存在奇數(shù)長(zhǎng)度的環(huán)3.一個(gè)具有n個(gè)頂點(diǎn)的完全圖K_n的邊數(shù)是多少？A.nB.n-1C.n(n-1)/2

D.n^24.下列哪個(gè)圖論概念與圖的連通性無(wú)關(guān)？A.路徑B.環(huán)C.割點(diǎn)D.橋5.設(shè)G是一個(gè)連通圖，若從G中刪去任意一條邊后，G都不再連通，則稱G為：A.完全圖B.二分圖C.樹(shù)D.環(huán)圖6.下列關(guān)于圖的著色的說(shuō)法中，錯(cuò)誤的是：A.四色定理指出，任何平面圖都可以用不超過(guò)四種顏色著色B.圖的著色數(shù)是指用最少顏色給圖著色，使得相鄰頂點(diǎn)顏色不同C.二分圖一定可以用兩種顏色著色D.完全圖K_n的著色數(shù)一定是n7.一個(gè)無(wú)向圖G是連通的，當(dāng)且僅當(dāng)：A.G中至少有一條邊B.G中任意兩個(gè)頂點(diǎn)之間都存在路徑C.G中不存在孤立頂點(diǎn)D.G是二分圖8.下列關(guān)于歐拉圖的說(shuō)法中，正確的是：A.歐拉圖一定包含偶數(shù)個(gè)頂點(diǎn)B.歐拉圖中每個(gè)頂點(diǎn)的度數(shù)都是偶數(shù)C.歐拉圖中一定存在哈密爾頓回路D.歐拉圖一定是連通的9.設(shè)G是一個(gè)有向圖，若G中存在從頂點(diǎn)v到頂點(diǎn)w的路徑，但不存在從w到v的路徑，則稱：A.v是w的前驅(qū)B.w是v的后繼C.v可達(dá)wD.w可達(dá)v10.下列關(guān)于平面圖的說(shuō)法中，錯(cuò)誤的是：A.平面圖可以畫(huà)在平面上，使得邊與邊之間除了頂點(diǎn)外沒(méi)有交點(diǎn)B.庫(kù)拉托夫斯基定理給出了判斷一個(gè)圖是否是平面圖的充分必要條件C.任何平面圖都滿足歐拉公式D.完全圖K_5是平面圖二、多項(xiàng)選擇題（每題2分，共40分）1.下列哪些圖論概念與圖的遍歷有關(guān)？A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.拓?fù)渑判駾.最短路徑2.下列哪些圖是二分圖？A.完全二分圖K_{m,n}B.樹(shù)C.環(huán)圖C_n（n為偶數(shù)）D.完全圖K_n3.下列哪些條件可以保證一個(gè)無(wú)向圖是連通的？A.圖中任意兩個(gè)頂點(diǎn)之間都存在直接邊B.圖中存在一個(gè)生成樹(shù)C.圖中沒(méi)有孤立頂點(diǎn)，且邊數(shù)足夠多D.圖中每個(gè)頂點(diǎn)的度數(shù)都大于等于14.下列哪些說(shuō)法關(guān)于圖的著色是正確的？A.圖的著色問(wèn)題是一個(gè)NP完全問(wèn)題B.二分圖的著色數(shù)不超過(guò)2C.完全圖的著色數(shù)等于其頂點(diǎn)數(shù)D.圖的著色數(shù)一定小于其頂點(diǎn)數(shù)5.下列哪些圖論概念與有向圖的強(qiáng)連通性有關(guān)？A.強(qiáng)連通分量B.可達(dá)性C.環(huán)D.路徑6.下列哪些圖具有歐拉回路？A.每個(gè)頂點(diǎn)的度數(shù)都是偶數(shù)的連通圖B.完全圖K_n（n為奇數(shù)）C.環(huán)圖C_n（n為任意正整數(shù)）D.樹(shù)7.下列哪些條件可以判斷一個(gè)有向圖是否存在環(huán)？A.圖中存在強(qiáng)連通分量B.圖中存在一個(gè)頂點(diǎn)的入度等于出度C.使用拓?fù)渑判蛩惴〞r(shí)無(wú)法得到線性序列D.圖中存在哈密爾頓回路8.下列哪些圖論算法可以用于求解最短路徑問(wèn)題？A.Dijkstra算法B.Floyd算法C.深度優(yōu)先搜索D.廣度優(yōu)先搜索9.下列哪些說(shuō)法關(guān)于平面圖的性質(zhì)是正確的？A.平面圖的面數(shù)等于邊數(shù)減去頂點(diǎn)數(shù)加2B.平面圖的邊數(shù)不超過(guò)3n-6（n為頂點(diǎn)數(shù)，n≥3）C.任何平面圖都可以通過(guò)邊收縮操作轉(zhuǎn)化為更簡(jiǎn)單的平面圖D.庫(kù)拉托夫斯基圖是非平面圖10.下列哪些圖論概念與圖的匹配有關(guān)？A.完美匹配B.最大匹配C.最小路徑覆蓋D.哈密爾頓回路三、判斷題（每題1分，共10分）1.任何無(wú)向圖都至少有一個(gè)生成樹(shù)。（）2.完全圖K_n的邊數(shù)是n(n-1)。（）3.二分圖中一定不存在奇數(shù)長(zhǎng)度的環(huán)。（）4.歐拉圖中每個(gè)頂點(diǎn)的度數(shù)都是偶數(shù)。（）5.有向圖中存在環(huán)當(dāng)且僅當(dāng)圖中存在強(qiáng)連通分量。（）6.圖的著色數(shù)一定小于或等于其最大度數(shù)加1。（）7.平面圖一定可以嵌入到球面上而不產(chǎn)生邊交叉。（）8.任何連通圖都至少有一條哈密爾頓回路。（）9.深度優(yōu)先搜索和廣度優(yōu)先搜索都可以用于判斷圖的連通性。（）10.圖的匹配問(wèn)題中，完美匹配一定存在當(dāng)且僅當(dāng)圖中每個(gè)頂點(diǎn)的度數(shù)都相等。（）四、填空題（每題1分，共10分）1.一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向完全圖K_n的邊數(shù)為_(kāi)_____。2.二分圖G=(V1,V2,E)中，|V1|=m，|V2|=n，則G中最多可以有______條邊。3.圖的著色數(shù)是指用最少顏色給圖著色，使得相鄰頂點(diǎn)顏色不同，這個(gè)最少顏色數(shù)稱為圖的______。4.一個(gè)連通無(wú)向圖G中，如果刪除任意一條邊后圖都不再連通，則稱G為_(kāi)_____。5.歐拉圖中，從任意頂點(diǎn)出發(fā)，沿著邊行走，經(jīng)過(guò)每條邊恰好一次后能回到出發(fā)頂點(diǎn)的路徑稱為_(kāi)_____。6.有向圖中，如果存在從頂點(diǎn)v到頂點(diǎn)w的路徑，則稱v______w。7.平面圖G中，邊將平面劃分成的區(qū)域稱為G的______。8.圖的匹配是指圖中一組沒(méi)有公共頂點(diǎn)的邊集合，如果匹配中的邊數(shù)達(dá)到最大值，則稱該匹配為_(kāi)_____。9.拓?fù)渑判蚴侵笇?duì)有向無(wú)環(huán)圖（DAG）的頂點(diǎn)進(jìn)行線性排序，使得對(duì)于圖中的每一條有向邊(u,v)，u在排序中總是位于v的______。10.庫(kù)拉托夫斯基定理指出，一個(gè)圖是平面圖當(dāng)且僅當(dāng)它不包含與______或K_{3,3}同胚的子圖。答案：一、單項(xiàng)選擇題答案1.B2.C3.C4.B5.C6.D7.B8.B9.C10.D二、多項(xiàng)選擇題答案1.AB2.ABC3.B4.ABC5.AB6.AC7.C8.AB9.ABD10.AB三、判斷題答案1.錯(cuò)（非連通圖沒(méi)有生成樹(shù)）2.錯(cuò)（n(n-1)/2）3.對(duì)4.對(duì)5.錯(cuò)（有向圖中存在環(huán)不一定意味著存在強(qiáng)連通分量，但存在強(qiáng)連通分量一定意味著存在環(huán)）6.