圖論知到章節(jié)測試答案智慧樹2023年最新長安大學緒論單元測試

下列選項中正確的是（）.

參考答案:

圖論的研究對象是圖;圖論中圖是頂點集合上的一種二元關系;圖的結構是圖論的重要研究方向之一;圖論中的圖由若干給定的頂點及連接某些頂點對的邊所構成

著名的哥尼斯堡七橋問題最初由哪位數(shù)學家給出解答（）.

參考答案:

歐拉

在任意6個人的聚會上，總有3個人互相認識，或者3個人互不認識.（）

參考答案:

對

圖論中著名的中國郵遞員問題是由中國管梅谷教授提出的.（）

參考答案:

對

圖論與數(shù)學的其他分支形成的交叉研究方向有（）.

參考答案:

隨機圖論;代數(shù)圖論;模糊圖論;拓撲圖論

第一章測試

四個頂點的非同構簡單圖有（）.

參考答案:

11個

序列稱為圖序列，如果d是某一個簡單圖的度序列.則下列不是圖序列的是（）.

參考答案:

(7,6,5,4,3,2,2);(6,6,5,4,3,3,1)

設圖G有21條邊，12個3度頂點，其余頂點的度均為2，則圖G的頂點數(shù)為（）.

參考答案:

15

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

參考答案:

;

本題中所給的兩個圖G與H不同構.（）

參考答案:

錯

第二章測試

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

參考答案:

錯

六個頂點的非同構的樹有（）.

參考答案:

6個

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

參考答案:

3個

設G是五個頂點的標號完全圖（即給G的每個頂點標號），則G的不同的生成樹（注意“不同”是指標號不同，不是不同構）的個數(shù)等于（）.

參考答案:

125

若G是單圈圖（即G是僅含一個圈的連通圖）,則G的邊數(shù)一定等于它的頂點數(shù).（）

參考答案:

對

第三章測試

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

參考答案:

對

若H是連通圖G的子圖,則H的連通度不超過G的連通度.（）

參考答案:

錯

若圖G沒有偶圈,則G的每個塊或是2個頂點的完全圖或是奇圈.（）

參考答案:

對

設G是有n個頂點m條邊的k-邊連通圖,則下列一定成立的是（）.

參考答案:

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

參考答案:

3,4,4

第四章測試

設M和N是簡單圖G的兩個不同的完美匹配，則由M與N的對稱差在G中的邊導出子圖的每個連通分支必為（）.

參考答案:

偶數(shù)個頂點的圈

一棵樹T可以有兩個或者兩個以上的完美匹配.（）

參考答案:

錯

2n個頂點的完全圖中不同的完美匹配個數(shù)為（）.

參考答案:

(2n-1)!

如果每個小伙子恰好認識k個姑娘，而每個姑娘也恰好認識k個小伙子(k>0)，則每個小伙子都能與自己認識的姑娘結婚.（）

參考答案:

對

本題中所示圖沒有完美匹配.（）

參考答案:

錯

第五章測試

本題中所示圖能一筆畫成（即筆不離紙，線不重復）.（）

參考答案:

錯

下列哪些是非空連通圖G有Euler跡的充分條件（）？

參考答案:

G沒有奇度頂點;G有2個奇度頂點

如果非空連通圖G恰有2個奇度頂點，則G的Euler跡一定是從其中一個奇度頂點出發(fā)，終止于另一個奇度頂點.（）

參考答案:

對

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

參考答案:

錯

完全二部圖（m,n均大于0）是Hamilton圖的充分必要條件是（）.

參考答案:

m=n

第六章測試

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

參考答案:

對

下列命題中正確的是（）.

參考答案:

頂點子集F是圖G的點覆蓋集當且僅當V(G)\F是G的獨立集;一個圖的獨立數(shù)和點覆蓋數(shù)的和等于它的頂點數(shù)目

下列哪個選項中的集合分別是該圖的最大匹配、最小邊覆蓋集（）.

參考答案:

以下選項中正確的是（）.

參考答案:

Q是G的極大團的充分必要條件是Q是G的補圖中的極大獨立集;任意6個人的聚會上,總有3人互相認識或互不認識

若I是獨立集,則它是極大獨立集的充分必要條件是I是極小控制集.（）

參考答案:

錯

第七章測試

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

參考答案:

4

3-正則Hamilton圖的邊色數(shù)為（）.

參考答案:

3

設H是圖G的子圖，則H的邊色數(shù)不超過G的邊色數(shù).（）

參考答案:

對

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

參考答案:

3

設G是n個頂點的圈，則G的色多項式P(G,k)等于（）.

參考答案:

第八章測試

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

參考答案:

錯

Petersen圖是可平面圖.（）

參考答案:

錯

若地圖上每兩個地區(qū)都相鄰，則最多能有幾個地區(qū)（）.

參考答案:

4個

正八面體的頂點數(shù)、邊數(shù)和面數(shù)分別為（）.

參考答案:

6,12,8

從Petersen圖中需至少刪除幾條邊才能得到一個可平面子圖（）.

參考答案:

2條

第九章測試

設G是3個頂點的圈，則G的積和多項式為.（）

參考答案:

對

完全二部圖的譜為（）.

參考答案:

-3,0,0,0,0,3

五個頂點的完全圖的譜為（