早教吧作业答案频道 -->数学-->
求证一道图论题在几个点组成的图Gn中,若对某个2≤k≤n-2,任意k个点间的边数相同,则Gn是完全图.(提示上面说可以先征Gn是正则图,在证明它是完全图,
题目详情
求证一道图论题
在几个点组成的图Gn中,若对某个2≤k≤n-2,任意k个点间的边数相同,则Gn是完全图.
(提示上面说可以先征Gn是正则图,在证明它是完全图,
在几个点组成的图Gn中,若对某个2≤k≤n-2,任意k个点间的边数相同,则Gn是完全图.
(提示上面说可以先征Gn是正则图,在证明它是完全图,
▼优质解答
答案和解析
这个是图论中的Ramsey定理,题目的描述稍有问题,应该加上G是非零图的条件
1) 先证G是正则图
对于n个点,按照它们的度数从大到小排序,然后编号为v1、v2...vn,即满足d(v1)>=d(v2)>=...>=d(vn)
以下反证证明.如果G不是正则图,那就有d(v1)>d(vn)
对于V-{v1,vn}中的n-2个点,按照与v1、vn相连或者不相连,可以划分到以下4个集合中:
A:只与v1相连
B:与v1、vn都相连
C:只与vn相连
D:与v1、vn都不相连
因为d(v1)>d(vn),所以|A|>|C|
按照如下方法从V-{v1,vn}中挑选出k-1个点:
a) 优先从A中挑选
b) 如果从A中挑选不满,那么再从B∪D中挑选
c) 如果以上还挑选不满,最后从C中挑选
假设最后挑选出来的k-1个点落在A、B、C、D的子集分别为A'、B'、C'、D',根据以上方法,显然有|A'|>|C'|
考察以下两个k子集:
V1={v1}∪A'∪B'∪C'∪D'
V2={vn}∪A'∪B'∪C'∪D'
e(G[V1])-e(G[V2])=|A'|-|C'|>0,这与条件任意k个点的导出子图的边数相等相矛盾
因此d(v1)=d(vn),即G是正则图
2) 再证明对于任意的两个点,比如v1,vn,有|A|=|C|=0
1)的证明可以得到|A|=|C|
仍然通过反证证明.如果|A|=|C|>0,注意还有个条件:k-1e(G[V2]),与条件任意k个点的导出子图的边数相等相矛盾
所以|A|=|C|=0
3) 最后证G是完全图
还是通过反证证明.如果d(v1)0,所以存在v3,使得v3与v1相连但v3不与v2相连
这样v3就落在v1、v2的A集合里面,因此|A|>0,这与2)的结论相矛盾
所以d(v1)=n-1,即G是完全图
1) 先证G是正则图
对于n个点,按照它们的度数从大到小排序,然后编号为v1、v2...vn,即满足d(v1)>=d(v2)>=...>=d(vn)
以下反证证明.如果G不是正则图,那就有d(v1)>d(vn)
对于V-{v1,vn}中的n-2个点,按照与v1、vn相连或者不相连,可以划分到以下4个集合中:
A:只与v1相连
B:与v1、vn都相连
C:只与vn相连
D:与v1、vn都不相连
因为d(v1)>d(vn),所以|A|>|C|
按照如下方法从V-{v1,vn}中挑选出k-1个点:
a) 优先从A中挑选
b) 如果从A中挑选不满,那么再从B∪D中挑选
c) 如果以上还挑选不满,最后从C中挑选
假设最后挑选出来的k-1个点落在A、B、C、D的子集分别为A'、B'、C'、D',根据以上方法,显然有|A'|>|C'|
考察以下两个k子集:
V1={v1}∪A'∪B'∪C'∪D'
V2={vn}∪A'∪B'∪C'∪D'
e(G[V1])-e(G[V2])=|A'|-|C'|>0,这与条件任意k个点的导出子图的边数相等相矛盾
因此d(v1)=d(vn),即G是正则图
2) 再证明对于任意的两个点,比如v1,vn,有|A|=|C|=0
1)的证明可以得到|A|=|C|
仍然通过反证证明.如果|A|=|C|>0,注意还有个条件:k-1e(G[V2]),与条件任意k个点的导出子图的边数相等相矛盾
所以|A|=|C|=0
3) 最后证G是完全图
还是通过反证证明.如果d(v1)0,所以存在v3,使得v3与v1相连但v3不与v2相连
这样v3就落在v1、v2的A集合里面,因此|A|>0,这与2)的结论相矛盾
所以d(v1)=n-1,即G是完全图
看了 求证一道图论题在几个点组成的...的网友还看了以下:
不要建立直角坐标系,要用向量的方法做.1,已知正方体ABCD-A1B1C1D1,点E是上底面A1C 2020-05-13 …
已知一次函数y=x+2与反比例函数y=kx,其中一次函数y=x+2的图象经过点P(k,5).(1) 2020-05-22 …
1.微绒毛与纤毛的相同点与不同点.2.肾上腺皮质的组织结构和各部分所分泌激素的名称 2020-06-13 …
关于口袋妖怪白天亲密进化的精灵1:白天是指几点到几点?2:是指只累积白天得到的亲密度吗?(夜晚关于 2020-06-22 …
如图,四边形ABCD是梯形,点E是上底边AD上一点,CE的延长线与BA的延长线交于点F,过点E作B 2020-06-23 …
已知正方体,点E是上底面AC的中心,若向量AE=AA'+xAB+yAD已知正方体,点E是上底面AC 2020-06-27 …
已知正方体,点E是上底面A'C'的中心,若向量AE=AA'+xAB+yA已知正方体,点E是上底面A 2020-06-27 …
如图,已知正方体ABCD-A1B1C1D1的棱长为4,点E,F分别是线段AB,C1D1上的动点,点 2020-06-27 …
高等数学:设函数f(x)和g(x)在(-无穷,+无穷)内有定义,f(x)为连续函数,且f(x)≠0 2020-07-21 …
(本小题满分12分)如图所示,在直三棱柱中,、、分别是、、的中点,是上的点.(1)求直线与平面所成 2020-07-30 …