《图论》5-8章-习题课

1.

平面图G的对偶G*同构于G时，称G为自对偶图。证明：G=(V,E)为自对偶图时，有m=2n

2。这里n=|V|，m=|E|。《图论》4-8章习题课1.平面图G的对偶G*同构于G时，称G为自对偶图。证明：G=(V,E)为自对偶图时，有m=2n

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

m+d=2 对偶性：d=n* 同构性：n*=n

联立解得。《图论》4-8章习题课2.证明：Perterson图不是平面图。《图论》4-8章习题课2.证明：Perterson图不是平面图。《图论》4-8章习题课证一：反证。设其为平面图，则n

m+d=2。每个面至少有5条边，则2m

5d，或d

2/5m。故n

m+2/5m

2，即m

5/3(n

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

5/3

8，矛盾。《图论》4-8章习题课2.证明：Perterson图不是平面图。证二：反证。设其为平面图。由图示，每个面至少有5条边，即l=5，代入： 得： 3m

5(n2) 将n=10,m=15代入得4540，矛盾。3.设G是边数m小于30的简单平面图，证明G中存在节点v，deg(v)

4。《图论》4-8章习题课3.设G是边数m小于30的简单平面图，证明G中存在节点v，deg(v)

4。证明：不妨设G是连通的。若G是一棵树，结论显然成立。设G中有回路。反证：若G中所有结点的度均大于等于5，则2m

5n。联立m

3n

6得m

30，矛盾。《图论》4-8章习题课4.设简单平面图G中结点数n=7，边数m=15。证明G是连通的。《图论》4-8章习题课4.设简单平面图G中结点数n=7，边数m=15。证明G是连通的。证明：反证。设G不连通，有k个连通分支G1,G2,…,Gk，Gi对应结点数和边数分别为ni和mi。不存在1阶的连通分支，否则G只能由平凡图加上K6才能构成m=15，而K6是不可平面的。也不存在2阶的连通分支K2，否则G最多由K2加上K5也只能构成m=10<15。因此任意连通分支的阶必大于等于3。由mi

3ni

6，对全部连通分支求和得m

3n

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

1。《图论》4-8章习题课5.

将平面分成x个区域，且使得任意两个区域都相邻，问x最大是多少？《图论》4-8章习题课5.

将平面分成x个区域，且使得任意两个区域都相邻，问x最大是多少？证明：上述分法得到平面图G，设其对偶为G*。可知G*的任意两个顶点都邻接，即G*是一个完全图。又G*是一个平面图，故最多G*为K4。即x的最大值是4。《图论》4-8章习题课6.

设G是连通的平面图，证明：G为二部图当且仅当G的对偶图为欧拉图。《图论》4-8章习题课6.

设G是连通的平面图，证明：G为二部图当且仅当G的对偶图为欧拉图。证明：设G的对偶为G*，则G*是连通的。必要性：G为二部图，则G中无奇数长度回路，故G*中无奇数度顶点，因此G*是一个欧拉图。充分性：G*是一个欧拉图，则G*中无奇数度顶点，故G中无奇数长度回路，因此G为一个二部图。《图论》4-8章习题课7.

证明：k色图G中至少有k(k

1)/2条边。《图论》4-8章习题课7.

证明：k色图G中至少有k(k

1)/2条边。证明：按G的一个k正常着色方案划分G的顶点为k个集合V1,V2,…,Vk。则任给i,j，i

j，在Vi和Vj之间必有边相连，否则给Vi和Vj的顶点染上相同颜色，可以得到G的一个k

1正常着色方案，与G的色数是k矛盾。将Vi用一个结点ui取代，得到一个k阶完全图，其边数恰为k(k

1)/2。《图论》4-8章习题课8.

色数的图解求法：如图，求其色数(G)。

《图论》4-8章习题课《图论》4-8章习题课 (G)=min{(K5),(K4),(K3)}=(K3)=3K5K4K4K39-1.色数多项式的图解求法：加边法。如图，求其色数多项式。《图论》4-8章习题课《图论》4-8章习题课 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.

色数多项式的图解求法：减边法。如图，求其色数多项式。《图论》4-8章习题课《图论》4-8章习题课 PG(k)

=k4

3k3+3k2

k10.

如图是一份PCB板设计图，孔位x1~x9,y1~y3已经确定，联结边（导通）e1~e9。问至少要分成几层板才能实现。《图论》4-8章习题课x1x2x3x4x5y1y2y3x6x7x8x9e1e2e3e4e5e6e7e8e910.解：PCB要求将设计图P中发生交叉的边分配到不同的层面。若将同层的边染以相同颜色，问题转化为求最少颜色数。构造图G如下：以顶点vi标示图P的边ei，G的两个顶点vi,vj邻接当且仅当P中的两条边ei,ej。《图论》4-8章习题课v1v2v3v4v5v6v7v8v910.易得G的色数为3，即至少需要3层板。给出G的一种染色方案，相应可以得到P的一种铺板方案。《图论》4-8章习题课v1v2v3v4v5v6v7v8v910.

P的一种3层铺板方案。《图论》4-8章习题课x1x2x3x4x5y1y2y3x6x7x8x9e1e2e5e7e9x1x2x3x4x5y1y2y3x6x7x8x9e3e4e8x1x2x3x4x5y1y2y3x6x7x8x9e611.

点独立集与点覆盖的相关关系。[定理6-3-2]

设图G=(V,E)无孤立点，C

V，则：C为G的一个点覆盖

V-C为G的一个独立集。[推论1]

G如上所述，C

V，则：C为G的一个极小点覆盖

V-C是G的一个极大独立集。[推论2]

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

0

+

0=

n。《图论》4-8章习题课12.

匹配与边覆盖的相关关系。[定理8-1-1]

设M是G=(V,E)的一个匹配，n=|V|，且G中无孤立点：(1)设M为G的一个最大匹配，对G中每一个M不饱和顶点取一条关联边，组成边集N，则W=M

N为G的一个最小边覆盖。(2)设W1为G的一个最小边覆盖，将W1中每相邻的边移去一条，设移去的边构成边集N1，则M1=W1

N1为G的一个最大匹配。(3)

1(G)+

1(G)=n。《图论》4-8章习题课13.

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

|Y|，存在完全匹配的充要条件是：对任意A

X，有|

(A)|

|A|。

(A)为A在Y中的像：

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

设有二部图G=(X,Y,E)，若对每个结点x

X，都有deg(x)

k；对每个结点yY，都有deg(y)

k，则G中存在从X到Y的完全匹配。

《图论》4-8章习题课14.

匈牙利算法求二部图的可增广道：如图，设初始匹配{(x2,y2),(x3,y3),(x5,y5)}，求其最大匹配。《图论》4-8章习题课x1x2x3x4x5y1y2y3y4y514.解：《图论》4-8章习题课x1x2x3x4x5y1y2y3y4y5(1)U={x1}，V=。(U)={y2,y3} y2

(U)

V，且有标记：(x2,y2)M。 U={x1,x2}，V={y2}。(U)={y2,y3,y1,y4,y5} y1

(U)

V，且未标记，故存在从x1到y1的可增广道。 找到一条可增广道P=(x1,y2,x2,y1)。将x1、y1标记I。 M={(x1,y2),(x2,y1),(x3,y3),(x5,y5)}。15.

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

设网络N中一个从z到z

的流f的流量为w,(S,S)为任意一个割切，则w=f(S,S)

f(S,S)[推论1]

对网络N中任意流量w和割切(S,S)，有

w

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

最大流量