圖論張先迪李正良課后習題答案 .doc

《圖論張先迪李正良課后習題答案 .doc》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、1.證明：在n階連通圖中(1)至少有n-1條邊；習題一作者---寒江獨釣(2)如果邊數(shù)大于n-1，則至少有一條閉跡；(3)如果恰有n-1條邊，則至少有一個奇度點。證明:(1)若G中沒有1度頂點，由握手定理：2md(v)2nmnmn1vV(G)若G中有1度頂點u，對G的頂點數(shù)作數(shù)學(xué)歸納。當n=2時，結(jié)論顯然；設(shè)結(jié)論對n=k時成立。當n=k+1時，考慮G-u,它仍然為連通圖，所以，邊數(shù)≥k-1.于是G的邊數(shù)≥k.(2)考慮G中途徑：W:v1v2Lvn1vn若W是路，則長為n-1;但由于G的邊數(shù)大于n-1,因此，存在vi與vj,它們相異，但鄰接。于ii1vvL是：vjvi為G中一閉途徑

2、，于是也就存在閉跡。(3)若不然，G中頂點度數(shù)至少為2，于是由握手定理：2md(v)2nmnmn1vV(G)這與G中恰有n-1條邊矛盾！2.(1)2??-1??2-1??-122(2)2??-2-1(3)2??-23.證明下面兩圖不同構(gòu)。u1v1證明:u1的兩個鄰接點與v1的兩個鄰接點狀況不同。所以，兩圖不同構(gòu)。4.證明下面兩圖同構(gòu)。5.v1v6v2v10v5v7v8v9v4v3(a)u1u2u10u7u6u5u8u3u4u9(b)證明:作映射f:vi?ui(i=1,2?.10)容易證明，對vivjE((a)),有f(vivj,),,ui,uj,,E,((b))(1i10,1j10)由圖

3、的同構(gòu)定義知，圖(a)與(b)是同構(gòu)的。3.指出4個頂點的非同構(gòu)的所有簡單圖。分析：四個頂點的簡單圖最少邊數(shù)為0，最多邊數(shù)為6，所以可按邊數(shù)進行枚舉。3.證明:1)充分性:當G是完全圖時，每個頂點的度數(shù)都是n-1,共有n個頂點，總的度數(shù)為n(n-1)，??(??-1)因此總的邊數(shù)是2=??(2).2)必要性:因為G是簡單圖,所以當G是完全圖的時候每個頂點的度數(shù)才達到最大:n-1.若G不是完全圖，則至少有一個頂點的度數(shù)小于n-1,這樣的話，總的度數(shù)就要小于n(n-1)??，因此總的邊數(shù)小于(2)，矛盾。所以G是完全圖。2m8.Δ與δ是簡單圖G的最大度與最小度，求證：n證明：由握手定理有：

4、nd(v)2mnvV(G)所以有：2mn9.證明：設(shè)

5、V1

6、=?1?,

7、V2

8、=?2?,?1?中點的度數(shù)之和為??1,,??2中點的度數(shù)之和為??2,??的邊數(shù)為m.有偶圖的定義可知d1=??=d2.而d1=k?1?,d2=??2?.?所以?1?=?2?.10.證明：將每個人看成一個頂點，若其中有兩個人是朋友，則將這兩個人所代表的頂點連接起來，這樣便得到了一個簡單圖。這個圖中每個頂點的度數(shù)就是這個頂點所代表的人的朋友的數(shù)目。因為簡單圖中至少有兩個頂點的度數(shù)相同，所以這些人中至少有兩個人這這個人群中的朋友數(shù)目是相同的。12.證明：若δ≥2，則G中必然含有圈。證明：只就連通圖證明即可！設(shè)W=

9、v1v2?..vk-1vk是G中的一條最長路。由于δ≥2，所以vk必然有相異于vk-1的鄰接頂點。又W是G中最長路,所以，這樣的鄰接點必然是v1,v2,?.,kv-2中之一。設(shè)該點為vm，則vmvm+1?.vkvm為G中圈。13.證明:不妨設(shè)G是連通的（否則可考慮其某一個連通分支）.設(shè)L=??1??2?????-1????是G中最長的一條路。因為δ≥2,所以V(G)中還有δ-1個點與????相鄰。因為L是最長的路,所以這些點在??1,??2,?,????-1中。又因為G是簡單圖，所以這些點不可能是????-1.設(shè)從??1開始????(1≤i≤k-1-δ)是這些點中第一個與????相鄰的點,

10、則????????+1?????????是G中的一個圈，其長度至少為δ+1.12.G的圍長是指G中最短圈的長；若G沒有圈，則定義G的圍長為無窮大。證明：（1）圍長為4的k的正則圖至少有2k個頂點，且恰有2k個頂點的這樣的圖（在同構(gòu)意義下）只有一個。（2）圍長為5的k正則圖至少有k2+1個頂點。證明(1)設(shè)u,v是G中兩相鄰頂點，則S(u)S(v)=,否則，可推出G中的圍長為3，與已知矛盾。因此，G中至少有2（k-1）+2個頂點，即有2k個頂點。把S(u)v，S(v)u連為完全偶圖，則得到2k個頂點的圍長為4的圖，由作法知，這樣的圖是唯一的。(2)設(shè)G是圍長為5的k正則圖,任取u∈V(G)記

11、S??={??∈??(??):??(??,??)=?}?(??=0,1,2,?).則:①S1中不同的頂點不相鄰;②?2?中每個頂點有且只有一條邊與S1相連.(若①或②不成立,則G的圍長不是5).這樣的話G的頂點數(shù)至少為

12、?0?

13、+

14、??1

15、+

16、??2

17、=1+??+??(??-1)=??2+1.13.證明:(1)①G連通②G不連通由m≥n>n-1知,G中至少有一個閉跡,所以G中包含圈.設(shè)G的所有的連通分支為??1,??2