第10章习题答案

第10章 图

于是G中共含1+r1+r2+?+rs=1+r=

k条边不重合的简单通路,它们含G中的全部边。 241.甲、乙、丙、丁四位教师,分配他们教数学、物理,电工和计算机原理四门课。甲能教物理和电工,乙能教数学和计算机原理,丙能教数学、物理和电工,丁只能教电工,对他们的工作怎样分配?

解 设.甲、乙、丙、丁四位教师分别用v1、v2、v3、v4表示,V1={v1,v2,v3,v4},数学、物理,电工和计算机原理四门课分别用u1、u2、u3、u4表示,V2={u1,u2,u3,u4}。若vi能教uj,令∈E。所作图G=,则G为二部图,如下图所示。易证满足“相异性条件”,且|V1|=|V2|,所以,存在V1到V2的完全匹配。图中粗线所示就是其一种分配方案。

v1v2v3v4u1u2u3u442.某杂志发表了7个征求答案的题目,当从读者寄来的解答中挑选每题的两个解答时,编者发现所有14个选出来的解答恰好是7个读者提出来的,而且每个人正好提出了两个答案。试证明:编辑可以这样发表每道题的一个解答,使得在发表的解答中,这7个读者每个人都恰有一个解答。

解 7个位读者分别用v1、v2、?、v7表示,V1={v1,v2,?,v7},7个题目分别用u1、u2、?、

u7表示V2={u1,u2,?,u7}。若vi为uj做解答,令∈E。所作图G=,则G为

二部图。由已知条件可知V1中每个结点关联两条边,中每个结点也关联两条边,即G满足t=2的“t条件”,所以存在V1到V2的完备匹配,又因为|V1|=|V2|,因而对于任意的V1到V2的完备匹配M,不存在M-非饱和点,故M也是完全匹配。即使得7个题目的7个解答分别由7个读者给出是办得到的。

43.给定二部图G=,且|V1∪V2|=m,|E|=n,证明n≤m/4。

2证明 设|V1|=m1,则|V2|=m-m1,于是n≤m1(m-m1)=m1m-m1。因为(?m1)2?0,即

2

m2m222,所以n≤m/4。 ?mm1?m1444.设G是面数r小于12的简单平面图,G中每个结点的度数至少为3。 (1)证明G中存在至多由4条边围成的面。

(2)给出一个例子说明,若G中的面数为12,且每个结点的度至少为3,则(1)的结论不成立。 证明 1)不妨设G是连通的,否则可以对它的每个连通分支进行讨论(因为每个连通分支均满足条件)。因而由偶拉公式有

n-m+r=2, (1)

又由已知条件得r<12且n≤m, (2)

23 13

第10章 图

将(2)其代入(1)得2<m-m+12,m<30。 (3) 若所有的面均至少由5条边围成,则

5r≤2m,r≤m, (4) 将(2)、(4)代入(1)得

2≤m-m+m,m≥30。 (5) (3)与(5)是矛盾的,因而必存在至多由4条边围成的面。

2)十二面体图有12个面,每个结点均为3度,每个面由5条边围成,并没有4条边围成的面。 45.把平面分成?个区域,每两个区域都相邻,问?最大为几?

解 在每个区域放一个结点,当两区域相邻时就在相应的两个结点之间连一条线,如此构造了一个平面图且是完全图K?,而最大的平面完全图为K4,所以?最大为4。

46.设简单平面图G中结点数n=7,边数m=15,证明G是连通的。

证明 反证法。设G为非连通的,具有k≥2个连通分支G1,G2,?,Gk。设Gi的结点数为ni,边数为

mi,i=1,2,?,k23252325。

若存在nj=1,则k必为2,因为只有此时G为一个平凡图并上一个K6才能使其边数为15,可是K6不是平凡图,这矛盾于G为平面图这个事实,所以不存在nj=1。

若存在nj=2,Gj中至少有一条边(因为G为简单图),另外5个结点构成K5时边数最多,但充其量为10条边,这与G有15条边矛盾。

综上所述,ni必大于等于3,i=1,2,?,k。由定理10.37可知,mi≤3(ni-2)=3ni-6,i=1,2,?,k。求和得

m≤3n-6k (1)

将n=7,m=15代入(1)得15≤21-6k,于是k≤1,这与k≥2矛盾。 至此证明了G必为连通图。

47.设G是边数m小于30的简单平面图,试证明G中存在结点v使得d(v)≤4。

解 不妨设G是连通的,否则因为它的每个连通分支的边数都应小于30,因此可对它的每个连通分支进行讨论,所以可设G是连通的。

若G中无回路,则G必为树,结论显然成立。若G中有回路,由于G为简单图,因而G中每个面至少由3个边围成,由定理10.37有m≤3n-6。

下面用反证法证明结论。若不然,G中所有结点的度数均大于等于5,由握手定理可知2m=

2525?d(v)kk?1n≥5n,所以n≤m,将其代入m≤3n-6得m≤3×m-6,于是m≥30,与m<30矛盾,所以一定存在结点v使得d(v)≤4。

14

第10章 图

48.设G为有k(k≥2)个连通分支的平面图,G的平面图的每个面至少由f(f≥3)条边围成,则m≤

f(n-k-1)。 f?2解 设G的各面的边界长度之和为T。G的每条边在计算T时,均提供2,又因为G的平面图G? 的每个面至少由f条边围成,所以fr≤T=2m。又因为r=k+1+m-n,将其代入fr≤2m得f(k+1+m-n)≤2m,整理得m≤

f(n-k-1)。 f?2*

49.证明:平面图G的对偶图G是欧拉图?G中每个面的次数均为偶数。

证明 显然G是连通图,设v*为G*的任一结点,v*位于G的面R中,由于R由偶数边围成,所以d(v*)为偶数,由v*的任意性可知,G是欧拉图。

50.在由6个结点,12条边构成的连通平面图G中,每个面由几条边围成?为什么?

解 每个面由3条边围成。因图中结点数和边数分别为n=6,m=12。根据欧拉公式n-m+r=2得r=8。

又因为围成。

51.给定连通简单平面图G=,且|V|=6,|E|=12。证明:对任意f∈F,d(f)=3。 证明 由偶拉公式得|V|-|E|+|F|=2,所以|F|=2-|V|+|E|=8,又由定理10.31得?d(f)=

f?F*

*

?d(v)=2m=24,而简单连通平面图的每个面至少由3条边围成,所以G中每个面由3条边

i2|E|=24。若存在f∈F,使得d(f)>3,则3|F|<2|E|=24,于是|F|<8,与|F|=8矛盾。故对任意f∈F,d(f)=3。

52.证明:不存在具有5个面,每两个面都共享一条公共边的平面图G。

证明 若存在这样的平面图G,设G的对偶图为G*,则G*也是平面图。由于G有5个面,所以G*具有5个结点。设v*为G*的任一结点,设它位于G的面R中。由于R与其余4个面均有公共边,所以v*与其余面中的结点均相邻,于是d(v*)=4,而且G*为简单图,所以G*必为K5,可是K5为非平面图,这与G*为平面图矛盾。

53.已知一棵无向树T有三个3度结点,一个2度结点,其余的都是1度结点。 (1)T中有几个1度结点?

(2)试画出两棵满足上述度数要求的非同构的无向树。

解 (1)设T中有x个1度结点,则T中结点数n=3+1+x,T中边数m=3+1+x-1=3+x。T中各结点度数之和

?d(v)=3×3+2×1+1×x=11+x。由握手定理得11+x=2m=6+2x,于是x=5。所

ii?1n以T中有5个1度结点。

(2)下图中所示的两棵树均满足要求,但它们是不同构的。

15

第10章 图

54.一棵无向树T有ni个度数为i的结点,i=2,3,?,k,问有多少个1度结点? 解 设T中有x个1度结点,则T中结点数n=

nkk

?n+x,T中边数m=?n+x-1。T中各结点度

iii?2i?2kk数之和

k

?d(v)=?i*n+1×x=?i*n+x。由握手定理得

iii

i?1i?2i?2

kkiii?2i?32(

?ni?2ki+x-1)=

?i*n+x,于是

i

i?2

k

x=

?i*n-2?n+2=?(i?2)*n+2。

i

i?2

所以T中有

?(i?2)*n+2个1度结点。

ii?3k55.证明恰有两个结点的度数为1的树必为一条通路。

证明 设T为一棵具有两个1度结点的树(n,m),则m=n-1且有

n?d(v)=2m=2(n-1)。又T

ii?1n?2i?1in连通且除两个1度结点外,其他结点度数均大于等于2,而

n?2i?1n?2i?1?d(v)=2+?d(v),有

ii?12(n-1)=2+

?d(v),故?d(v)=2(n-1)。因此n-2个分支结点的度数都恰为2,即T为一条通路。

ii56.设无向图G是由k(k≥2)棵树构成的森林,至少在G中添加多少条边才能使G成为一棵树? 解 设G的k个连通分支为T1、T2、?、Tk,设结点vi∈Ti,i=1,2,?,k。在G中添加边(vi,vi?1),i=1,2,?,k,设所得图为T,则T连通且无回路,因而T是树。所以边的添加数k-1是使得G为树的最小数目。

57.试画出4个结点和5个结点的所有非同构的无向树。

解 4个结点的所有非同构的无向树有2棵,如图(1)和(2)所示。5个结点的所有非同构的无向树有3棵,如图(3)、(4)和(5)所示。

(1)

(2)(3)16

(4)(5)

联系客服:779662525#qq.com(#替换为@)