圖論第一次作業(yè)

1、4.證明下面兩圖同構(gòu)。 Vi習(xí)題U43(a)證明：作映射f : v i? Ui (i=1,2.10)容易證明，對 ViVj E (a),有 f (v i Vj,), ,u i, Uj, ,E,(b) )(1 i 10,1 j 10 )由圖的同構(gòu)定義知，圖(a)與(b)是同構(gòu)的。5.證明：四個(gè)頂點(diǎn)的非同構(gòu)簡單圖有11個(gè)。證明：設(shè)四個(gè)頂點(diǎn)中邊的個(gè)數(shù)為m則有：m=0:m=1 :m=2：*m=3:m=4:m=5:m=6:因?yàn)樗膫€(gè)頂點(diǎn)的簡單圖最多就是具有6條邊，上面所列出的情形是在不同邊的條件下的不同構(gòu)的情形，貝以上面窮舉出的情況可以看出四個(gè)頂點(diǎn)的非同構(gòu)簡單圖 有11個(gè)。11.證明：序列(7,6,5,4

2、,3,3,2)和(6,6,5,4,3,3,1) 證明：由于7個(gè)頂點(diǎn)的簡單圖的最大度不會超過 6， 是圖序列；(6,6,5,4,3,3,1)是圖序列(d1,d2,|,dn),d1非負(fù)整數(shù)組d2ndn, dii 1不是圖序列。因此序列(7,6,5,4,332)不2m是圖序列的充要條件是:(d2 1,d3 1,|,dd111,dd1 2,|,dn)是圖序列是圖序列，然而(5,4,3,2,2,0)不是圖序列，所以(6,6,5,433,1)di 1(5,4,3,2,2,0不是圖序列。12證明：若2,則G包含圈。證明：下面僅對連通圖的下的條件下進(jìn)行證明，不連通的情形可以通過分成若干 個(gè)連通的情形來證明。設(shè)

3、 V(G) = Vi , V2,V3,? Vn,對于G中的路Vi , V2,V3,? Vn若Vk與Vi鄰接，則構(gòu)成一個(gè)圈。若Vii，V2,V3,? Vn是一條路，由于2 ,因此, 對于Vn，存在Vk與之鄰接，則Vk , ,? VnVk構(gòu)成一個(gè)圈。17. 證明：若G不連通，則G連通。證明：對于任意的u,v (G),若u與V屬于G的不同連通分支，顯然u與V在G中連 通；若u與V屬于g的同一連通分支，設(shè)w為G的另一個(gè)連通分支中的一個(gè)頂點(diǎn)， 則u與w，V與w分別在G中連通，因此，u與V在G中連通。18. 證明：若 e E(G),則w(G) < w(G- e) <w(G) + 1.證明：若e

4、為G的割邊，則w(G- e) = w(G) + 1，若e為G的非割邊，則w(G- e) =w(G)， 所以，若 e E(G)，則有 w(G) <w(G- e) < w(G) + 1.習(xí)題二：1.證明：非平凡樹的最長路的起點(diǎn)和終點(diǎn)均是1 度的。證明設(shè)P= V1V2Vk是非平凡樹T中一條最長路，若d(V1)>2則V1與Vk在T中的 鄰接點(diǎn)只能有一個(gè)，否則，若V1與除了 P中頂點(diǎn)之外的其他頂點(diǎn)相連，則P可以繼 續(xù)延長，這與P是最長路是相矛盾的。若V1與P上的某頂點(diǎn)相連，則就構(gòu)成了圈， 這與數(shù)相矛盾，推出P不是最長路。即說明V1與Vk是樹葉，則V1與Vk均是一度的。 所以非平凡樹的最

5、長路的起點(diǎn)和終點(diǎn)均是 1度的。9.證明：頂點(diǎn)度數(shù)為偶數(shù)的連通圖本身可構(gòu)成一個(gè)包含所有邊的閉跡。證明：證明：由于G是連通非平凡的且每個(gè)頂點(diǎn)度數(shù)為偶數(shù)，所以 G中至少存在 圈G,從G中去掉G中的邊，得到G的生成子圖G,若G沒有邊，則G的邊集合能劃 分為圈。否則，G的每個(gè)非平凡分支是度數(shù)為偶數(shù)的連通圖， 于是又可以抽取一 個(gè)圈。反復(fù)這樣抽取，E(G)最終劃分為若干圈。16.Kruskal 算法能否用來求：( 1 )賦權(quán)連通圖中的最大權(quán)的樹？( 2)賦權(quán)圖中的最小權(quán)的最大森林？如果可以，怎樣實(shí)現(xiàn)？ 答： 1、設(shè)G是G的邊劃分中的一個(gè)圈。若G僅由此圈組成，則G顯然是閉跡。否則，由于 G連通，所以，必然存

6、在圈C2,它和C1有公共頂點(diǎn)。于是，G UC2是一條含有G與 C2的邊的歐拉閉跡，如此拼接下去，得到包含 G的所有邊的一條閉跡.2、1.證明：不能，由Kruskal算法得到的任何生成樹一定是最小生成樹。 能a. 選擇邊e1使其權(quán)值最小b. 若已經(jīng)選定邊e1 e2 e3 ，-Sk從E-e1, e2, e3e，選擇邊ek+1c. Ge1,e2,e3 為無圈圖，且可以不連通d. ek+1的權(quán)值w (eK+1)盡可能小e. 當(dāng)a、b、c不能進(jìn)行時(shí)，停止。習(xí)題三：e是連通圖G的割邊當(dāng)且僅當(dāng)V(G)可劃分為兩個(gè)子集V1和V2 ,使對任 意u V及V V2, G中的路(u， V)必含e.證明：必要性：e是G

7、的割邊，故G- e至少含有兩個(gè)連通分支，設(shè) V是其中一 個(gè)連通分支的頂點(diǎn)集，V2是其余分支的頂點(diǎn)集，對u Vi, V V2，因?yàn)镚- e中的u,v不連通，而在G中u與V連通，所以e在每一條(u, V)路上，G中的(u, v)必 含 e。充分性：取u Vi,v V，由假設(shè)G中所有(u,v)路均含有邊e,從而在G- e中不存在從u與到V的路，這表明G- e不連通，所以e是割邊。3.設(shè) G 是階大于 2 的連通圖，證明下列命題等價(jià)：( 1 ) G 是塊(2) G 無環(huán)且任意一個(gè)點(diǎn)和任意一條邊都位于同一個(gè)圈上；( 3) G 無環(huán)且任意三個(gè)不同點(diǎn)都位于同一條路上。G是塊，任取G的一點(diǎn)u，邊e,在e邊插入

8、一點(diǎn)v,使得e成為兩條邊，由此 得到新圖G，顯然Gi的是階數(shù)大于2的塊，由定理4, Gi中的u,v位于同一個(gè) 圈上，于是G中u與邊e都位于同一個(gè)圈上。（2） f （3 ）：G無環(huán)，且任意一點(diǎn)和任意一條邊都位于同一個(gè)圈上，任取 G的點(diǎn)u，邊e， 若u不在e上，則三個(gè)不同點(diǎn)位于同一個(gè)圈，即位于同一條路，如 u在e上，由 定理e的兩點(diǎn)在同一個(gè)圈上，在e邊插入一個(gè)點(diǎn)V,使得e成為2條邊，由此得 到新圖G，顯然Gi的是階數(shù)大于2的塊，貝ffi條邊的三個(gè)不同點(diǎn)在同一條路上。（3） f（1）：G連通，若G不是塊，則G中存在著割點(diǎn)u,劃分為不同的子集塊Vi, V V, %無 環(huán)，x Vi, y V2，點(diǎn)u在每

9、一條（x, y）的路上，由于x,y的任意性，則三個(gè)不同 點(diǎn)不能位于同一條路上，則與已知矛盾，G是塊。7證明：若V是簡單圖G的一個(gè)割點(diǎn)，貝U v不是補(bǔ)圖G的割點(diǎn)。證明：V是單圖G的割點(diǎn)，則G- V至少兩個(gè)連通分支?，F(xiàn)任取x,y V（G- v）, 如果x,y在G- V的同一分支中，令u是與x,y處于不同分支的點(diǎn)，那么，通過u， 可說明，X,與y在G- v的補(bǔ)圖中連通。若x,y在G- v的不同分支中，貝尼們在 G- v的補(bǔ)圖中鄰接。所以，若V是G的割點(diǎn)，則V不是其補(bǔ)圖的割點(diǎn)。12對圖320給出的圖G1和G2,求其連通度和邊連通度，給出相應(yīng)的最小 點(diǎn)割和最小邊割。最小點(diǎn)割 6,8解：G1最小邊割 （6,5），（8,5） （6,7），（8,7）（6,9），（8,9）G2最小點(diǎn)割 6,7,8,9,10(G2)最小邊割 （