回复:你好,好久不见了
我在脑坛找你好几年了,不料你在这儿。这回我可找到组织了!
想不到叱诧风云的康大帝竟然是MM!你真的是MM?我五体投地!
以下是我的证明,请指正。
1. 存在4个点,互为好点:(0,0.6),(0,-0.6),(0.6,0),(-0.6,0)。在每个点附近取25个点,则每个点和75个点互为好点,所以共有75×50对好点。
2. 不存在5个点互为好点。
3. 将好点连线,得一图。由2,此图不含5阶完全图。顶点数固定而不含5阶完全图的图中,最大边数一定可以由4分图实现。
4. 顶点数为100的4分图最大边数为75×50。4分图是指所有顶点可分为4组,每组之内没有连线。4分图不含5阶完全图。
2的证明:若三个点互为好点,则其中任一个不可位于由另两个点所框定的矩形(含边界)内。可证平面上任5点内必有一点位于另两点框定的矩形内--给定5个点,考虑最小的包含所有5点的四边平行于x轴和y轴的矩形,称之为大矩形。这5点中必有若干点在此矩形边上,在这些点中一定可以找出2至4个点,使得每条边(含端点)上都有点。在这些选取出的点中,每两点框定一个小矩形。易证这些小矩形覆盖大矩形。5点中至少有1点不在这些选取的点中,而它在大矩形中,故必在某小矩形中。
3的证明:称不含n阶完全图的图为n-无关图。没有边的图即为2-无关图,亦称无关图。先证3-无关图的最大边数可由2分图实现。给定一个3-无关图。假设A是其最大(点数最多的,下同)无关子图,设A有n个点。在余下的点构成的子图A'中选取其最大无关子图B,设B有m个点。A中每点至A'最多有m条边,所以A和A'之间的边最多有m×n条,可将其改为A和B之间的所有边。这样得到的新图总边数只增不减,且仍是3-无关图。若A'比B大,新图将有更大的无关子图(在A中加入A'-B中的任何一点)。此过程必将终止,此时A'=B,新图为2分图。欲证(n+1)-无关图的最大边数可由n分图实现,可用归纳法。维持A的定义,将B的定义改为最大n-无关子图即可。
康MM
2009-02-05 10:58:54回复:回复:你好,好久不见了