求证一道图论题在几个点组成的图Gn中,若对某个2≤k≤n-2,任意k个点间的边数相同,则Gn是完全图.(提示上面说可以先
来源:学生作业帮 编辑:百度作业网作业帮 分类:数学作业 时间:2024/08/08 19:11:05
求证一道图论题
在几个点组成的图Gn中,若对某个2≤k≤n-2,任意k个点间的边数相同,则Gn是完全图.
(提示上面说可以先征Gn是正则图,在证明它是完全图,
在几个点组成的图Gn中,若对某个2≤k≤n-2,任意k个点间的边数相同,则Gn是完全图.
(提示上面说可以先征Gn是正则图,在证明它是完全图,
![求证一道图论题在几个点组成的图Gn中,若对某个2≤k≤n-2,任意k个点间的边数相同,则Gn是完全图.(提示上面说可以先](/uploads/image/z/19421705-65-5.jpg?t=%E6%B1%82%E8%AF%81%E4%B8%80%E9%81%93%E5%9B%BE%E8%AE%BA%E9%A2%98%E5%9C%A8%E5%87%A0%E4%B8%AA%E7%82%B9%E7%BB%84%E6%88%90%E7%9A%84%E5%9B%BEGn%E4%B8%AD%2C%E8%8B%A5%E5%AF%B9%E6%9F%90%E4%B8%AA2%E2%89%A4k%E2%89%A4n-2%2C%E4%BB%BB%E6%84%8Fk%E4%B8%AA%E7%82%B9%E9%97%B4%E7%9A%84%E8%BE%B9%E6%95%B0%E7%9B%B8%E5%90%8C%2C%E5%88%99Gn%E6%98%AF%E5%AE%8C%E5%85%A8%E5%9B%BE.%EF%BC%88%E6%8F%90%E7%A4%BA%E4%B8%8A%E9%9D%A2%E8%AF%B4%E5%8F%AF%E4%BB%A5%E5%85%88)
这个是图论中的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是完全图
电子称中GN的意思
牛顿单位GN换算我想问的是1GN=多少牛,比如1kN=10^3 N
高达00中Arios的GN Drive
若对任意整数n,满足(n+11)^2-n^2的值总可以被k整除 则k=_____.
若n为任意整数,(n+11)^2-n^2的值总可以被k整除,则k等于?
如图,正五边形ABCDEF与正五边形ACMHG共点于A,连接BG、CF,则线段BG、CF具有什么样的数量关系并求出∠GN
求和证明不等式求证∑k=2(1/k-ln1/k)>(n-1)/2(n+1).其中k=5是在∑下面,上面是n
数列{an}中,an=n^2-kn,若对任意的正整数n,an≥a3都成立,则k的取值范围是
如图,任意五边形ABCDE中,M,N,P,Q分别为AB,CD,BC,DE的中点,K,L,分别为MN,PQ的中点,求证:K
若n为任意数,(n+11)-n的值总可以被k整除,求k的最大值.
若n为任意实数,(n+11)^2-n^2-n^2的值总可以被k整除,则k等于?
已知k∈N,求证:k²+k²(k+1)²+(k+1)是一个完全平方数