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

【答案】見解析

【解析】

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

用反證法.

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

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

考慮與的對稱差

.

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

分兩種情形討論

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

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

練習(xí)冊系列答案
相關(guān)習(xí)題

科目：高中數(shù)學(xué) 來源： 題型：

【題目】某醫(yī)院為篩查某種疾病，需要檢驗血液是否為陽性，現(xiàn)有（）份血液樣本，有以下兩種檢驗方式：（1）逐份檢驗，則需要檢驗次；（2）混合檢驗，將其中（且）份血液樣本分別取樣混合在一起檢驗．若檢驗結(jié)果為陰性，這份的血液全為陰性，因而這份血液樣本只要檢驗一次就夠了，如果檢驗結(jié)果為陽性，為了明確這份血液究竟哪幾份為陽性，就要對這份再逐份檢驗，此時這份血液的檢驗次數(shù)總共為次．假設(shè)在接受檢驗的血液樣本中，每份樣本的檢驗結(jié)果是陽性還是陰性都是獨立的，且每份樣本是陽性結(jié)果的概率為．

（1）假設(shè)有5份血液樣本，其中只有2份樣本為陽性，若采用逐份檢驗方式，求恰好經(jīng)過4次檢驗就能把陽性樣本全部檢驗出來的概率．

（2）現(xiàn)取其中（且）份血液樣本，記采用逐份檢驗方式，樣本需要檢驗的總次數(shù)為，采用混合檢驗方式，樣本需要檢驗的總次數(shù)為

（�。┰囘\用概率統(tǒng)計的知識，若 ，試求關(guān)于的函數(shù)關(guān)系式；

（ⅱ）若，采用混合檢驗方式可以使得樣本需要檢驗的總次數(shù)的期望值比逐份檢驗的總次數(shù)期望值更少，求的最大值．

參考數(shù)據(jù)：，，，，

查看答案和解析>>

科目：高中數(shù)學(xué) 來源： 題型：

【題目】已知函數(shù).

（1）若函數(shù)，求的極值；

（2）證明：.

（參考數(shù)據(jù)： ）

查看答案和解析>>

科目：高中數(shù)學(xué) 來源： 題型：

【題目】已知橢圓（）的左焦點為，點為橢圓上任意一點，且的最小值為，離心率為.

（1）求橢圓的方程；

（2）設(shè)O為坐標(biāo)原點，若動直線與橢圓交于不同兩點、（、都在軸上方），且.

（i）當(dāng)為橢圓與軸正半軸的交點時，求直線的方程；

（ii）對于動直線，是否存在一個定點，無論如何變化，直線總經(jīng)過此定點？若存在，求出該定點的坐標(biāo)；若不存在，請說明理由.

查看答案和解析>>

科目：高中數(shù)學(xué) 來源： 題型：

【題目】某餐廳通過查閱了最近5次食品交易會參會人數(shù) (萬人)與餐廳所用原材料數(shù)量 (袋)，得到如下統(tǒng)計表：

第一次

第二次

第三次

第四次

第五次

參會人數(shù) (萬人)

13

9

8

10

12

原材料 (袋)

32

23

18

24

28

（1）根據(jù)所給5組數(shù)據(jù)，求出關(guān)于的線性回歸方程.

（2）已知購買原材料的費用 (元)與數(shù)量 (袋)的關(guān)系為，

投入使用的每袋原材料相應(yīng)的銷售收入為700元，多余的原材料只能無償返還，據(jù)悉本次交易大會大約有15萬人參加，根據(jù)(1)中求出的線性回歸方程，預(yù)測餐廳應(yīng)購買多少袋原材料，才能獲得最大利潤，最大利潤是多少？(注：利潤銷售收入原材料費用).

參考公式： ， .

參考數(shù)據(jù)： ， ， .

查看答案和解析>>

科目：高中數(shù)學(xué) 來源： 題型：

【題目】編號分別為的12名籃球運動員在某次籃球比賽中的得分記錄如下：

運動員編號

得分

5

10

12

16

8

21

27

15

6

22

18

29

（1）完成如下的頻率分布表：

得分區(qū)間

頻數(shù)

頻率

3

合計

（2）從得分在區(qū)間內(nèi)的運動員中隨機抽取2人，求這2人得分之和大于25的概率.

查看答案和解析>>

科目：高中數(shù)學(xué) 來源： 題型：

【題目】已知函數(shù)（為自然對數(shù)的底數(shù)）.

（1）討論函數(shù)的單調(diào)性；

（2）當(dāng)時，恒成立，求整數(shù)的最大值.

查看答案和解析>>

科目：高中數(shù)學(xué) 來源： 題型：

【題目】已知（m，n為常數(shù)），在處的切線方程為.

（Ⅰ）求的解析式并寫出定義域；

（Ⅱ）若任意，使得對任意上恒有成立，求實數(shù)a的取值范圍；

（Ⅲ）若有兩個不同的零點，求證： .

查看答案和解析>>

科目：高中數(shù)學(xué) 來源： 題型：

【題目】在直角坐標(biāo)系中，直線的參數(shù)方程為（為參數(shù)），直線與直線平行，且過坐標(biāo)原點，圓的參數(shù)方程為（為參數(shù)）．以坐標(biāo)原點為極點，軸的正半軸為極軸建立極坐標(biāo)系．

（1）求直線和圓的極坐標(biāo)方程；

（2）設(shè)直線和圓相交于點、兩點，求的周長．

查看答案和解析>>

同步練習(xí)冊答案