《圖論》5-8章-習(xí)題課

1.

平面圖G的對(duì)偶G*同構(gòu)于G時(shí)，稱G為自對(duì)偶圖。證明：G=(V,E)為自對(duì)偶圖時(shí)，有m=2n

2。這里n=|V|，m=|E|?！秷D論》4-8章習(xí)題課1.平面圖G的對(duì)偶G*同構(gòu)于G時(shí)，稱G為自對(duì)偶圖。證明：G=(V,E)為自對(duì)偶圖時(shí)，有m=2n

2。這里n=|V|，m=|E|。提示：歐拉公式：n

m+d=2 對(duì)偶性：d=n* 同構(gòu)性：n*=n

聯(lián)立解得?！秷D論》4-8章習(xí)題課2.證明：Perterson圖不是平面圖?！秷D論》4-8章習(xí)題課2.證明：Perterson圖不是平面圖。《圖論》4-8章習(xí)題課證一：反證。設(shè)其為平面圖，則n

m+d=2。每個(gè)面至少有5條邊，則2m

5d，或d

2/5m。故n

m+2/5m

2，即m

5/3(n

2)。將n=10,m=15代入得15

5/3

8，矛盾?！秷D論》4-8章習(xí)題課2.證明：Perterson圖不是平面圖。證二：反證。設(shè)其為平面圖。由圖示，每個(gè)面至少有5條邊，即l=5，代入： 得： 3m

5(n2) 將n=10,m=15代入得4540，矛盾。3.設(shè)G是邊數(shù)m小于30的簡單平面圖，證明G中存在節(jié)點(diǎn)v，deg(v)

4。《圖論》4-8章習(xí)題課3.設(shè)G是邊數(shù)m小于30的簡單平面圖，證明G中存在節(jié)點(diǎn)v，deg(v)

4。證明：不妨設(shè)G是連通的。若G是一棵樹，結(jié)論顯然成立。設(shè)G中有回路。反證：若G中所有結(jié)點(diǎn)的度均大于等于5，則2m

5n。聯(lián)立m

3n

6得m

30，矛盾?！秷D論》4-8章習(xí)題課4.設(shè)簡單平面圖G中結(jié)點(diǎn)數(shù)n=7，邊數(shù)m=15。證明G是連通的?！秷D論》4-8章習(xí)題課4.設(shè)簡單平面圖G中結(jié)點(diǎn)數(shù)n=7，邊數(shù)m=15。證明G是連通的。證明：反證。設(shè)G不連通，有k個(gè)連通分支G1,G2,…,Gk，Gi對(duì)應(yīng)結(jié)點(diǎn)數(shù)和邊數(shù)分別為ni和mi。不存在1階的連通分支，否則G只能由平凡圖加上K6才能構(gòu)成m=15，而K6是不可平面的。也不存在2階的連通分支K2，否則G最多由K2加上K5也只能構(gòu)成m=10<15。因此任意連通分支的階必大于等于3。由mi

3ni

6，對(duì)全部連通分支求和得m

3n

6k。將n=7,m=15代入得k

1?！秷D論》4-8章習(xí)題課5.

將平面分成x個(gè)區(qū)域，且使得任意兩個(gè)區(qū)域都相鄰，問x最大是多少？《圖論》4-8章習(xí)題課5.

將平面分成x個(gè)區(qū)域，且使得任意兩個(gè)區(qū)域都相鄰，問x最大是多少？證明：上述分法得到平面圖G，設(shè)其對(duì)偶為G*。可知G*的任意兩個(gè)頂點(diǎn)都鄰接，即G*是一個(gè)完全圖。又G*是一個(gè)平面圖，故最多G*為K4。即x的最大值是4。《圖論》4-8章習(xí)題課6.

設(shè)G是連通的平面圖，證明：G為二部圖當(dāng)且僅當(dāng)G的對(duì)偶圖為歐拉圖?！秷D論》4-8章習(xí)題課6.

設(shè)G是連通的平面圖，證明：G為二部圖當(dāng)且僅當(dāng)G的對(duì)偶圖為歐拉圖。證明：設(shè)G的對(duì)偶為G*，則G*是連通的。必要性：G為二部圖，則G中無奇數(shù)長度回路，故G*中無奇數(shù)度頂點(diǎn)，因此G*是一個(gè)歐拉圖。充分性：G*是一個(gè)歐拉圖，則G*中無奇數(shù)度頂點(diǎn)，故G中無奇數(shù)長度回路，因此G為一個(gè)二部圖?！秷D論》4-8章習(xí)題課7.

證明：k色圖G中至少有k(k

1)/2條邊?！秷D論》4-8章習(xí)題課7.

證明：k色圖G中至少有k(k

1)/2條邊。證明：按G的一個(gè)k正常著色方案劃分G的頂點(diǎn)為k個(gè)集合V1,V2,…,Vk。則任給i,j，i

j，在Vi和Vj之間必有邊相連，否則給Vi和Vj的頂點(diǎn)染上相同顏色，可以得到G的一個(gè)k

1正常著色方案，與G的色數(shù)是k矛盾。將Vi用一個(gè)結(jié)點(diǎn)ui取代，得到一個(gè)k階完全圖，其邊數(shù)恰為k(k

1)/2。《圖論》4-8章習(xí)題課8.

色數(shù)的圖解求法：如圖，求其色數(shù)(G)。

《圖論》4-8章習(xí)題課《圖論》4-8章習(xí)題課 (G)=min{(K5),(K4),(K3)}=(K3)=3K5K4K4K39-1.色數(shù)多項(xiàng)式的圖解求法：加邊法。如圖，求其色數(shù)多項(xiàng)式?！秷D論》4-8章習(xí)題課《圖論》4-8章習(xí)題課 PG(k)=PK4(k)+2PK3(k)+PK2(k) =k(k

1)(k

2)(k

3)+2k(k

1)(k

2)+k(k

1) =k44k3+6k2

3k9-2.

色數(shù)多項(xiàng)式的圖解求法：減邊法。如圖，求其色數(shù)多項(xiàng)式?！秷D論》4-8章習(xí)題課《圖論》4-8章習(xí)題課 PG(k)

=k4

3k3+3k2

k10.

如圖是一份PCB板設(shè)計(jì)圖，孔位x1~x9,y1~y3已經(jīng)確定，聯(lián)結(jié)邊（導(dǎo)通）e1~e9。問至少要分成幾層板才能實(shí)現(xiàn)?！秷D論》4-8章習(xí)題課x1x2x3x4x5y1y2y3x6x7x8x9e1e2e3e4e5e6e7e8e910.解：PCB要求將設(shè)計(jì)圖P中發(fā)生交叉的邊分配到不同的層面。若將同層的邊染以相同顏色，問題轉(zhuǎn)化為求最少顏色數(shù)。構(gòu)造圖G如下：以頂點(diǎn)vi標(biāo)示圖P的邊ei，G的兩個(gè)頂點(diǎn)vi,vj鄰接當(dāng)且僅當(dāng)P中的兩條邊ei,ej?！秷D論》4-8章習(xí)題課v1v2v3v4v5v6v7v8v910.易得G的色數(shù)為3，即至少需要3層板。給出G的一種染色方案，相應(yīng)可以得到P的一種鋪板方案?！秷D論》4-8章習(xí)題課v1v2v3v4v5v6v7v8v910.

P的一種3層鋪板方案?！秷D論》4-8章習(xí)題課x1x2x3x4x5y1y2y3x6x7x8x9e1e2e5e7e9x1x2x3x4x5y1y2y3x6x7x8x9e3e4e8x1x2x3x4x5y1y2y3x6x7x8x9e611.

點(diǎn)獨(dú)立集與點(diǎn)覆蓋的相關(guān)關(guān)系。[定理6-3-2]

設(shè)圖G=(V,E)無孤立點(diǎn)，C

V，則：C為G的一個(gè)點(diǎn)覆蓋

V-C為G的一個(gè)獨(dú)立集。[推論1]

G如上所述，C

V，則：C為G的一個(gè)極小點(diǎn)覆蓋

V-C是G的一個(gè)極大獨(dú)立集。[推論2]

G如上所述，n=|V|，則

0

+

0=

n?！秷D論》4-8章習(xí)題課12.

匹配與邊覆蓋的相關(guān)關(guān)系。[定理8-1-1]

設(shè)M是G=(V,E)的一個(gè)匹配，n=|V|，且G中無孤立點(diǎn)：(1)設(shè)M為G的一個(gè)最大匹配，對(duì)G中每一個(gè)M不飽和頂點(diǎn)取一條關(guān)聯(lián)邊，組成邊集N，則W=M

N為G的一個(gè)最小邊覆蓋。(2)設(shè)W1為G的一個(gè)最小邊覆蓋，將W1中每相鄰的邊移去一條，設(shè)移去的邊構(gòu)成邊集N1，則M1=W1

N1為G的一個(gè)最大匹配。(3)

1(G)+

1(G)=n?！秷D論》4-8章習(xí)題課13.

Hall婚姻定理。[定理8-2-2]二部圖G=(X,Y,E)，|X|

|Y|，存在完全匹配的充要條件是：對(duì)任意A

X，有|

(A)|

|A|。

(A)為A在Y中的像：

(A)={y|yYx(xA(x,y)E)}。[推論]

設(shè)有二部圖G=(X,Y,E)，若對(duì)每個(gè)結(jié)點(diǎn)x

X，都有deg(x)

k；對(duì)每個(gè)結(jié)點(diǎn)yY，都有deg(y)

k，則G中存在從X到Y(jié)的完全匹配。

《圖論》4-8章習(xí)題課14.

匈牙利算法求二部圖的可增廣道：如圖，設(shè)初始匹配{(x2,y2),(x3,y3),(x5,y5)}，求其最大匹配?！秷D論》4-8章習(xí)題課x1x2x3x4x5y1y2y3y4y514.解：《圖論》4-8章習(xí)題課x1x2x3x4x5y1y2y3y4y5(1)U={x1}，V=。(U)={y2,y3} y2

(U)

V，且有標(biāo)記：(x2,y2)M。 U={x1,x2}，V={y2}。(U)={y2,y3,y1,y4,y5} y1

(U)

V，且未標(biāo)記，故存在從x1到y(tǒng)1的可增廣道。 找到一條可增廣道P=(x1,y2,x2,y1)。將x1、y1標(biāo)記I。 M={(x1,y2),(x2,y1),(x3,y3),(x5,y5)}。15.

流割定理。[定理8-5-1]

設(shè)網(wǎng)絡(luò)N中一個(gè)從z到z

的流f的流量為w,(S,S)為任意一個(gè)割切，則w=f(S,S)

f(S,S)[推論1]

對(duì)網(wǎng)絡(luò)N中任意流量w和割切(S,S)，有

w

c(S,S)。[推論2]

最大流量