托兰定理,有人知道吗?

来源:百度知道 编辑:UC知道 时间:2024/05/27 13:03:45
请告诉我这个定理的内容。谢了

托兰定理就是平面上N个点,至少连【N^2/4】+1条线段必定存在三角形

对于平面含有n个点的点集,在这些点之间两两连线,但不构成三角形,至多能连[n^2/4]条线,[]表示取整

证明如下
先找到所有点中连出线段最多的那个点,记为A
将剩下的点分为了两个集合B和C
B中的点于A点连边
C中的点于A点不连边

设B中有K个元素,C中有n-k-1个元素

对于B中的任意点,两两之间不能连线(若否,则与A构成三角形),它们之中的每个元素至多连出n-k条边

对于C中的任意点,它们至多连k条边(k的最大性)

总边数的两倍>=k+k(n-k)+(n-k-1)*k=2k(n-k)

后面容易可以得到结论

我知射影定律