Question

【題目】設(shè)、為平面上兩個點集，滿足，，且任意三點不共線.在集合和間各連若干條線段，每條線段均一個端點在集合中，另一個端點在集合中，且任意兩點間至多連一條線段，記所有線段構(gòu)成的集合為.若集合滿足對于集合或中任意一點均至少連出條線段，則稱集合是“一好的”.試確定的最大值，使得去掉任意一條線段，集合均不是一好的.

Answer 1

【答案】見解析

【解析】

設(shè)集合中有個點引出邊數(shù)不為條，有個點恰引出條邊，設(shè)集合中有個點引出邊數(shù)不為條，有個點恰引出條邊.

由于對稱性，不妨設(shè).

記，其中，為集合中所有恰引出條線段的點構(gòu)成的集合，為集合中除去外余下的點構(gòu)成的集合，記B=，其中，為集合中所有恰引出條線段的點構(gòu)成的集合，為集合中除去外余下的點構(gòu)成的集合.

則滿足以下兩個估計：

（1） .

注意到，集合中的點僅能與集合中的點相鄰，故對于，

.

（2）.

對于集合中的任意一條邊，至少有一個端點在集合或內(nèi)，因此，

.

由（1）、（2）知

.

若，則；

若，則.

故當時，

；

當時，，即

構(gòu)造：（i）若，構(gòu)造兩個完全的二部圖，即將集合中的點劃分為兩個集合、；將集合中的點劃分為兩個集合、，，其中，將集合中每一點與集合中每一點均連線，將集合中每一點和集合中每一點均連線.

（ii）若，對集合、進行如下的劃分：

，

，；

，

，.

此時，將集合中的每一點與集合中的每一點相連，將集合中的每一點與集合i中的每一點均相連.然后，在和這兩個點集間再構(gòu)造一個的二部正則圖即可.