Question

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

Answer 1

【答案】見解析

【解析】

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

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

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

則滿足以下兩個(gè)估計(jì)：

（1） .

注意到，集合中的點(diǎn)僅能與集合中的點(diǎn)相鄰，故對(duì)于，

.

（2）.

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

.

由（1）、（2）知

.

若，則；

若，則.

故當(dāng)時(shí)，

；

當(dāng)時(shí)，，即

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

（ii）若，對(duì)集合、進(jìn)行如下的劃分：

，

，；

，

，.

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