组合数学第四版(RichardA.Brualdi)第11章的几道课后题(8、20、21).被采纳的一定追加分数.一共3道
来源:学生作业帮 编辑:灵鹊做题网作业帮 分类:数学作业 时间:2024/05/16 09:55:20
组合数学第四版(RichardA.Brualdi)第11章的几道课后题(8、20、21).被采纳的一定追加分数.一共3道题:
首先核对一下术语,题目里的"图"应该是指简单图,即每一对顶点间至多有一条边.
21题中的"一般图"才是一般意义上的图,允许多条边和起点终点重合的边.
8.将G的顶点分为两个子集:由前k个顶点组成的集合A,和后n-k个顶点组成的集合B.
在和式∑{1 ≤ i ≤ k} di中,A中顶点之间的边被计数两次,A中顶点与B中顶点之间的边被计数1次.
因此有不等式∑{1 ≤ i ≤ k} di ≤ 2·A内部的边数+A到B的边数,两部饭分别估计.
①因为G是简单图,A有k个顶点,故A内部的边数 ≤ C(k,2) = k(k-1)/2.
②A到B的边数 = ∑{k+1 ≤ i ≤ n} 第i个顶点到A的边数.
易见,第i个顶点到A的边数 ≤ di,且第i个顶点到A的边数 ≤ k.
故A到B的边数 ≤ ∑{k+1 ≤ i ≤ n} min{k,di}.
综合得∑{1 ≤ i ≤ k} di ≤ k(k-1)+∑{k+1 ≤ i ≤ n} min{k,di},即所求证.
20.用反证法,假设图不连通,则可将图分成两个子图的无交并.
设两个子图分别为k阶和n-k阶,1 ≤ k ≤ n-1.
作为简单图,二者的边数分别至多为C(k,2)和C(n-k,2).
因此原图边数 ≤ C(k,2)+C(n-k,2)
= (k²-k+(n-k)²-(n-k))/2
= (k²+(n-k)²-n)/2
= (n²+(n-2k)²-2n)/4
≤ (n²+(n-2)²-2n)/4 (1 ≤ k ≤ n-1)
= (n-1)(n-2)/2,
与至少有(n-1)(n-2)/2+1条边矛盾.
例子:一个n-1阶完全图恰有(n-1)(n-2)/2条边,添加一个孤立点即可.
21.基本事实:一个图中奇顶点的个数必为偶数.
设G中包含x的连通分支为H,由H包含奇顶点x,H至少还包含一个奇顶点.
但G中只有两个奇顶点x和y,故H包含y.
G中已存在x到y的路径,因此添加新边{x,y}不改变G的连通性.
即G连通当且仅当G*连通.
21题中的"一般图"才是一般意义上的图,允许多条边和起点终点重合的边.
8.将G的顶点分为两个子集:由前k个顶点组成的集合A,和后n-k个顶点组成的集合B.
在和式∑{1 ≤ i ≤ k} di中,A中顶点之间的边被计数两次,A中顶点与B中顶点之间的边被计数1次.
因此有不等式∑{1 ≤ i ≤ k} di ≤ 2·A内部的边数+A到B的边数,两部饭分别估计.
①因为G是简单图,A有k个顶点,故A内部的边数 ≤ C(k,2) = k(k-1)/2.
②A到B的边数 = ∑{k+1 ≤ i ≤ n} 第i个顶点到A的边数.
易见,第i个顶点到A的边数 ≤ di,且第i个顶点到A的边数 ≤ k.
故A到B的边数 ≤ ∑{k+1 ≤ i ≤ n} min{k,di}.
综合得∑{1 ≤ i ≤ k} di ≤ k(k-1)+∑{k+1 ≤ i ≤ n} min{k,di},即所求证.
20.用反证法,假设图不连通,则可将图分成两个子图的无交并.
设两个子图分别为k阶和n-k阶,1 ≤ k ≤ n-1.
作为简单图,二者的边数分别至多为C(k,2)和C(n-k,2).
因此原图边数 ≤ C(k,2)+C(n-k,2)
= (k²-k+(n-k)²-(n-k))/2
= (k²+(n-k)²-n)/2
= (n²+(n-2k)²-2n)/4
≤ (n²+(n-2)²-2n)/4 (1 ≤ k ≤ n-1)
= (n-1)(n-2)/2,
与至少有(n-1)(n-2)/2+1条边矛盾.
例子:一个n-1阶完全图恰有(n-1)(n-2)/2条边,添加一个孤立点即可.
21.基本事实:一个图中奇顶点的个数必为偶数.
设G中包含x的连通分支为H,由H包含奇顶点x,H至少还包含一个奇顶点.
但G中只有两个奇顶点x和y,故H包含y.
G中已存在x到y的路径,因此添加新边{x,y}不改变G的连通性.
即G连通当且仅当G*连通.
数学几道填空题,答好的采纳OK
几道数学填空题,好的追加50
如下几题(解出来的,追加分数30)
几道简单的汇编语言题求答案!我追加高的分数
语文课后要怎么写第3题.好的我会采纳
关于安全知识的几道选择题,请大家帮忙做一下.(答的好的追加分数)
初2数学北师大版第四章的复习题B组第2道怎么做?
第四章第3节硫和氮的氧化物课后习题答案,人教版
几道数学填空题 加急!回答正确的有追加分!
数学判断题2道分子相同的两个分数,分数单位大的分数一定比较大.( )两根一样长的铁丝,且都比l米长,第一根剪去 5分之1
求解初三数学复习题.【第1大题10分,第2大题20分.采纳时追加.保底10.[就算只回答1道也可以啊啊啊啊啊.]】图请自
第四版数学物理方法的课后题答案谢谢急用