发布时间 : 星期四 文章第10章习题答案更新完毕开始阅读cc1b2b659b6648d7c1c746c9
第10章 图
u4}。若vi能教uj,令
异性条件”,且|V1|=|V2|,所以,存在V1到V2的完全匹配。图中粗线所示就是其一种分配方案。
42.某杂志发表了7个征求答案的题目,当从读者寄来的解答中挑选每题的两个解答时,编者发现所有14个选出来的解答恰好是7个读者提出来的,而且每个人正好提出了两个答案。试证明:编辑可以这样发表每道题的一个解答,使得在发表的解答中,这7个读者每个人都恰有一个解答。
解 7个位读者分别用v1、v2、?、v7表示,V1={v1,v2,?,v7},7个题目分别用u1、u2、?、u7表示V2={u1,u2,?,u7}。若vi为uj做解答,令
43.给定二部图G=
m2?m1)2?0,即
4?mm1?m12,所以n≤m/4。
2
44.设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)
32将(2)其代入(1)得2<m-m+12,m<30。 (3)
32若所有的面均至少由5条边围成,则
5r≤2m,r≤m, (4)
52将(2)、(4)代入(1)得
2≤m-m+m,m≥30。 (5)
3522 13
第10章 图
(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,?,k。
若存在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。
n下面用反证法证明结论。若不然,G中所有结点的度数均大于等于5,由握手定理可知2m=?k?1d(vk)≥
5n,所以n≤m,将其代入m≤3n-6得m≤3×m-6,于是m≥30,与m<30矛盾,所以一定存在结
5522点v使得d(v)≤4。
48.设G为有k(k≥2)个连通分支的平面图,G的平面图的每个面至少由f(f≥3)条边围成,则m≤
ff?2(n-k-1)。
解 设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≤
ff?2(n-k-1)。
14
第10章 图
49.证明:平面图G的对偶图G*是欧拉图?G中每个面的次数均为偶数。
*证明 显然G*是连通图,设v*为G*的任一结点,由于R由偶数边围成,所以d(v*)v位于G的面R中,
为偶数,由v*的任意性可知,G*是欧拉图。
50.在由6个结点,12条边构成的连通平面图G中,每个面由几条边围成?为什么?
解 每个面由3条边围成。因图中结点数和边数分别为n=6,m=12。根据欧拉公式n-m+r=2得r=8。
又因为?d(vi)=2m=24,而简单连通平面图的每个面至少由3条边围成,所以G中每个面由3条边围成。
51.给定连通简单平面图G=
f?F2|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(vi)=3×3+2×1+1×x=11+x。由握手定理得11+x=2m=6+2x,于是x=5。所以T
i?1n中有5个1度结点。
(2)下图中所示的两棵树均满足要求,但它们是不同构的。
54.一棵无向树T有ni个度数为i的结点,i=2,3,?,k,问有多少个1度结点?
15
第10章 图
kk解 设T中有x个1度结点,则T中结点数n=?ni+x,T中边数m=?ni+x-1。T中各结点度数
i?2nkkki?2kk之和?d(vi)=?i*ni+1×x=?i*ni+x。由握手定理得2(?ni+x-1)=?i*ni+x,于是x=?i*ni-
i?1kki?2i?2i?2i?2i?22?ni+2=?(i?2)*ni+2。
i?2i?3k所以T中有?(i?2)*ni+2个1度结点。
i?355.证明恰有两个结点的度数为1的树必为一条通路。
证明 设T为一棵具有两个1度结点的树(n,m),则m=n-1且有?d(vi)=2m=2(n-1)。又T
i?1nn?2n?2n连通且除两个1度结点外,其他结点度数均大于等于2,而?d(vi)=2+?d(vi),有2(n-1)=2+?d(vi),
i?1n?2i?1i?1故?d(vi)=2(n-1)。因此n-2个分支结点的度数都恰为2,即T为一条通路。
i?156.设无向图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)所示。
58.设G=
(1)(2)(3)(4)(5)是连通图且e∈E,试证
明:e是G的割边?e包含在G的每棵生成树中。
证明 ?设e包含在G的每棵生成树中,但e不是G的割边。在图G中删去e得图G?,G? 仍是连通图。对G来说必有一棵生成树T,T中不包含边e,与假设矛盾。
?设边e不是G的割边,删去e,G就分成两个互不连通的子图G1和G2。对于G的任一一棵生成树T,由于T是连通图,故连结G1和G2之间的唯一边e必在T中。
59.如何由有向图G的邻接矩阵A判定G是否是根树,若是根树,如何定出它的树根和树叶。 解 一个有向图G为根树,它的邻接矩阵A必须满足:1)所有主对角元素为0;2)矩阵中有一列元
16