请输入您要查询的百科知识:

 

词条 托兰定理
释义

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

如果一个n阶简单图,它不包括Kp,则其边数最大值为 (p-2)(n^2-r^2)/(2*(p-1))+r/2

其中r是n mod (p-1)

托兰定理的补形:

平面上N个点,任何三点存在一条直线,至少连NC2-[N^2/4]条线

托兰定理的证明:

设A为N个点中,向外连线最多的点,设它向外连k条线,则与A相连的点之间不允许连线

而剩余N-1-k中的任意一点不可能向外连线数大于k,设这些点连线总数为y,则有

y≤k(N-1-k)+k

y≤-k^2+Nk=-(k-N/2)^2+[N^2/4]

当k=N/2时,y是整数,所以y的最大值为N^2/4

所以y≤[N^2/4]

随便看

 

百科全书收录4421916条中文百科知识,基本涵盖了大多数领域的百科知识,是一部内容开放、自由的电子版百科全书。

 

Copyright © 2004-2023 Cnenc.net All Rights Reserved
更新时间:2024/12/24 20:13:36