圖論知到智慧樹(shù)章節(jié)測(cè)試課后答案2024年秋長(zhǎng)安大學(xué)

圖論知到智慧樹(shù)章節(jié)測(cè)試課后答案2024年秋長(zhǎng)安大學(xué)緒論單元測(cè)試

下列選項(xiàng)中正確的是（）.

A:圖論中的圖由若干給定的頂點(diǎn)及連接某些頂點(diǎn)對(duì)的邊所構(gòu)成B:圖論中圖是頂點(diǎn)集合上的一種二元關(guān)系C:圖的結(jié)構(gòu)是圖論的重要研究方向之一D:圖論的研究對(duì)象是圖

答案:圖論中的圖由若干給定的頂點(diǎn)及連接某些頂點(diǎn)對(duì)的邊所構(gòu)成；圖論中圖是頂點(diǎn)集合上的一種二元關(guān)系；圖的結(jié)構(gòu)是圖論的重要研究方向之一；圖論的研究對(duì)象是圖著名的哥尼斯堡七橋問(wèn)題最初由哪位數(shù)學(xué)家給出解答（）.

A:黎曼B:高斯C:歐幾里得D:歐拉

答案:歐拉在任意6個(gè)人的聚會(huì)上，總有3個(gè)人互相認(rèn)識(shí)，或者3個(gè)人互不認(rèn)識(shí).（）

A:錯(cuò)B:對(duì)

答案:對(duì)圖論中著名的中國(guó)郵遞員問(wèn)題是由中國(guó)管梅谷教授提出的.（）

A:對(duì)B:錯(cuò)

答案:對(duì)圖論與數(shù)學(xué)的其他分支形成的交叉研究方向有（）.

A:拓?fù)鋱D論B:模糊圖論C:隨機(jī)圖論D:代數(shù)圖論

答案:拓?fù)鋱D論；模糊圖論；隨機(jī)圖論；代數(shù)圖論

第一章單元測(cè)試

四個(gè)頂點(diǎn)的非同構(gòu)簡(jiǎn)單圖有（）.

A:8個(gè)B:11個(gè)C:9個(gè)D:10個(gè)

答案:11個(gè)序列稱(chēng)為圖序列，如果d是某一個(gè)簡(jiǎn)單圖的度序列.則下列不是圖序列的是（）.

A:(6,6,5,4,3,3,1)B:(7,6,5,4,3,2,2)C:(2,2,2,2,2,2,2)D:(3,3,2,2,2,1,1)

答案:(6,6,5,4,3,3,1)；(7,6,5,4,3,2,2)設(shè)圖G有21條邊，12個(gè)3度頂點(diǎn)，其余頂點(diǎn)的度均為2，則圖G的頂點(diǎn)數(shù)為（）.

A:16B:14C:15D:17

答案:15

下列哪些矩陣是本題中所給圖的鄰接矩陣？（）

A:B:C:D:

答案:；

本題中所給的兩個(gè)圖G與H不同構(gòu).（）

A:對(duì)B:錯(cuò)

答案:錯(cuò)

第二章單元測(cè)試

邊數(shù)比頂點(diǎn)數(shù)少1的簡(jiǎn)單圖一定是樹(shù).（）

A:對(duì)B:錯(cuò)

答案:錯(cuò)六個(gè)頂點(diǎn)的非同構(gòu)的樹(shù)有（）.

A:6個(gè)B:7個(gè)C:4個(gè)D:5個(gè)

答案:6個(gè)

本題中所給圖的非同構(gòu)生成樹(shù)的個(gè)數(shù)等于（）.

A:3個(gè)B:1個(gè)C:2個(gè)D:4個(gè)

答案:3個(gè)設(shè)G是五個(gè)頂點(diǎn)的標(biāo)號(hào)完全圖（即給G的每個(gè)頂點(diǎn)標(biāo)號(hào)），則G的不同的生成樹(shù)（注意“不同”是指標(biāo)號(hào)不同，不是不同構(gòu)）的個(gè)數(shù)等于（）.

A:5B:25C:625D:125

答案:125若G是單圈圖（即G是僅含一個(gè)圈的連通圖）,則G的邊數(shù)一定等于它的頂點(diǎn)數(shù).（）

A:錯(cuò)B:對(duì)

答案:對(duì)

第三章單元測(cè)試

若圖G的每條邊是割邊,則G是森林.（）

A:對(duì)B:錯(cuò)

答案:對(duì)若H是連通圖G的子圖,則H的連通度不超過(guò)G的連通度.（）

A:錯(cuò)B:對(duì)

答案:錯(cuò)若圖G沒(méi)有偶圈,則G的每個(gè)塊或是2個(gè)頂點(diǎn)的完全圖或是奇圈.（）

A:錯(cuò)B:對(duì)

答案:對(duì)設(shè)G是有n個(gè)頂點(diǎn)m條邊的k-邊連通圖,則下列一定成立的是（）.

A:B:C:D:

答案:

圖G的連通度、邊連通度和最小度分別為（）.

A:3,3,4B:3,4,4C:4,4,4D:4,3,4

答案:3,4,4

第四章單元測(cè)試

設(shè)M和N是簡(jiǎn)單圖G的兩個(gè)不同的完美匹配，則由M與N的對(duì)稱(chēng)差在G中的邊導(dǎo)出子圖的每個(gè)連通分支必為（）.

A:奇數(shù)個(gè)頂點(diǎn)的圈B:奇數(shù)個(gè)頂點(diǎn)的路C:偶數(shù)個(gè)頂點(diǎn)的路D:偶數(shù)個(gè)頂點(diǎn)的圈

答案:偶數(shù)個(gè)頂點(diǎn)的圈一棵樹(shù)T可以有兩個(gè)或者兩個(gè)以上的完美匹配.（）

A:錯(cuò)B:對(duì)

答案:錯(cuò)2n個(gè)頂點(diǎn)的完全圖中不同的完美匹配個(gè)數(shù)為（）.

A:(2n-1)!B:(2n)!!C:(2n)!D:(2n-1)!!

答案:(2n-1)!如果每個(gè)小伙子恰好認(rèn)識(shí)k個(gè)姑娘，而每個(gè)姑娘也恰好認(rèn)識(shí)k個(gè)小伙子(k>0)，則每個(gè)小伙子都能與自己認(rèn)識(shí)的姑娘結(jié)婚.（）

A:對(duì)B:錯(cuò)

答案:對(duì)

本題中所示圖沒(méi)有完美匹配.（）

A:對(duì)B:錯(cuò)

答案:錯(cuò)

第五章單元測(cè)試

本題中所示圖能一筆畫(huà)成（即筆不離紙，線不重復(fù)）.（）

A:錯(cuò)B:對(duì)

答案:錯(cuò)下列哪些是非空連通圖G有Euler跡的充分條件（）？

A:G有4個(gè)奇度頂點(diǎn)B:G有6個(gè)奇度頂點(diǎn)C:G有2個(gè)奇度頂點(diǎn)D:G沒(méi)有奇度頂點(diǎn)

答案:G有2個(gè)奇度頂點(diǎn)；G沒(méi)有奇度頂點(diǎn)如果非空連通圖G恰有2個(gè)奇度頂點(diǎn)，則G的Euler跡一定是從其中一個(gè)奇度頂點(diǎn)出發(fā)，終止于另一個(gè)奇度頂點(diǎn).（）

A:錯(cuò)B:對(duì)

答案:對(duì)

本題中所示圖是Hamilton圖.（）

A:對(duì)B:錯(cuò)

答案:錯(cuò)完全二部圖（m,n均大于0）是Hamilton圖的充分必要條件是（）.

A:m>n，m<n，m=n都不對(duì)B:m>nC:m<nD:m=n

答案:m=n

第六章單元測(cè)試

對(duì)于控制數(shù)為1的n個(gè)頂點(diǎn)的圖，其控制集中頂點(diǎn)的度為n-1.（）

A:對(duì)B:錯(cuò)

答案:對(duì)下列命題中正確的是（）.

A:一個(gè)圖的獨(dú)立數(shù)和點(diǎn)覆蓋數(shù)的和等于它的頂點(diǎn)數(shù)目B:一個(gè)圖的獨(dú)立數(shù)小于或者等于它的控制數(shù)C:頂點(diǎn)子集F是圖G的點(diǎn)覆蓋集當(dāng)且僅當(dāng)V(G)\F是G的獨(dú)立集D:任意控制集必含有一個(gè)最小控制集

答案:一個(gè)圖的獨(dú)立數(shù)和點(diǎn)覆蓋數(shù)的和等于它的頂點(diǎn)數(shù)目；頂點(diǎn)子集F是圖G的點(diǎn)覆蓋集當(dāng)且僅當(dāng)V(G)\F是G的獨(dú)立集

下列哪個(gè)選項(xiàng)中的集合分別是該圖的最大匹配、最小邊覆蓋集（）.

A:B:C:D:

答案:以下選項(xiàng)中正確的是（）.

A:Q是G的極大團(tuán)的充分必要條件是Q是G的補(bǔ)圖中的極大獨(dú)立集B:點(diǎn)覆蓋集必為控制集,控制集未必是點(diǎn)覆蓋集C:圖的邊覆蓋數(shù)和匹配數(shù)的和等于圖的頂點(diǎn)數(shù)D:任意6個(gè)人的聚會(huì)上,總有3人互相認(rèn)識(shí)或互不認(rèn)識(shí)

答案:Q是G的極大團(tuán)的充分必要條件是Q是G的補(bǔ)圖中的極大獨(dú)立集；任意6個(gè)人的聚會(huì)上,總有3人互相認(rèn)識(shí)或互不認(rèn)識(shí)若I是獨(dú)立集,則它是極大獨(dú)立集的充分必要條件是I是極小控制集.（）

A:錯(cuò)B:對(duì)

答案:錯(cuò)

第七章單元測(cè)試

Petersen圖的邊色數(shù)等于（）.

A:3B:5C:4D:6

答案:43-正則Hamilton圖的邊色數(shù)為（）.

A:6B:4C:5D:3

答案:3設(shè)H是圖G的子圖，則H的邊色數(shù)不超過(guò)G的邊色數(shù).（）

A:錯(cuò)B:對(duì)

答案:對(duì)Petersen圖的色數(shù)等于（）.

A:3B:4C:6D:5

答案:3設(shè)G是n個(gè)頂點(diǎn)的圈，則G的色多項(xiàng)式P(G,k)等于（）.

A:B:C:D:

答案:

第八章單元測(cè)試

可平面圖有可能存在子圖是不可平面圖.（）

A:對(duì)B:錯(cuò)

答案:錯(cuò)Petersen圖是可平面圖.（）

A:對(duì)B:錯(cuò)

答案:錯(cuò)若地圖上每?jī)蓚€(gè)地區(qū)都相鄰，則最多能有幾個(gè)地區(qū)（）.

A:3個(gè)B:5個(gè)C:2個(gè)D:4個(gè)

答案:4個(gè)正八面體的頂點(diǎn)數(shù)、邊數(shù)和面數(shù)分別為（）.

A:5,13,8B:5,12,8C:6,12,8D:6,12,9

答案:6,12,8從Petersen圖中需至少刪除幾條邊才能得到一個(gè)可平面子圖（）.

A:3條B:1條C:2條D:4條

答案:2條

第九章單元測(cè)試

設(shè)G是3個(gè)頂點(diǎn)的圈，則G的積和多項(xiàng)式為.（）

A:錯(cuò)B:對(duì)

答案:對(duì)完全二部圖的譜為（）.

A:-2,0,0,0,0,2B:-1,0,0,0,0,1C:-3,0,0,0,0,3D:-4,0,0,0,0,4

答案:-3,0,0,0,0,3五個(gè)頂點(diǎn)的完全圖的譜為（）.

A:2,-1,-1,-1,-1B:3,-1,-1,-1,-1C:1,-1,-1,-1,-1