8楼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点有线段相连的情况.
