圖論及其應(yīng)用知到智慧樹章節(jié)測試課后答案2024年秋山東大學(xué)

圖論及其應(yīng)用知到智慧樹章節(jié)測試課后答案2024年秋山東大學(xué)第一章單元測試

一個圖的邊數(shù)m和所有點的度和r的關(guān)系是（）。

A:r=m/3B:r=2mC:r=m+1D:r=m

答案:r=2m下列說法正確的是（）。

A:一條跡上的邊可以重復(fù)B:一條路上的點可以重復(fù)C:邊不重復(fù)的途徑稱為跡D:點不重復(fù)的途徑稱為路

答案:邊不重復(fù)的途徑稱為跡；點不重復(fù)的途徑稱為路圖的周長是其中最長圈的長度。（）

A:對B:錯

答案:對圖的一個連通分支是它的一個極大連通子圖。（）

A:錯B:對

答案:對一個圖的點連通度小于等于它的邊連通度。（）

A:對B:錯

答案:對一個圖的點連通度和邊連通度不一定小于等于最小度。（）

A:對B:錯

答案:錯有向圖是強(qiáng)連通的是指，對其中的任意有序點對x，y，都有從x到y(tǒng)的路。（）

A:對B:錯

答案:對下列說法正確的是（）。

A:樹是無圈的連通圖B:一棵樹的兩個點之間僅有一條路C:如果一棵樹的最大度是k，那么至少有k個葉子頂點D:一棵樹可能含圈

答案:樹是無圈的連通圖；一棵樹的兩個點之間僅有一條路；如果一棵樹的最大度是k，那么至少有k個葉子頂點一個二部圖可能含奇圈。（）

A:錯B:對

答案:錯一個連通圖如果沒有奇度頂點，則它是歐拉圖。（）

A:對B:錯

答案:對

第二章單元測試

如果一個圖的每個頂點的度都等于k，那么它是k-正則的。（）

A:錯B:對

答案:對如果存在關(guān)于匹配M的增廣路，那么M可能是最大匹配。（）

A:對B:錯

答案:錯下列說法錯誤的是（）

A:2-因子的每個分支都是圈B:1-因子是圖的完美匹配C:設(shè)二部圖G=(X,Y)有1-因子，但是可能存在X的一個子集S，使得|N(S)|<|S|D:二部圖中最大匹配的邊數(shù)等于其邊的頂點覆蓋的最小基數(shù)

答案:設(shè)二部圖G=(X,Y)有1-因子，但是可能存在X的一個子集S，使得|N(S)|<|S|圖的一個1-因子也稱為完美匹配，包含了圖的所有頂點。（）

A:對B:錯

答案:對一個無橋的立方圖，它的邊連通度可能等于1。（）

A:對B:錯

答案:錯下列說法錯誤的是（）

A:一個立方圖，它的邊連通度可能等于1B:一個立方圖一定有1-因子C:一個立方圖，它的邊連通度不可能等于1D:一個立方圖一定含圈

答案:一個立方圖一定有1-因子；一個立方圖，它的邊連通度不可能等于1設(shè)k是自然數(shù)，那么每個k-正則二部圖包含1-因子。（）

A:對B:錯

答案:對設(shè)一個圖G有1-因子，那么對任意點子集S，G-S的奇分支數(shù)都小于等于S的點數(shù)。（）

A:錯B:對

答案:對設(shè)對圖G的任意點子集S，G-S的奇分支數(shù)都小于等于S的點數(shù)，那么圖G也不一定有1-因子。（）

A:對B:錯

答案:錯每個立方圖都有1-因子。（）

A:錯B:對

答案:錯

第三章單元測試

如果圖G是k-連通的，那么任意刪掉k-1點，它仍然是連通的。（）

A:對B:錯

答案:對下列說法正確的是（）

A:一個2-連通圖的最小度可以很大B:一個2-連通圖可能含有割點C:如果G是2-連通圖，那么從圖中去掉任意一個點，這個圖仍然是連通的。D:一個2-連通圖的最小度等于2

答案:一個2-連通圖的最小度可以很大；如果G是2-連通圖，那么從圖中去掉任意一個點，這個圖仍然是連通的。下列哪個說法是錯誤的（）

A:塊是一個沒有割點的極大連通分支。B:圖中的孤立點不是塊。C:每個連通圖的塊圖是一棵樹D:圖中的孤立點和孤立邊都是塊

答案:圖中的孤立點不是塊。四個點的完全圖不是3-連通圖。（）

A:對B:錯

答案:錯如果G是一個3-連通圖，但它不是四個點的完全圖，那么G中有一條邊e，使得G/e仍然是3-連通圖。（）

A:錯B:對

答案:對對于有向圖G的兩個點s，t，G中存在k條弧不交的s-t路的充要條件是任意刪掉k-1條邊，s仍然可以到達(dá)t。（）

A:錯B:對

答案:對一個階大于k的圖G是k-連通的，當(dāng)且僅當(dāng)對于G的兩個點s，t，G中存在k條獨立的s-t路。（）

A:錯B:對

答案:對如果圖G是k-邊連通的，那么對于G的兩個不交點集A和B，在A和B之間存在k條邊不交的路。（）

A:錯B:對

答案:對如果圖G是k-連通的，那么它也是k-連接的。（）

A:對B:錯

答案:錯對于任意自然數(shù)k，存在一個函數(shù)f(k)，使得每個f(k)-連通的圖是k-連接的。（）

A:錯B:對

答案:對

第四章單元測試

下列說法正確的是（）

A:五個點的完全圖不是可平面圖B:四個點的完全圖是可平面圖C:如果一個圖的細(xì)分圖是可平面圖，那么這個圖是可平面圖D:如果一個圖是可平面圖，那么這個圖的細(xì)分圖是可平面圖

答案:五個點的完全圖不是可平面圖；四個點的完全圖是可平面圖；如果一個圖的細(xì)分圖是可平面圖，那么這個圖是可平面圖；如果一個圖是可平面圖，那么這個圖的細(xì)分圖是可平面圖在一個2-連通平面圖中，每個面被一個圈所界定。（）

A:對B:錯

答案:對下列說法正確的是（）

A:對偶圖的邊對應(yīng)原圖的邊B:對偶圖的頂點對應(yīng)原圖的面C:一個平面圖的對偶圖的對偶圖就是它本身D:一個平面圖的對偶圖是可平面的

答案:對偶圖的邊對應(yīng)原圖的邊；對偶圖的頂點對應(yīng)原圖的面；一個平面圖的對偶圖的對偶圖就是它本身；一個平面圖的對偶圖是可平面的平面圖的對偶圖是連通的。（）

A:錯B:對

答案:對設(shè)一個平面圖的點數(shù)、邊數(shù)和面數(shù)分別是n、m和l，下列說法正確的是（）

A:n-m+l=-1B:n-m+l=1C:n-m+l=2D:n、m和l沒有關(guān)系

答案:n-m+l=2一個簡單平面圖的邊數(shù)和點數(shù)的關(guān)系是：m不大于3n-6。（）

A:對B:錯

答案:對Petersen圖是可平面圖。（）

A:對B:錯

答案:錯每個平面圖的最小度至多為5。（）

A:對B:錯

答案:對在一個無環(huán)的3-連通圖中，任意一個點的所有鄰點在同一個圈上。（）

A:錯B:對

答案:對由Kuratowski定理可以判定Petersen圖是非平面圖。（）

A:錯B:對

答案:對

第五章單元測試

每個平面圖是5-可著色的。（）

A:錯B:對

答案:對下列說法正確的是（）

A:一個圖的色數(shù)可能等于它的最大度加1。B:一個圖的色數(shù)可能與點數(shù)有關(guān)。C:一個圖的色數(shù)小于等于它的最大度加1。D:一個奇圈的色數(shù)等于3。

答案:一個圖的色數(shù)可能等于它的最大度加1。；一個圖的色數(shù)可能與點數(shù)有關(guān)。；一個圖的色數(shù)小于等于它的最大度加1。；一個奇圈的色數(shù)等于3。非平凡二部圖的色數(shù)等于2。（）

A:對B:錯

答案:對二部圖的邊色數(shù)等于它的最大度。（）

A:錯B:對

答案:對在正常邊著色圖中，由兩種不同顏色構(gòu)成的途徑不一定是一條路，其中的點可以重復(fù)。（）

A:對B:錯

答案:錯Vizing定理告訴我們，一個圖的邊色數(shù)介于最大度與最大度加1之間（）

A:對B:錯

答案:對每個k-色圖都包含一個最小度至少為k-1的k-色子圖。（）

A:錯B:對

答案:對二部圖是Vizing定理的第一類圖。（）

A:對B:錯

答案:對Vizing定理把有限圖分為兩類：色數(shù)等于最大度的圖為第一類，色數(shù)等于最大度加1的圖為第二類。（）

A:對B:錯

答案:對如果一個圖G的任意導(dǎo)出子圖H，都滿足H的色數(shù)等于H的團(tuán)數(shù)，那么稱G是完美圖。（）

A:錯B:對

答案:對

第六章單元測試

P問題是指是可以有一個確定型圖靈機(jī)在多項式時間內(nèi)解決的問題。（）

A:錯B:對

答案:對NP問題是指可以在多項式時間內(nèi)被圖靈機(jī)驗證的問題。（）

A:錯B:對

答案:對一個問題如果是NP-Hard問題，那么它一定是NP問題。（）

A:對B:錯

答案:錯NPC問題是指既是NP問題又具有特定性質(zhì)，即任何NP問題都可以在多項式時間內(nèi)歸約到該問題。（）

A:對B:錯

答案:對如果一個問題是NP-Hard，它的意思是：（）

A:該問題可以在多項式時間內(nèi)解決B:該問題比NP問題更容易C:該問題一定是NP問題D:任何NP問題都可以在多項式時間內(nèi)歸約到該問題

答案:任何NP問題都可以在多項式時間內(nèi)歸約到該問題如果一個問題可以在多項式時間內(nèi)解決，它被歸類為：（）

A:NPC問題B:NP-Hard問題C:P問題D:NP問題

答案:P問題下列哪些問題是NP問題？（）

A:哥德爾不完備定理B:背包問題C:最大團(tuán)問題D:旅行推銷員問題(TSP)

答案:背包問題；最大團(tuán)問題；旅行推銷員問題(TSP)NPC問題的證明通常涉及哪種類型的歸約？（）

A:線性歸約B:對數(shù)歸約C:多項式歸約D:指數(shù)歸約

答案:多項式歸約在證明一個問題是NPC時，需要滿足什么條件？（）

A:問題必須屬于P類B:問題必須有多項式時間算法C:問題必須可以在線性時間內(nèi)解決D:問題必須是NP問題

答案:問題必須是NP問題如果一個問題被證明是NPC問題，它的意義是什么？（）

A:該問題的解法可以在非常短的時間內(nèi)找到B:該問題的解法可以在多項式時間內(nèi)找到C:該問題在實際中沒有任何應(yīng)用D:該問題與其他NP問題具有相似的計算復(fù)雜性

答案:該問題與其他NP問題具有相似的計算復(fù)雜性

第七章單元測試

下列說法錯誤的是（）

A:最大度至少為4的子式是拓?fù)渥邮紹:拓?fù)渥邮揭欢ㄊ亲邮紺:最大度至多為3的子式是拓?fù)渥邮紻:子式一定是拓?fù)渥邮?/p>

答案:最大度至少為4的子式是拓?fù)渥邮?；子式一定是拓?fù)渥邮剿胁话?個點的完全圖作為子式的邊極大圖的邊數(shù)不一定相同。（）

A:對B:錯

答案:錯n個頂點的Turan圖關(guān)于點數(shù)和r個點的完全圖是極值的，并且是唯一的。（）

A:對B:錯

答案:對每個平均度至少為2的r-2次冪的圖都包含一個r個點的完全圖作為它的子式。（）

A:錯B:對

答案:對每個最小度至少為3，圍長至少為f(r)的圖，都包含一個r個點的完全圖作為子式。（）

A:對B:錯

答案:對

第八章單元測試

在Prim算法中，從一個起始節(jié)點開始，逐步添加節(jié)點以構(gòu)建最小生成樹。（）

A:對B:錯

答案:對Kruskal算法和Prim算法在找到最小生成樹時得到的結(jié)果總是相同的。（）

A:錯B:對

答案:錯Kruskal算法總是選擇連接兩個獨立的連通分量的邊。（）

A:錯B:對

答案:對集合覆蓋問題的目標(biāo)是什么？（）

A:最小化集合元素的數(shù)量B:最小化集合的數(shù)量C:最大化集合的數(shù)量D:最大化集合元素的數(shù)量

答案:最小化集合的數(shù)量什么是絕對近似算法？（）

A:一種總是能找到最優(yōu)解的算法B:一種總是能找到精確解的算法C:一種在多項式時間內(nèi)找到近似解的算法D:一種在指數(shù)時間內(nèi)找到最優(yōu)解的算法

答案:一種在多項式時間內(nèi)找到近似解的算法Prim算法和Kruskal算法都可以用于解決最小生成樹問題。它們之間的主要區(qū)別是：（）

A:Prim算法基于節(jié)點的操作，而Kruskal算法基于邊的操作。B:Prim算法總是生成相同的最小生成樹。C:Prim算法總是比Kruskal算法更高效。D:Kruskal算法總是生成相同的最小生成樹。

答案:Prim算法基于節(jié)點的操作，而Kruskal算法基于邊的操作。在Prim算法中，如果圖是不連通的，算法將會：（）

A:陷入無限循環(huán)B:無法執(zhí)行C:可以執(zhí)行但得到不完全的最小生成樹D:正常執(zhí)行

答案:可以執(zhí)行但得到不完全的最小生成樹當(dāng)最小生成樹不唯一時，哪些因素可能導(dǎo)致不同的最小生成樹？（）

A:不同算法B:邊權(quán)重相同C:不同起始節(jié)點D:圖不是連通圖

答案:不同算法；邊權(quán)重相同；不同起始節(jié)點關(guān)于k因子近似算法，哪些描述是正確的？（）

A:k因子近似算法總是提供精確的解。B:k因子近似算法的性能通常與近似因子k有關(guān)。C:k因子近似算法通常運行時間很長。D:k因子近似算法通常用于解決組合優(yōu)化問題。

答案:k因子近似算法的性能通常與近似因子k有關(guān)。；k因子近似算法通常用于解決組合優(yōu)化問題。

第九章單元測試

對任意的自然數(shù)r，下列說法錯誤的是（）

A:B:C:D:

答案:；若T是一個樹，那么存在無限個關(guān)于T是Ramsey極小的圖。（）

A:錯B:對

答案:錯Ramsey定理簡單來說就是：給定一個正整數(shù)r，每個充分大的圖G都包含r個點的完全圖作為導(dǎo)出子圖。（）

A:對B:錯

答案:錯對每個自然數(shù)r，都存在自然數(shù)n，使得每個連通圖（階數(shù)至少為n）一定包含哪些作為導(dǎo)出子圖？（）

A:B:C:D:

答案:對于稀疏圖的Ramsey數(shù)有以下性質(zhì)：具有有界最大度的圖H的Ramsey數(shù)以|H|的指數(shù)方式增長。（）

A:錯B:對

答案:錯

第十章單元測試

如果一個圖G的最小度大于點數(shù)的一半，則G是連通的。（）

A:對B:錯

答案:對哈密頓圈問題是NP-C問題。（）

A:錯B:對

答案:對下列說法錯誤的是（）

A:圖中最小獨立集的點數(shù)，稱為它的獨立數(shù)B:如果S是圖的獨立集，那么S中任意兩個頂點不相鄰C:圖的連通度是圖中最小分離集的點數(shù)D:圖中最大獨立集的點數(shù)，稱為它的獨立數(shù)

答案:圖中最小獨立集的點數(shù)，稱為它的獨立數(shù)如果一個圖的獨立數(shù)小于等于它的連通度，那么這個圖是哈密頓的。（）

A: