圖論卷子測(cè)試A卷數(shù)本

1、*學(xué)院 20212021學(xué)年第二學(xué)期期末測(cè)試2021級(jí)本科數(shù)學(xué)與應(yīng)用數(shù)學(xué)專(zhuān)業(yè)?圖論?試卷 A本試卷總分值100分,測(cè)試時(shí)間110分鐘一、填空題每題2分,共20分1 .圖G的兩個(gè)子圖G1, G2的環(huán)和表示為.2 .圖G中的一圈,假設(shè)它通過(guò)G中的每一條邊或弧恰好一次,那么稱(chēng)該圈為 .3 .圖G的兩個(gè)不同的生成的樹(shù)T1, T2的頂點(diǎn)個(gè)數(shù).填相同或不相同4 .卜3,3是歐拉圖也是哈密頓圖這句話(huà)是.填對(duì)或錯(cuò)5 .圖G的任意頂點(diǎn)的關(guān)聯(lián)集都等于其余各頂點(diǎn)關(guān)聯(lián)集的 6 .p,q圖G的根本圈有個(gè).7 .連通圖G的邊連通度定義為 .8 .設(shè)M是G的一個(gè)匹配,如果G的每一個(gè)頂點(diǎn)都是M-飽和點(diǎn),那么M為.9 .使圖G

2、為n-著色的最小數(shù)值即為G的.10 .極大可平面圖的每一個(gè)面的次數(shù)都是.二、判斷題每題1分,共10分1 .同構(gòu)的圖保持鄰接關(guān)系.2 .最小生成樹(shù)即G的所有生成樹(shù)中權(quán)值最小的生成樹(shù).3 . K5是歐拉圖.4 .設(shè)G是無(wú)向連通圖,那么G是一筆畫(huà) G中沒(méi)有奇數(shù)度頂點(diǎn).5 .圖的秩等于圖的完全關(guān)聯(lián)矩陣的秩,而不等于其關(guān)聯(lián)矩陣的秩.6 .圖的關(guān)聯(lián)矩陣是對(duì)稱(chēng)矩陣.7 .圖的邊連通度大于最小頂點(diǎn)的度數(shù).8 .一個(gè)非完全連通圖的連通度就是使這個(gè)圖成為非連通圖所需要去掉的最小頂點(diǎn)數(shù).9 .完美匹配必定是最大匹配,但反之不然.10 . 一個(gè)圖是平面圖當(dāng)且僅當(dāng)它沒(méi)有收縮到 K5或K3,3的子圖.三、單項(xiàng)選擇題每題2

3、分,共20分1. 一個(gè)圖的所有頂點(diǎn)的度數(shù)之和不可能是A. 5B. 6C. 8 D. 102 .如果連通圖G的頂點(diǎn)個(gè)數(shù)為8,那么其生成樹(shù)中邊的個(gè)數(shù)為A. 7B. 6C. 9 D. 83 .在如下各圖中歐拉圖.4 .如下右圖所示,以下說(shuō)法正確的選項(xiàng)是 .A. a, e是點(diǎn)割集B. e 割點(diǎn)C. b, e是點(diǎn)割集D. d是點(diǎn)割集5 .如果連通圖G的頂點(diǎn)個(gè)數(shù)為7,邊數(shù)為8,那么其向量空間的維數(shù)為A. 9 B. 8 C. 7 D. 16 .設(shè)無(wú)向圖G的鄰接矩陣為0 110 010 0 111 0 0 0 0,0 10 0 10 10 10那么G的邊數(shù)為.A. 3 B. 4C. 5 D. 67 .如果連通

4、圖G的點(diǎn)連通度為2,邊連通度為3,圖的最小頂點(diǎn)的度數(shù)可能為A. 0 B. 1 C. 3 D, 28 . G的一個(gè)匹配M中的頂點(diǎn)M飽和頂點(diǎn)A.都不是 B.只有一個(gè)是C.有些是,有些不是D.全部是9 .如果連通圖G的最大頂點(diǎn)的度數(shù)3,那么圖G的色數(shù)不可能是A.2 B. 3 C. 4 D. 510 .如果一個(gè)圖含同胚于的子圖,它可能是可平面圖A. K5B. K3,3 C. 5 階完全圖 D. K3四、解做題每題10分,共40分1 .下列圖中各圖是否可以一筆畫(huà)出請(qǐng)寫(xiě)明理由.10分10分2 .求下列圖的完全關(guān)聯(lián)矩陣并以v1為參考點(diǎn)寫(xiě)出關(guān)聯(lián)矩陣和一個(gè)可逆大子陣3 .請(qǐng)答復(fù)一下問(wèn)題：1試說(shuō)明下列圖是否為正那

5、么圖請(qǐng)畫(huà)出該圖的一顆生成樹(shù)；2簡(jiǎn)述四色定理,畫(huà)出下列圖的一種頂點(diǎn)著色方案.4 .5項(xiàng)工作準(zhǔn)備分給5個(gè)人去做,如圖,其中邊f(xié)i, mj表示fi可以從事mj ,如果每個(gè)人最多從事其中一項(xiàng),且每項(xiàng)工作只能由一人擔(dān)任.問(wèn)怎樣才能使盡可能多的人安派上任務(wù)10 分flf2f3f4f5mi m2m3m4m5五、證實(shí)題10分證實(shí)：平面圖歐拉公式設(shè)G為p階q條邊f(xié)個(gè)面的連通平面圖,那么 p q+f=2.*學(xué)院20212021學(xué)年第二學(xué)期期末測(cè)試2021級(jí)本科數(shù)學(xué)與應(yīng)用數(shù)學(xué)專(zhuān)業(yè)?圖論?參考答案與評(píng)分標(biāo)準(zhǔn)A命題教師：*二、填空題參考答案：1, G G2； 2,鏈；3,相同；4,錯(cuò)；5,環(huán)合；6, q p 1 ; 7

6、,使得連通圖G變?yōu)椴贿B通的邊割集的最小邊數(shù)；8,完美匹配；9,色數(shù)；10,3評(píng)分標(biāo)準(zhǔn)：本局部每題2分.凡與答案一致的得2分,不一致含空白的不得分 、判斷題1-5 VWx x 6-10.XX,評(píng)分標(biāo)準(zhǔn)：本局部每題1分.凡與答案一致的得1分,不一致含未作判斷的不得分三、單項(xiàng)選擇題參考答案：1-5 AABBB 6-10 CCDDD評(píng)分標(biāo)準(zhǔn):本局部每題2分.凡與答案一致的得2分,不一致含未選的不得分 四、解做題1 .解：一個(gè)圖是“一筆畫(huà)當(dāng)且僅當(dāng)奇數(shù)度頂點(diǎn)的個(gè)數(shù)是0或2個(gè),因此2 3 4是“一筆畫(huà). 10分2 .解： 完全關(guān)聯(lián)矩陣關(guān)聯(lián)矩陣10 0 11 1 1 0此題答案不叱0答對(duì)艮SM0 1 1 0

7、110 1v 1為參考點(diǎn)10 分3.解：力 5*為4圖,0四為佟個(gè)頂點(diǎn)的度數(shù)不完全相同.該圖的生成樹(shù)不唯一,只要是該圖的子圖曲刪衾主締邊的樹(shù)即可.10分 S金金2四色的b加在一張地圖中,給地圖的各地域著色,要使鄰接的地域具有不同的顏色,0 1 1四種顏色用夠0該圖的色數(shù)為3,頂點(diǎn)著色方案不唯一,符合題意即可. 10分4.解：這個(gè)問(wèn)題即為：二部圖G V1,V2,E是否存在V1完美匹配.如下圖,實(shí)線(xiàn)表示 的即為一種分配方案 10分m 1 m2m3m4m5評(píng)分標(biāo)準(zhǔn)：本局部每題10分,考生每解出一個(gè)步驟,得相應(yīng)的分?jǐn)?shù).由于某一步單純計(jì)算錯(cuò)誤而導(dǎo)致其后數(shù)據(jù)錯(cuò)誤,但方法正確的,可以在不超過(guò)該局部應(yīng)得分一半的范圍內(nèi)給分 五、證實(shí)題證實(shí)：(1)假設(shè)G中無(wú)圈,那么G為無(wú)圈連通圖,是一顆樹(shù),必有一個(gè)度數(shù)為1的頂點(diǎn)v,刪除v及與它關(guān)聯(lián)的邊,記作G . G連通無(wú)圈,有p-1個(gè)頂點(diǎn),條邊和f個(gè)面.由歸納假設(shè),(p-1)- (q-1) +f=2,即p-q+f=2,得證q=k+1時(shí)結(jié)論成立.(5分)(2)假設(shè)G中有圈,那么刪去一個(gè)圈上的一條邊,記作G . G連通,有p個(gè)頂點(diǎn),q-1條邊和f-1 個(gè)面.由歸納假設(shè),p- (q-1)