圖論智慧樹知到期末考試答案章節(jié)答案2024年長安大學

圖論智慧樹知到期末考試答案+章節(jié)答案2024年長安大學

答案:錯如果圖G是一個非平凡簡單圖且是一個正則圖，則其獨立數(shù)不超過圖G的頂點數(shù)的一半.（）

答案:對k正則圖一定存在完美匹配.（）

答案:錯設n,m,c分別表示圖G的頂點數(shù)、邊數(shù)和連通分支數(shù)，則G是森林的充分必要條件是m=n-c.（）

答案:對任何k-邊連通圖都是k-連通圖.（）

答案:錯每棵樹都是二部圖.（）

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

答案:錯設n,m,c分別表示圖G的頂點數(shù)、邊數(shù)和連通分支數(shù)，則G至少包含n–m+c個不同的圈.（）

答案:對5個頂點的完全圖不是可平面圖，但其刪掉任一條邊后所得之圖是可平面圖.（）

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

答案:錯圖G有完美匹配的充分必要條件是G有偶數(shù)個頂點.（）

答案:錯

答案:對每個沒有割邊的3-正則圖都有完美匹配.（）

答案:對不是塊的連通圖G至少有兩個塊，他們每個恰含有G的一個割點.（）

答案:對存在一個平面圖使得它恰好有5個面且任兩個面之間至少有一條公共邊.（）

答案:錯

答案:錯如果圖G的直徑至少是3，則其補圖的控制數(shù)不超過2.（）

答案:對任意圖的邊色數(shù)不超過它的最大度加1.（）

答案:對設G是簡單圖且G的每個頂點的度等于2，則G是一個圈.（）

答案:錯兩人或更多人組成的人群中，總有兩人在該人群內恰好有相同的朋友數(shù).（）

答案:對

答案:錯

答案:對連通是圖的頂點集上的一個等價關系.（）

答案:對恰有兩個頂點不是割點的簡單連通圖不一定是路.（）

答案:錯一棵樹T最多只有一個完美匹配.（）

答案:對若圖G的每個頂點的度都是偶數(shù)，則G沒有割邊.（）

答案:對任意兩個頂點均由唯一的路所連接的簡單圖一定是樹.（）

答案:對如果非空連通圖G有2個奇度頂點，則G有Euler閉跡.（）

答案:錯至少有兩個頂點的樹的最長路的起點和終點的度都等于1.（）

答案:對每條閉跡的邊集可被表示成一些圈的邊集的不交并.（）

答案:對設G=(X,Y)是k-正則二部圖，則X與Y所含頂點的個數(shù)可以不相等.（）

答案:錯連通圖中的兩條最長路必有公共頂點.（）

答案:對

答案:錯設G是簡單圖且其最小度至少為k，則G中一定有長為k的路.（）

答案:對同構關系是由簡單圖構成的集合上的一種等價關系.（）

答案:對

答案:錯

答案:對以下選項正確的是（）.

答案:最小控制集必是一個極小控制集###極小控制集不唯一###極小點覆蓋集未必是極小控制集設T是有n個頂點m條邊的一棵樹，則下列正確的是（）.

答案:T中任兩個頂點均由唯一的路連接###T連通###m=n-1###T無圈2n個頂點的完全圖的邊色數(shù)等于（）.

答案:2n-1設G是有n個頂點m條邊的簡單圖，則下列哪些可以作為G是樹的等價條件（）.

答案:G無圈且m=n-1###G連通且m=n-1###G連通，且對G的任意兩個不相鄰的頂點u與v，G+uv恰有1個圈###G連通，且對G中的任意一條邊e，G-e不連通正十二面體的頂點數(shù)、邊數(shù)和面數(shù)分別為（）.

答案:20,30,12每個不連通圖有1個孤立點（即度等于0的頂點）.（）

答案:錯簡單圖G的補圖H是指和G有相同頂點集的一個簡單圖，在H中兩頂點相鄰當且僅當它們在G中不相鄰.則下列正確的是（）.

答案:下列對Ramsey問題的描述，正確的是（）.

答案:用紅、藍兩種顏色對完全圖的邊染色,要求無論怎么染,都能要么出現(xiàn)染紅色的p階完全子圖,要么出現(xiàn)染藍色的q階完全子圖,這樣的完全圖至少應有多少個頂點?###求滿足條件的圖的最小頂點數(shù)，使得圖中要么有p-團，要么該圖的補圖有q-團###求滿足條件的圖的最小頂點數(shù)，使得圖中要么有p-團，要么有q個頂點的獨立集Petersen圖的連通度等于（）.

答案:3M是圖G的一個最大匹配當且僅當G中無M可擴路.（）

答案:對

答案:r(3,4)≥9

答案:m,n均為偶數(shù)正六面體的頂點數(shù)、邊數(shù)和面數(shù)分別為（）.

答案:8,12,6偶數(shù)個頂點的圈，匹配數(shù)和點覆蓋數(shù)的關系是（）.

答案:相等設M是圖G的關聯(lián)矩陣，則M的每一列元素之和等于（）.

答案:2四個頂點的非同構的樹有（）.

答案:2個Petersen圖中長度等于6的圈的個數(shù)等于（）.

答案:10

答案:m=n

答案:圖G的圍長定義為圖G的最短圈的長度（若圖G中無圈，則定義G的圍長為無窮大）.Petersen圖的圍長等于（）.

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

答案:16

答案:5

答案:4

答案:3

答案:81設G是一個有n個頂點、m條邊的連通圖，則下列一定成立的是（）.

答案:G至少包含n-m+1個不同的圈

答案:4下列選項哪個是正確的（）.

答案:圖G的極大獨立集必是G的極小控制集三個頂點的非同構簡單圖有（）.

答案:4個一個非空連通圖G是Euler圖的充分必要條件是（）.

答案:G沒有奇度頂點

答案:對設G是n（n大于或等于3）個頂點的路，則G的邊色數(shù)和彩虹連通數(shù)分別為（）.

答案:2,n-1

答案:10五個頂點的完全圖的譜為（）.

答案:4,-1,-1,-1,-1

答案:-3,0,0,0,0,3Petersen圖是可平面圖.（）

答案:錯可平面圖有可能存在子圖是不可平面圖.（）

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

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

答案:6,12,8若地圖上每兩個地區(qū)都相鄰，則最多能有幾個地區(qū)（）.

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

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

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

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

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

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

答案:對以下選項中正確的是（）.

答案:Q是G的極大團的充分必要條件是Q是G的補圖中的極大獨立集###任意6個人的聚會上,總有3人互相認識或互不認識若I是獨立集,則它是極大獨立集的充分必要條件是I是極小控制集.（）

答案:錯

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

答案:頂點子集F是圖G的點覆蓋集當且僅當V(G)\F是G的獨立集###一個圖的獨立數(shù)和點覆蓋數(shù)的和等于它的頂點數(shù)目下列哪些是非空連通圖G有Euler跡的充分條件（）？

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

答案:對

答案:錯

答案:m=n

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

答案:(2n-1)!

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

答案:偶數(shù)個頂點的圈如果每個小伙子恰好認識k個姑娘，而每個姑娘也恰好認識k個小伙子(k>0)，則每個小伙子都能與自己認識的姑娘結婚.（）

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

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

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

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

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

答案:錯

答案:3,4,4邊數(shù)比頂點數(shù)少1的簡單圖一定是樹.（）

答案:錯

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

答案:125六個頂點的非同構的樹有（）.

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

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

答案:15

答案:

答案:錯

答案:(6,6,5,4,3,3,1)###(7,6,5,4,3,2,2)四個頂點的非同構簡單圖有（）.

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

答案:對圖論中著名的中國郵遞員問題是由中國管梅谷教授