《圖論》練習(xí)題201410

《《圖論》練習(xí)題201410》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、《圖論》練習(xí)題(2014)1、利用Dijkstra算法求下圖中頂點(diǎn)到其它各頂點(diǎn)的距離，并寫出到頂點(diǎn)的最短路。2、1、列出色數(shù)為的三個(gè)圖：。2、階完全圖的色數(shù)為：。3、階樹的鄰接多項(xiàng)式為：。4、階完全圖的鄰接多項(xiàng)式為：。5、如下圖所示的圖的鄰接矩陣為　　　　　　　　　　，關(guān)聯(lián)矩陣為　　　　　　　　。6、度序列為的簡單圖是　　　　　　　　　　　　。7、是否存在度序列為，的簡單圖？若存在，給出一個(gè)圖；若不存在，請說明理由。8、畫出如下圖的所有生成子圖。9、設(shè)圖如下圖所示，求該圖的生成樹個(gè)數(shù)。610、已知圖G（V、E），畫出G－V5，G－v3

2、v4，G[{v2，v3，v5}]，G[{v3v4，v4，v6，v7v8}]G：11、已知圖G的鄰接矩陣，畫出G，并求出度序列。12、證明：偶圖G的任意子圖H仍為偶圖。13、證明：設(shè)圖G（V、E）的度序列為（），邊數(shù)為q，則14、證明：在任何圖中，奇頂點(diǎn)個(gè)數(shù)為偶數(shù)。15、證明：整數(shù)序列（6，6，5，4，3，3，1）不可能為一個(gè)簡單圖的圖序列。16、證明頂點(diǎn)度數(shù)均為的簡單連通圖是圈。17、證明非平凡樹的邊連通度為。18、階完全圖的連通度為。19、設(shè)G是一個(gè)p階圖，且，則G連通圖。20、若圖G是不連通的，則其補(bǔ)圖GC是連通的。621、證明：

3、設(shè)是由和兩個(gè)連通分支組成的圖，則。22、證明：設(shè)是由和兩個(gè)連通分支組成的圖，則。23、證明：如果是連通圖的一個(gè)割點(diǎn)，則不是的割點(diǎn)。24、證明：如果是不連通的，則是連通的。反之不成立，試舉例說明。25、設(shè)圖G為簡單圖且δ≥k，k∈/N，則G包含一條長為R的路。26、若G的最小度δ（G）≥2，則G中存在一條長度至少為δ（G）+1的圈。27、設(shè)圖G（V、E）且

4、V

5、＝p，

6、E

7、＝q，則G為樹當(dāng)且僅當(dāng)G為連通的且p＝q＋1。28、證明：圖G為樹當(dāng)且僅當(dāng)G的任意兩個(gè)不同頂點(diǎn)之間存在唯一的一條路。29、畫出全部非同構(gòu)的6階樹。30、利用Cayle

8、y公式計(jì)算圖G的生成樹數(shù)目（寫出演算過程）。G：31、下列圖是否為Enler圖？G1：G2：32、證明：為條邊的階樹當(dāng)且僅當(dāng)不包含圈且。33、證明：設(shè)為條邊的階連通簡單圖且，則包含圈。34、證明：為樹當(dāng)且僅當(dāng)?shù)娜我鈨蓚€(gè)不同頂點(diǎn)之間存在唯一的一條路。635、證明：非平凡樹的最長路的起點(diǎn)和終點(diǎn)均為懸掛點(diǎn)。36、證明：恰好有兩個(gè)懸掛點(diǎn)的樹是一條路。37、證明圖G為非平面圖。G：38、給出下圖G的一個(gè)最大匹配（最大對(duì)集）。G：39、設(shè)圖G有完美匹配，則G為偶數(shù)階圖。40、證明：路至多有一個(gè)完美匹配。41、證明：樹至多有一個(gè)完美匹配。42、寫出

9、p（≥1）階樹T的色多項(xiàng)式，并確定T的色數(shù)。43、寫出5個(gè)階輪圖W5的色多項(xiàng)式，并求χ（w5）W5：44、設(shè)G為任一偶圖，則χ（G）≤2。45、證明：一個(gè)8×8方格棋盤移去其中兩個(gè)對(duì)角上的1×1方格之后，不可能用1×2長方形恰好填滿剩余棋盤。646、證明：非平凡連通偶圖的色數(shù)為。47、證明圈的色數(shù)為或。48、證明：設(shè)為具有條邊的階極大平面圖，則。49、證明：設(shè)為階平面圖，則其最小度。50、證明：Ramsey數(shù)。51、證明：Ramsey數(shù)。52.平面上有n個(gè)點(diǎn)，其中任意兩個(gè)的距離至少為1。證明，這n個(gè)點(diǎn)中至多有3n對(duì)點(diǎn)，每對(duì)點(diǎn)的距離恰好

10、是1。證:將n個(gè)點(diǎn)看成是圖G的n個(gè)頂點(diǎn)，若兩點(diǎn)的距離為1，則該兩個(gè)頂點(diǎn)相鄰（有連邊）。平面上和點(diǎn)v距離為1的點(diǎn)就是圖G中和頂點(diǎn)v相鄰的頂點(diǎn)。由于平面上和點(diǎn)v距離為1的點(diǎn)的個(gè)數(shù)至多為6，所以圖G中頂點(diǎn)v的度數(shù)滿足d(v)≦6.從而圖G中的邊數(shù)q(G)≦3n(As2q(G)=∑d(v)≤6n)。即平面上這n個(gè)點(diǎn)中至多有3n對(duì)點(diǎn)，每對(duì)點(diǎn)的距離恰好是1。53.試證明：在任何一群人中，認(rèn)識(shí)這群人中奇數(shù)個(gè)人的人有偶數(shù)個(gè)。（匈牙利，1942）證明：把每個(gè)人用頂點(diǎn)表示，若兩人認(rèn)識(shí)，則它們之間有邊相連，故認(rèn)識(shí)這群人中奇數(shù)個(gè)人的頂點(diǎn)度數(shù)為奇數(shù)，由推論1即

11、可得證。54.證明：在空間中，不可能有這樣的多面體存在，它們有奇數(shù)個(gè)面，而它們的每個(gè)面又都有奇數(shù)條邊。（北京，1956）證明：假設(shè)存在這樣的多面體，將這多面體的面用頂點(diǎn)表示，當(dāng)且僅當(dāng)兩個(gè)面有公共棱時(shí)，在相應(yīng)的頂點(diǎn)間連一邊，得圖G。按題意，G有奇數(shù)個(gè)奇頂點(diǎn)。顯然，這樣的圖不存在，故這樣的多面體是不存在的。55．平面上有n條線段，n≥3，其中任意3條都有公共點(diǎn)，則這n條線段有一個(gè)公共點(diǎn)。證:將這n條線段的端點(diǎn)看作一個(gè)圖G的頂點(diǎn)，線段看作G的邊，依題意，G是無圈的連通圖，且最長的路的長度是2，所以G是星圖（如圖5所示），即這n條線段有一個(gè)公

12、共點(diǎn)。56.某工廠有六種顏色的紗，用來生產(chǎn)雙色布，每種雙色布用兩種顏色搭配織成。在生產(chǎn)過程中，每種顏色的紗至少各其他三種顏色的紗搭配。證明，可以選出三種不同的雙色布，它們包含所有六種顏色的紗。（匈牙利數(shù)學(xué)競賽題）6證:先