离散作业答案2016ex

作业119.479.4910.510.810.1010.15

2

9.47证明小于30条边的连通简单平面图至少有一个顶点的度数小于或等于4。证明方法一：用反证法。设平面图简单图有n个顶点，m条边。 假设所有顶点度数5,则有5n2m。 又因为m3n-6, 故

m+63n， 从而，有5(m+6)15n3(2m),即30m。 这与题意中m<30矛盾。定理2任何一个简单的连通平面图G=(V,E)，|V|=n，|E|=m，则有m≤3n－6∑d(v)=2|E|3

9.47证明小于30条边的连通简单平面图至少有一个顶点的度数小于或等于4。证明方法二： 用反证法。设平面图简单图有n个顶点，m条边。 假设所有顶点次数5,则有5n2m。 而m<30，故n<12。又因为m3n-6,故

5n2m2(3n-6)=6n-12， 即n12。矛盾。

故说明有一个顶点的次数小于等于4。∑d(v)=2|E|定理2任何一个简单的连通平面图G=(V,E)，|V|=n，|E|=m，则有m≤3n－64

9.49证明具有6个顶点12条边的连通平面简单图，它的每一个面都是由3条边组成。证明：由题意，有n=6 m=12。 由欧拉公式n-m+r=2,得

6-12+r=2,

故 r=8。用反证法。若有区域是用>3条边围成的，则有

2m>3r,

即2m>24， 故

m>12

矛盾！这说明每个区域都是用3条边围成。定理3m≤2n－4欧拉公式：n－m+r=2

10.5证明：一棵树若有三片树叶，则至少有一个顶点度数大于等于3。证明：反证法。 设没有一个顶点度数大于等于3，则 d(v)3+2(|V|-3) =2|V|-3

2|V|-2=2(|V|-1)=2|E|。 这与握手定理矛盾。故至少有一个顶点度数大于等于3∑d(v)=2|E|

10.5证明：一棵树若有三片树叶，则至少有一个顶点度数大于等于3。另证：反证法。 设没有一个顶点度数大于等于3，则 2|E|=d(v)3+2(|V|-3) =2|V|-3

2|V|-2=2(|V|-1)=2|E|。 矛盾。故至少有一个顶点度数大于等于37

10.8证明：（1）一棵树又是二部图(偶图)。

证明：（1）因为T是一棵树，所以T中没有回路，也可以说T中回路的长度都为0（0为偶数），这样根据二部图的等价定义（即所有回路长度均为偶数），知：T是二部图。另证：（1）T=(V,E)

对于任意一个顶点v0，令

V1={v|从v0走奇数步可以到达点v}V2={v|从v0走偶数步可以到达点v}

显然，(V1,V2)是树T的顶点的二分类

T是二部图。8

10.8证明：（2）T=(V,E)，V1,V2是作为二部图的顶点分类，|V1|≥|V2|,则V1中至少有一片树叶。证明：（2）假设V1中没有树叶，则V1中每个顶点的度数至少为2,

于是

|E|≥2|V1|

即|V1|+|V2|-1≥

2|V1|

故得:|V2|≥

|V1|+1

这与已知条件矛盾。矛盾说明假设错误,V1中至少有一片树叶。9

10.8证明：（2）T=(V,E)，V1,V2是作为二部图的顶点分类，|V1|≥|V2|,则V1中至少有一片树叶。证明：（2）设V1中没有树叶，则V1中每个顶点的度数至少为2 2|E|≥2|V1|+2|V1|≥

2|V1|+2|V2|=

2(|V1|+|V2|-1)+2 =2(|V|-1)+2=2|E|+2

矛盾,假设错误。故V1中至少有一片树叶。10

10.10求下面图的最小生成树。最小生成树的权为2+3+3+3+3+4+4+5+5=32解:11

10.15证明一棵正则2－分树必有奇数个顶点。证明:假设一棵正则2－分树有i个分枝点，每个分枝点有2个儿子，故总的儿子数目为2i。而所有的儿子包括全部顶点减去一个根，即为分枝点数目i与树叶数目t之和,再减去1，所以有：

2i=i+t-1

即为

i=t-1。 从而全部顶点数目为

i+t=(t-1)+t=2t-1

显然,它是一个奇数，结论得证明。树叶数目的2倍减1