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

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

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

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

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

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

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

A:對B:錯(cuò)

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

A:錯(cuò)B:對

答案:對一個(gè)圖的點(diǎn)連通度小于等于它的邊連通度。（）

A:對B:錯(cuò)

答案:對一個(gè)圖的點(diǎn)連通度和邊連通度不一定小于等于最小度。（）

A:對B:錯(cuò)

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

A:對B:錯(cuò)

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

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

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

A:錯(cuò)B:對

答案:錯(cuò)一個(gè)連通圖如果沒有奇度頂點(diǎn)，則它是歐拉圖。（）

A:對B:錯(cuò)

答案:對

第二章單元測試

如果一個(gè)圖的每個(gè)頂點(diǎn)的度都等于k，那么它是k-正則的。（）

A:錯(cuò)B:對

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

A:對B:錯(cuò)

答案:錯(cuò)下列說法錯(cuò)誤的是（）

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

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

A:對B:錯(cuò)

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

A:對B:錯(cuò)

答案:錯(cuò)下列說法錯(cuò)誤的是（）

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

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

A:對B:錯(cuò)

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

A:錯(cuò)B:對

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

A:對B:錯(cuò)

答案:錯(cuò)每個(gè)立方圖都有1-因子。（）

A:錯(cuò)B:對

答案:錯(cuò)

第三章單元測試

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

A:對B:錯(cuò)

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

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

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

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

答案:圖中的孤立點(diǎn)不是塊。四個(gè)點(diǎn)的完全圖不是3-連通圖。（）

A:對B:錯(cuò)

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

A:錯(cuò)B:對

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

A:錯(cuò)B:對

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

A:錯(cuò)B:對

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

A:錯(cuò)B:對

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

A:對B:錯(cuò)

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

A:錯(cuò)B:對

答案:對

第四章單元測試

下列說法正確的是（）

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

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

A:對B:錯(cuò)

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

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

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

A:錯(cuò)B:對

答案:對設(shè)一個(gè)平面圖的點(diǎn)數(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一個(gè)簡單平面圖的邊數(shù)和點(diǎn)數(shù)的關(guān)系是：m不大于3n-6。（）

A:對B:錯(cuò)

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

A:對B:錯(cuò)

答案:錯(cuò)每個(gè)平面圖的最小度至多為5。（）

A:對B:錯(cuò)

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

A:錯(cuò)B:對

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

A:錯(cuò)B:對

答案:對

第五章單元測試

每個(gè)平面圖是5-可著色的。（）

A:錯(cuò)B:對

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

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

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

A:對B:錯(cuò)

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

A:錯(cuò)B:對

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

A:對B:錯(cuò)

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

A:對B:錯(cuò)

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

A:錯(cuò)B:對

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

A:對B:錯(cuò)

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

A:對B:錯(cuò)

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

A:錯(cuò)B:對

答案:對

第六章單元測試

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

A:錯(cuò)B:對

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

A:錯(cuò)B:對

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

A:對B:錯(cuò)

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

A:對B:錯(cuò)

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

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

答案:任何NP問題都可以在多項(xiàng)式時(shí)間內(nèi)歸約到該問題如果一個(gè)問題可以在多項(xiàng)式時(shí)間內(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:多項(xiàng)式歸約D:指數(shù)歸約

答案:多項(xiàng)式歸約在證明一個(gè)問題是NPC時(shí)，需要滿足什么條件？（）

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

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

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

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

第七章單元測試

下列說法錯(cuò)誤的是（）

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

答案:最大度至少為4的子式是拓?fù)渥邮剑蛔邮揭欢ㄊ峭負(fù)渥邮剿胁话?個(gè)點(diǎn)的完全圖作為子式的邊極大圖的邊數(shù)不一定相同。（）

A:對B:錯(cuò)

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

A:對B:錯(cuò)

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

A:錯(cuò)B:對

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

A:對B:錯(cuò)

答案:對

第八章單元測試

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

A:對B:錯(cuò)

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

A:錯(cuò)B:對

答案:錯(cuò)Kruskal算法總是選擇連接兩個(gè)獨(dú)立的連通分量的邊。（）

A:錯(cuò)B:對

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

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

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

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

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

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

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

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

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

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

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

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

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

第九章單元測試

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

A:B:C:D:

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

A:錯(cuò)B:對

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

A:對B:錯(cuò)

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

A:B:C:D:

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

A:錯(cuò)B:對

答案:錯(cuò)

第十章單元測試

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

A:對B:錯(cuò)

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

A:錯(cuò)B:對

答案:對下列說法錯(cuò)誤的是（）

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

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

A: