回複：你好，好久不見了

我在腦壇找你好幾年了，不料你在這兒。這回我可找到組織了！
想不到叱詫風雲的康大帝竟然是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- ♀ (271 bytes) () 02/05/2009 postreply 10:58:54

• 回複：回複：回複：你好，好久不見了 -yaluzangbu- ♂ (233 bytes) () 02/05/2009 postreply 14:08:21

• 回複：回複：回複：回複：你好，好久不見了 -康MM- ♀ (82 bytes) () 02/06/2009 postreply 13:43:47

• 很漂亮！ -亂彈- ♂ (0 bytes) () 02/05/2009 postreply 16:28:23