旺旺网 - Powered by Discuz! Board

标题: [数学] 2008-5-3 [打印本页]

作者: 老猫 时间: 2008-5-3 07:34 标题: 2008-5-3

平面上有七个点，它们之间可以连一些线段，使得7个点中的任意三点中必存在2点有线段相连。问至少要连多少条线段？请证明你的结论。.

作者: xyq2100 时间: 2008-5-5 11:02

一般情况下n=2k+1 至少要连k^2条线段将n个点分成两组k和k+1，两组内的点两两互连
n=2k 至少要连k(k-1)条线段，同上
这里7=2*3+1 至少要连3^2=9条线段。有空我补充这个证明.

作者: 老猫 时间: 2008-5-5 14:16

这个证明是不是图兰定理？
我始终证的不象样。.

作者: zhenai 时间: 2008-5-5 17:00

7个点很容易证明，n个点也不是太复杂。.

作者: zhenai 时间: 2008-5-6 10:41

1）n=2k
设将n个点分为k+a和k-a两组
((k+a)(k+a-1)+(k-a)(k-a-1)) / 2
= k^2 - k + a^2
当a=0时最小值为k(k-1)

2) n=2k+1
设将n个点分为k+a和k+1-a两组
((k+a)(k+a-1)+(k+1-a)(k-a)) / 2
= k^2 + a(a-1)
当a=0或1时最小值为k^2.

作者: 老猫 时间: 2008-5-6 11:20

为什么是分两组呢？.

作者: zhenai 时间: 2008-5-6 12:54

首先分3组肯定不行，否则3组中个取一点，则这3点没有连线。
其次分两组，且两组一定都是全连通的图，否则也能找到3点没有连线。
最后全在1组的话一定比2个不连通的全连通图的连线多。.

作者: xyq2100 时间: 2008-5-7 11:19

最后全在1组的话一定比2个不连通的全连通图的连线多这句话有问题，这种情况没有说清楚。因为全在1组的话并不需要全连通，n个点的连通图最少只需要n-1条连线即可，所以全在1组的话一定比2个不连通的全连通图的连线需要合适的理由。

结论：n个点至少要连[n/2]*[(n-1)/2]条线段，[ ]表示取整
我写一个证明：设n个点中跟其他点连线最少的一个点为O，连线数为m，如果m>[(n-1)/2]，
那么总的连线数>[(n-1)/2]*n>=[n/2]*[(n-1)/2]，因此m<=[(n-1)/2]，
设O和O相连的点的集合为A(点数为m+1)，与O不相连的点的集合为B(点数为n-m-1)，
那么B中的点必两两相连，而且由于A中的点的连线数最少为m，
所以总的连线数>=((m+1)m+(n-m-1)(n-m-2))/2>=[n/2]*[(n-1)/2]，等号当且仅当m=[(n-1)/2]时成立。

其实这个方法也可以推广到任意k(k>=3)点中必存在2点有线段相连的情况.

欢迎光临旺旺网 (http://ww123.net/)