Question

【題目】在一次數(shù)學(xué)競(jìng)賽中，某些選手是朋友關(guān)系.記所有選手的集合為X，對(duì)集合X的子集Y，若可以將這些人兩兩分組，且每組中兩名選手均是朋友關(guān)系，則稱子集Y“可兩兩分組”.已知集合X不可兩兩分組，且對(duì)于任意選手，若A、B不是朋友關(guān)系，則可兩兩分組，且X中沒有一個(gè)人與其他所有人均為朋友關(guān)系證明:對(duì)任意選手，若a、b為朋友關(guān)系，b、c為朋友關(guān)系，則a、c也為朋友關(guān)系

Answer 1

【答案】見解析

【解析】

考慮一個(gè)圖G，頂點(diǎn)由集合X組成，若X中兩人認(rèn)識(shí)，則將這兩人相連，否則不相連若一個(gè)圖中的點(diǎn)可以兩兩分組，且每組中兩個(gè)點(diǎn)均相連，則稱這種分組為圖G的一個(gè)“完美匹配”（可以看成是圖G的一個(gè)子圖）.于是，題目的條件變成了圖G不存在完美匹配，且若x、y不相連，則G＋xy（表示把這個(gè)圖G的xy也相連）存在一個(gè)完美匹配，且沒有一個(gè)點(diǎn)與所有點(diǎn)均相連.

用反證法.

若存在a、b、c使得a、b認(rèn)識(shí)，b、c認(rèn)識(shí)，但a、c不認(rèn)識(shí)，由于沒有人認(rèn)識(shí)其他所有人，故存在，使得b、d不認(rèn)識(shí).

由假設(shè)可得G＋ac有一個(gè)完美匹配，記為；G＋bd也有一個(gè)完美匹配記為.

考慮與的對(duì)稱差

.

則容易得到S是一些互不相交的圈，且每個(gè)圈均由偶數(shù)個(gè)點(diǎn)組成，設(shè)ac屬于圈，bd屬于圈.

分兩種情形討論

若，則在圈外的點(diǎn)按照的分組方式分組，在圈中按照的分組方式即可得到原圖G的一個(gè)完美匹配，即得矛盾.

若，則這個(gè)圈從b出發(fā)沿邊bd開始，不妨設(shè)首先連到點(diǎn)a，即b到a的路徑（首先經(jīng)過邊bd）為P，于是，P＋ab為一個(gè)圈，其中，有一半的邊（間隔地）屬于對(duì)P＋ab這個(gè)圈外的點(diǎn)按的方式分組，而對(duì)P＋ab按ab及的方式分組即可得到原圖G的一個(gè)完美匹配，即得矛盾.