《《提優(yōu)教程》2012江蘇省高中數(shù)學(xué) 第67講 圖論問(wèn)題一競(jìng)賽教案》由會(huì)員分享，可在線(xiàn)閱讀，更多相關(guān)《《提優(yōu)教程》2012江蘇省高中數(shù)學(xué) 第67講 圖論問(wèn)題一競(jìng)賽教案（12頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、 第67講 圖論問(wèn)題(一) 本節(jié)主要內(nèi)容是：把一個(gè)具體問(wèn)題用圖形表示出來(lái)，利用圖形的直觀(guān)性可能更有利于問(wèn)題的解決． 有關(guān)的一些概念：由若干個(gè)不同的點(diǎn)及連接其中某些點(diǎn)對(duì)的線(xiàn)所組成的圖形就稱(chēng)為圖．圖中的點(diǎn)的集合稱(chēng)為圖的點(diǎn)集，記為V：V＝{v1，v2，…，vn，…}；圖中的線(xiàn)的集合稱(chēng)為圖的線(xiàn)集(邊的集合)，記為E：E＝{vivj}(vi，vj∈V)．故一個(gè)圖由其點(diǎn)集V和線(xiàn)集E所決定，若用G表示圖，則記為G＝G(V；E)．含有n個(gè)點(diǎn)的圖稱(chēng)為n階圖． 在一個(gè)圖中，如果某點(diǎn)v共連了k條線(xiàn)，則說(shuō)此點(diǎn)的“次數(shù)”(或“度數(shù)”)為k，記為degv＝k.如果一個(gè)p階圖的每?jī)蓚€(gè)頂點(diǎn)間都連且只連了1條線(xiàn)，則稱(chēng)該

2、圖為p階完全圖，記為Kp． 若對(duì)每條線(xiàn)確定一個(gè)方向(即確定了線(xiàn)的兩個(gè)端點(diǎn)中一個(gè)為“起點(diǎn)”，另一個(gè)為“終點(diǎn)”．這時(shí)，線(xiàn)是點(diǎn)的“有序?qū)Α?，則得到“有向圖”；對(duì)有向圖的一個(gè)頂點(diǎn)v，degv＝k，若v是其中n條邊的起點(diǎn)，m條邊的終點(diǎn)(m＋n＝k)，則稱(chēng)v的出次為n，入次為m． 鏈：若在一個(gè)圖G＝(V；E)中取n+1個(gè)頂點(diǎn) v1、v2、…、vn+1，每?jī)蓚€(gè)相鄰的頂點(diǎn)vi、vi+1間連有一條邊li,則邊l1,l2,…,ln就稱(chēng)為從v1到vn+1的一條鏈．n稱(chēng)為鏈的長(zhǎng)度． A類(lèi)例題 例1 ⑴證明任意的六人中一定有三個(gè)人互相認(rèn)識(shí)或互不認(rèn)識(shí)(約定甲認(rèn)識(shí)乙就意味著乙認(rèn)識(shí)甲)． ⑵ K6的邊染成紅藍(lán)

3、兩色，求證：其中必有兩個(gè)三角形，其三邊同色． 分析 ⑴ 以點(diǎn)表示人，連紅、藍(lán)兩色的線(xiàn)分別表示“認(rèn)識(shí)”與“不認(rèn)識(shí)”，問(wèn)題轉(zhuǎn)化成圖的問(wèn)題．要會(huì)把題目的語(yǔ)言轉(zhuǎn)譯成圖的語(yǔ)言：“三人互相認(rèn)識(shí)”就表示三點(diǎn)間都連紅線(xiàn)，“三人互不認(rèn)識(shí)”就表示三點(diǎn)間都連藍(lán)線(xiàn)．⑵ 考慮每個(gè)異色三角形的三個(gè)角，其中兩個(gè)角是異色角，而同色三角形的三個(gè)角都是同色角． 證明 ⑴ 用6個(gè)點(diǎn)v1，v2，…，v6表示這6個(gè)人，如果某兩人相互認(rèn)識(shí)，則在表示此二人的點(diǎn)間連一條紅線(xiàn)，否則連一條藍(lán)線(xiàn)．于是問(wèn)題轉(zhuǎn)化為證明此6點(diǎn)間一定連出了三邊均為紅色或藍(lán)色的三角形． 在點(diǎn)v1連出的5條線(xiàn)中，由抽屜原理知，必有某色線(xiàn)連有3條或3條以上．不妨設(shè)紅線(xiàn)連

4、了至少3條．設(shè)v1與v2、v3、v4連的紅線(xiàn)．現(xiàn)考慮點(diǎn)v2、v3、v4連線(xiàn)的情況，如果此三點(diǎn)間有任兩點(diǎn)連的紅線(xiàn)，則出現(xiàn)紅色三角形(例如v2v3連紅線(xiàn)，則v1v2v3是紅色三角形)，如果這三點(diǎn)間都不連紅線(xiàn)，則出現(xiàn)藍(lán)色三角形(v2v3v4是藍(lán)色三角形)．故證． ⑵ 考慮K6共連了C＝15條線(xiàn)，共得到C＝20個(gè)三角形．設(shè)第i個(gè)頂點(diǎn)連了ri(0≤i≤5)條紅線(xiàn)，5－ri條藍(lán)線(xiàn)．由于ri(5－ri)≤6．所以，連出的異色角個(gè)數(shù)≤66＝36個(gè)．由于每個(gè)異色的三角形有2個(gè)異色角，所以圖中異色三角形個(gè)數(shù)≤18，故圖中同色三角形個(gè)數(shù)≥20－18＝2． 說(shuō)明 題⑴是早期匈牙利的一個(gè)圖論競(jìng)賽題．解這類(lèi)“實(shí)際問(wèn)題

5、”時(shí)，重要的是會(huì)用圖的語(yǔ)言解釋題意，把實(shí)際問(wèn)題改寫(xiě)為圖的問(wèn)題． ⑵ 用異色角來(lái)解相關(guān)問(wèn)題是較好的方法． 例2 由5人組成一個(gè)公司，其中任意三人總有2人彼此認(rèn)識(shí)，也總有2人彼此不認(rèn)識(shí)．證明：這五人可以圍桌而坐，使每人兩旁都是他認(rèn)識(shí)的人．(1978年保加利亞數(shù)學(xué)競(jìng)賽) 證明 用5個(gè)點(diǎn)表示這5個(gè)人，若兩人互相認(rèn)識(shí)，則在表示這2個(gè)人的點(diǎn)間連1條線(xiàn)．題目的條件即是：任三點(diǎn)間至少連1條線(xiàn)，但不能連3條線(xiàn)． 首先，每點(diǎn)都至少連了2條線(xiàn)，若點(diǎn)v1只連出1條線(xiàn)，則它至少與某三點(diǎn)(設(shè)為v2、v3、v4)未連線(xiàn)，則此3點(diǎn)間都要連線(xiàn)(若v2與v3沒(méi)有連線(xiàn)，則v1與v2、v3就都沒(méi)有連線(xiàn)，與已知矛盾)．出現(xiàn)

6、了以v2、v3、v4為頂點(diǎn)的三角形，矛盾． 其次，若某點(diǎn)連出了3條線(xiàn)，則此三點(diǎn)間都不能連線(xiàn)，與已知矛盾． 故知：每點(diǎn)都恰連2條線(xiàn)．它不能連成三角形，也不能連成四邊形，否則余下的點(diǎn)無(wú)法連線(xiàn)，故只能如圖所示，證畢． 說(shuō)明 仔細(xì)體會(huì)上述兩例的特點(diǎn)，明白什么時(shí)候應(yīng)該用圖來(lái)解相關(guān)的題：當(dāng)涉及多個(gè)元素的某些相互關(guān)系時(shí)，就可能用圖來(lái)解釋?zhuān)? 情景再現(xiàn) 1．在例1中，把6個(gè)人改為5個(gè)人，結(jié)論是否一定成立？ 2．圖G有n個(gè)頂點(diǎn)，n+1條邊，證明：圖G至少有一個(gè)頂點(diǎn)的次數(shù)≥3． B類(lèi)例題 例3 設(shè)競(jìng)賽圖(每?jī)蓚€(gè)點(diǎn)都連了1條線(xiàn)的有向圖)中，點(diǎn)Ak的出次與入次分別為wk與ek(k＝1，2，…，n

7、)， 證明 w＋w＋…＋w＝e＋e＋…＋e． 分析 根據(jù)競(jìng)賽圖的特點(diǎn)可知：⑴ 每點(diǎn)的出次與入次的和都等于n－1，⑵ 所有點(diǎn)的出次的和與入次的和相等．由此可以推出：所有點(diǎn)的出次和與入次和都等于n(n－1)．這是兩個(gè)基本的性質(zhì)．在要證的式子中把ek用n－1－wk代替． 證明 對(duì)于每個(gè)點(diǎn)，出次與入次的和都是n－1，即 wk＋ek＝n－1(k＝1，2，…，n)， ① 所有出次的和與所有入次的和相等，且都等于圖中弧的條數(shù)： w1＋w2＋…＋wn＝e1＋e2＋…＋en＝n(n－1)．② 所以 e＋e＋…＋e ＝(n－1－w1)2＋(n－1－w2)2＋…＋(n－1－wn)2 ＝

8、n(n－1)2＋w＋w＋…＋w－2(w1＋w2＋…＋wn)(n－1) ＝w＋w＋…＋w＋n(n－1)2－2(n－1)(n－1) ＝ w＋w＋…＋w． 說(shuō)明 本題的證明方法與《奇偶分析》中的例6相似． 例4 平面上給定7個(gè)點(diǎn)，用一些線(xiàn)段連接它們，每三個(gè)點(diǎn)中至少有兩點(diǎn)相連，問(wèn)至少要有多少條線(xiàn)段？試給出一個(gè)圖．(1989蒙古數(shù)學(xué)競(jìng)賽) 分析 首先找到連線(xiàn)條數(shù)的下界(即至少要連出多少條線(xiàn))，再尋找是否可能達(dá)到這個(gè)下界，可以分別枚舉可能的連線(xiàn)方法，討論每種方法的連線(xiàn)條數(shù)，得到最小的結(jié)果． 解 7個(gè)點(diǎn)中共有三點(diǎn)組C=35個(gè)．每條線(xiàn)段共與其余5點(diǎn)組成5個(gè)三角形．故線(xiàn)段條數(shù)≥＝7條． 如果有

9、一個(gè)點(diǎn)沒(méi)有連線(xiàn)，則其余6點(diǎn)兩兩都必須連線(xiàn)，要C＝15條． 如果有一點(diǎn)只連了一條線(xiàn)，其余5點(diǎn)必須兩兩連線(xiàn)，連線(xiàn)數(shù)＞C＝10條． 設(shè)某點(diǎn)只連了2條線(xiàn)，如點(diǎn)A只連了AB、AC這2條線(xiàn)，則其余4點(diǎn)均未與A連線(xiàn)，于是它們必須兩兩互連，應(yīng)連C=＝6條．此時(shí)，取B、C兩點(diǎn)及其余4點(diǎn)中的任一點(diǎn)，尚不滿(mǎn)足條件，故BC應(yīng)連線(xiàn)，此時(shí)連了9條線(xiàn)，所得圖形滿(mǎn)足題目要求． 若每點(diǎn)都至少連出3條線(xiàn)，則總度數(shù)≥21，即至少連了[]+1＝11條線(xiàn)． 所以，至少連9條線(xiàn)． 例5 九名數(shù)學(xué)家在一次國(guó)際會(huì)議上相遇，發(fā)現(xiàn)他們中的任三人中至少有兩人能用同一種語(yǔ)言對(duì)話(huà)，如果每個(gè)數(shù)學(xué)家至多會(huì)用三種語(yǔ)言．證明：至少有三人可用同

10、一種語(yǔ)言對(duì)話(huà)．(1978年美國(guó)數(shù)學(xué)競(jìng)賽) 分析 9個(gè)人用9個(gè)點(diǎn)表示．證法1中，多種語(yǔ)言則用多種顏色的線(xiàn)來(lái)表示，轉(zhuǎn)譯結(jié)論“三人可用同一種語(yǔ)言對(duì)話(huà)”時(shí)，應(yīng)注意：如果從一點(diǎn)向另兩點(diǎn)連出了同色的兩條線(xiàn)，表示另兩人也能用相應(yīng)的語(yǔ)言對(duì)話(huà)，從而就出現(xiàn)了同色三角形．所以，只要證明從一點(diǎn)一定引出了同色的線(xiàn)即可．而在證法2中，改設(shè)若二人不能對(duì)話(huà)就連1條線(xiàn)(即不存在二人都會(huì)的語(yǔ)言)．此時(shí)結(jié)論就應(yīng)轉(zhuǎn)譯為“存在三點(diǎn)，兩兩都沒(méi)有連線(xiàn)”． 證法1 用9個(gè)點(diǎn)表示這9個(gè)人，某二人如能用第r種語(yǔ)言交談，則在表示此二人的點(diǎn)間連一條線(xiàn)，并涂上第r種顏色，于是，本題即是證明，存在一個(gè)同色的三角形． 首先，若v1與v2、v1與v3

11、間都連了第k種顏色線(xiàn)，則v2與v3間也要連第k種顏色線(xiàn)．此時(shí)即出現(xiàn)同色的三角形．所以只要證明從其中某一點(diǎn)出發(fā)的線(xiàn)中必有兩條線(xiàn)的顏色相同． 反設(shè)從任一點(diǎn)出發(fā)的線(xiàn)中沒(méi)有同色的線(xiàn)，由于每個(gè)人至多會(huì)用三種語(yǔ)言．即degvi≤3，于是v1至少與5個(gè)點(diǎn)不鄰接，設(shè)為v2、…、v6，同樣，v2至少與5個(gè)點(diǎn)不相鄰接，于是v3、…、v6中至少有一點(diǎn)與v2不相鄰接．設(shè)為v3，于是v1、v2、v3不相鄰接．與已知“任三人中都至少有兩人能用同一種語(yǔ)言對(duì)話(huà)”矛盾．故證． 證法2 取9個(gè)點(diǎn)v1，v2，…，v9表示9個(gè)人，如果某二人不能對(duì)話(huà)，則在表示此二人的點(diǎn)間連一條線(xiàn)，于是在任何三點(diǎn)間，都有兩個(gè)點(diǎn)不相鄰，即不存在三角形

12、． 如果有人至少與4個(gè)點(diǎn)不連線(xiàn)，由于他最多只能講三種語(yǔ)言，則他必與其中某兩人講同一種語(yǔ)言．于是相應(yīng)三人可以用同一種語(yǔ)言來(lái)對(duì)話(huà)． 下面證明存在一點(diǎn)，其度不大于4．從而該點(diǎn)至少與4點(diǎn)不相鄰．如果degv1≤4，則v1即為所求．若degv1＞4，則至少degv1＝5，即至少有5個(gè)點(diǎn)與之連線(xiàn)，設(shè)為v2，…，v6，由于這些點(diǎn)不能連出三角形，故v2，…，v6的任何兩個(gè)之間都不能連線(xiàn)，從而v2與v3，…，v6均無(wú)連線(xiàn)，于是degv2≤4．即可證得原題． 說(shuō)明 兩點(diǎn)間連了1條線(xiàn)，則說(shuō)這兩點(diǎn)相鄰． 本題的兩種證明方法從兩個(gè)方向出發(fā)，一種是兩人可用同一種語(yǔ)言通話(huà)，就在相應(yīng)兩點(diǎn)間連一條邊，證法2是反過(guò)來(lái)，兩

13、人不能通話(huà)時(shí)則連一條邊，都能應(yīng)用圖解決問(wèn)題． 例6 俱樂(lè)部里有14個(gè)人想打橋牌，已知過(guò)去每個(gè)人都與其中的5個(gè)人合作過(guò)，現(xiàn)在規(guī)定4個(gè)人中必須任兩個(gè)人都沒(méi)有合作過(guò)才準(zhǔn)許在一起打1局橋牌，這樣打了3局就無(wú)法再打下去了，如果這時(shí)又來(lái)了一人，他與原來(lái)的14個(gè)人都沒(méi)有合作過(guò)，證明：一定可以再打1局． 分析 打橋牌時(shí)，4人分成合作的兩對(duì)，合作的兩人坐在相對(duì)的位置打牌．于是每局橋牌，都有兩對(duì)人合作． 把題目的條件與結(jié)論都轉(zhuǎn)述為圖的語(yǔ)言，并找出結(jié)論的等價(jià)命題是：找到三個(gè)人互相都沒(méi)有合作過(guò)，即存在3個(gè)點(diǎn)互不相鄰． 證明 用14個(gè)點(diǎn)表示這14個(gè)人，若某兩人合作過(guò)，則在表示這兩人的點(diǎn)間連一條線(xiàn)，于是，題目

14、條件即：其中每個(gè)點(diǎn)都已連出了5條線(xiàn)，且在此14個(gè)點(diǎn)中，可以找出3組點(diǎn)(每組4個(gè)點(diǎn))，這三組點(diǎn)間，兩兩未連線(xiàn)，若這3組點(diǎn)之間共連出6條線(xiàn)后，對(duì)于任意4點(diǎn)，都至少有兩點(diǎn)連了線(xiàn)．(14個(gè)點(diǎn)間一共連了41條線(xiàn))，證明此時(shí)一定存在3個(gè)點(diǎn)，兩兩都沒(méi)有連線(xiàn)(從而添入第15個(gè)點(diǎn)后，可與此3點(diǎn)合成4點(diǎn)，兩兩無(wú)連線(xiàn))． 由于14個(gè)點(diǎn)中的每個(gè)點(diǎn)原來(lái)都與(14－1－5＝)8個(gè)點(diǎn)不相鄰．在又打3局連出了6條邊以后，至多有12個(gè)點(diǎn)又連了線(xiàn)，所以至少還有2個(gè)點(diǎn)，每個(gè)點(diǎn)仍與8個(gè)點(diǎn)不相鄰．設(shè)其中一點(diǎn)為v1．與v1不相鄰的點(diǎn)集為S． 下面證明：S中必有一點(diǎn)v2至少與7個(gè)點(diǎn)不相鄰．反設(shè)不存在這樣的點(diǎn)，則此8點(diǎn)中，每個(gè)點(diǎn)都至多與

15、6個(gè)點(diǎn)不相鄰，故此8個(gè)點(diǎn)都至少連了(14－6－1＝)7條邊，于是此8點(diǎn)中的每個(gè)點(diǎn)又都新連了至少2條邊，故又新連出了822＝8條邊(除以2是因?yàn)槊織l邊可能在兩個(gè)點(diǎn)端點(diǎn)處被計(jì)算了2次)．這與只連了6條邊矛盾，所以存在S中的一點(diǎn)v2，至少與7個(gè)點(diǎn)不相鄰． 但8+7＝15＞14，必有一點(diǎn)v3與v1，v2均未連線(xiàn)．此三點(diǎn)即為所求． 鏈接 v3存在是根據(jù)容斥原理：把這14個(gè)人的集合記為S，與v1相鄰的點(diǎn)集記為A，與v2相鄰的點(diǎn)集記為B，則A∪BS．故 card(A∪B)≤card(S)． 而 card(A∪B)＝card(A)＋card(B)－card(A∩B)， 故

16、 card(A)＋card(B)－card(A∩B)≤card(S)， 現(xiàn)card(A)＋card(B)＝15，card(S)＝14，于是card(A∩B)＞0． 情景再現(xiàn) A B C D 3．⑴右面的有向圖由4個(gè)頂點(diǎn)及一些弧(有向線(xiàn)段)組成，指出各點(diǎn)的出次(引出的弧的條數(shù))與入次(引入的弧的條數(shù))． ⑵求出上題中所有各點(diǎn)的出次的和與入次的和，它們與弧的條數(shù)有什么關(guān)系？ ⑶證明：任一有向圖中，出次的和與入次的和相等． 4．在n(n≥3)個(gè)點(diǎn)的競(jìng)賽圖中，一定有兩個(gè)點(diǎn)的出次相同嗎？ 5．在集合S的元素之間引入關(guān)系“→”．⑴ 對(duì)于任意兩個(gè)元素a，b∈S，要么a→b，要么b→

17、a，二者有且只有一個(gè)成立；⑵ 對(duì)任意三個(gè)元素a，b，c，如果a→b，b→c，則c→a．問(wèn)集合S中最多能有多少個(gè)元素？(1972年英國(guó)數(shù)學(xué)競(jìng)賽) 6．證明：⑴ 如果競(jìng)賽圖中各點(diǎn)的出次不等， 那么可將這些點(diǎn)排成一列，排在前面的點(diǎn)有弧到達(dá)排在后面的任一點(diǎn)(即排在前面的選手勝排在后面的所有選手)． ⑵ 如果點(diǎn)數(shù)n≥3的競(jìng)賽圖中有三角形回路，那么，圖中必有兩點(diǎn)的出次相等． C類(lèi)例題 例7 某足球賽有16個(gè)城市參加，每市派出2個(gè)隊(duì)，根據(jù)比賽規(guī)則，每?jī)申?duì)之間至多賽一場(chǎng)，同城兩隊(duì)之間不進(jìn)行比賽．賽過(guò)一段時(shí)間后，發(fā)現(xiàn)除A城甲隊(duì)外，其他各隊(duì)已賽過(guò)的場(chǎng)數(shù)各不相同．問(wèn)A城乙隊(duì)已賽過(guò)幾場(chǎng)?證明你的結(jié)論．

18、分析 注意分析“各隊(duì)賽過(guò)場(chǎng)次各不相同”的含義，即能推知比賽場(chǎng)次的取值情況．再?gòu)谋荣悎?chǎng)次最多的隊(duì)開(kāi)始討論，與之比賽的隊(duì)是哪些隊(duì)？ 證明 用32個(gè)點(diǎn)表示這32個(gè)隊(duì)，如果某兩隊(duì)比賽了一場(chǎng)，則在表示這兩個(gè)隊(duì)的點(diǎn)間連一條線(xiàn)．否則就不連線(xiàn)． 由于，這些隊(duì)比賽場(chǎng)次最多30場(chǎng)，最少0場(chǎng)，共有31種情況，現(xiàn)除A城甲隊(duì)外還有31個(gè)隊(duì)，這31個(gè)隊(duì)比賽場(chǎng)次互不相同，故這31個(gè)隊(duì)比賽的場(chǎng)次恰好從0到30都有．就在表示每個(gè)隊(duì)的點(diǎn)旁注上這隊(duì)的比賽場(chǎng)次． 考慮比賽場(chǎng)次為30的隊(duì)，這個(gè)隊(duì)除自己與同城的隊(duì)外，與不同城的隊(duì)都進(jìn)行了比賽，于是，它只可能與比賽0場(chǎng)的隊(duì)同城；再考慮比賽29場(chǎng)的隊(duì)，這個(gè)隊(duì)除與同城隊(duì)及比賽0場(chǎng)、1場(chǎng)(

19、只賽1場(chǎng)的隊(duì)已經(jīng)與比賽30場(chǎng)的隊(duì)賽過(guò)1場(chǎng)，故不再與其它隊(duì)比賽)的隊(duì)不比賽外，與其余各隊(duì)都比賽，故它與比賽1場(chǎng)的隊(duì)同城；依次類(lèi)推，知比賽k場(chǎng)的隊(duì)與比賽30－k場(chǎng)的隊(duì)同城，這樣，把各城都配對(duì)后，只有比賽15場(chǎng)的隊(duì)沒(méi)有與其余的隊(duì)同城，故比賽15場(chǎng)的隊(duì)就是A城乙隊(duì)．即A城乙隊(duì)比賽了15場(chǎng)． 說(shuō)明 有些題的已知條件討論起來(lái)頭緒紛繁，如果利用圖來(lái)討論則可以化繁為簡(jiǎn)．利用點(diǎn)與線(xiàn)的相鄰與否來(lái)研究這一類(lèi)題目需要一定的技巧，也需要相當(dāng)?shù)某橄蟾爬芰εc邏輯推理能力．請(qǐng)大家多做些練習(xí)． 例8 n(n＞3)名乒乓球選手單打若干場(chǎng)后，任意兩個(gè)選手已賽過(guò)的對(duì)手恰好都不完全相同，試證明：總可以從中去掉一名選手，而使在

20、余下的選手中，任意兩個(gè)選手已賽過(guò)的對(duì)手仍然都不完全相同．(1987年全國(guó)高中數(shù)學(xué)聯(lián)賽) 分析 本題的求證暗示要用反證法，設(shè)去掉任一個(gè)選手，都會(huì)有兩個(gè)選手賽過(guò)的對(duì)手完全相同．于是這兩人組成一個(gè)點(diǎn)對(duì)．這樣就會(huì)得到n個(gè)點(diǎn)對(duì)．每個(gè)點(diǎn)對(duì)連一條線(xiàn)，n個(gè)點(diǎn)連出了n條線(xiàn)，就可用圖的性質(zhì)得到圈，使問(wèn)題得證．這是證法1的思路． 每個(gè)選手的對(duì)手可以組成集合，研究對(duì)手集的性質(zhì)，用最小數(shù)原理來(lái)證明，這是證法2的思路． 證法1 把這些選手編為1至n號(hào)，以n個(gè)點(diǎn)表示這n個(gè)人，各點(diǎn)也相應(yīng)編為1至n號(hào)． 反設(shè)去掉任何一個(gè)選手后，都有兩個(gè)選手的已賽過(guò)的對(duì)手完全相同．于是，如果先去掉1號(hào)選手，則有兩個(gè)選手的已賽過(guò)的對(duì)手完全

21、相同，設(shè)為第i號(hào)與第j號(hào)，在表示此二人的點(diǎn)間連一條線(xiàn)，并在線(xiàn)上注上“1號(hào)”．這說(shuō)明，此二人在去掉1號(hào)選手之前必是一人與1號(hào)賽過(guò)，另一人與1號(hào)沒(méi)有賽過(guò)．而且不可能在去掉1號(hào)后有三人都相同，否則，此三人與1號(hào)選手比賽的情況只有兩種：賽過(guò)或沒(méi)有賽過(guò)，如果去掉1號(hào)后，此三人的情況完全相同，則去掉1號(hào)之前必有2人賽過(guò)的對(duì)手完全相同．(如果去掉1號(hào)后有不止一對(duì)選手的已賽過(guò)對(duì)手完全相同，則只任取其中的一對(duì)連線(xiàn)，其余的對(duì)則不連線(xiàn)．) 同樣，如果再依次去掉2號(hào)、3號(hào)，…，直至n號(hào)，每去掉1個(gè)選手，都會(huì)在某兩點(diǎn)之間連1條線(xiàn)．這樣，就在n個(gè)點(diǎn)間連了n條線(xiàn)．且這些線(xiàn)上分別注了1至n號(hào)，每條線(xiàn)注了1個(gè)號(hào)碼，每個(gè)號(hào)碼只

22、注在1條線(xiàn)上． 由于在10個(gè)點(diǎn)間連了10條線(xiàn)，故圖中必存在一圈． 現(xiàn)從圈上一點(diǎn)i出發(fā)，經(jīng)過(guò)點(diǎn)j、k、…最后回到點(diǎn)i．注意到點(diǎn)i與點(diǎn)j所代表的兩個(gè)選手中1個(gè)是與1號(hào)比賽的，另一個(gè)是沒(méi)有與1號(hào)比賽的，不妨設(shè)i號(hào)沒(méi)有與1號(hào)比賽過(guò)，j號(hào)與1號(hào)比賽過(guò)．而j與k所連線(xiàn)上注的號(hào)碼不是1，故j與k與1號(hào)比賽的情況相同，即k號(hào)與1號(hào)比賽過(guò)，…，這樣沿線(xiàn)走一圈后回到i，就應(yīng)該得出i號(hào)與1號(hào)比賽過(guò)，矛盾．故證． 證明2 用A、B、…表示選手，而用α(A)、α(B)表示A、B已賽過(guò)的對(duì)手集合．顯然，若A∈α(B)，則B∈α(A)． 設(shè)A是對(duì)手集中元素最多的的選手． 若命題不成立，則存在兩個(gè)選手B、C使去掉A

23、后，B、C的對(duì)手集相同，由于α(B)≠α(C)，故A必屬于α(B)與α(C)之一．不妨設(shè)A∈α(B)，于是，B∈α(A)，Cα(A)且α(C)＝α(B)\{A}．(在α(B)中去掉它的一個(gè)元素A后的集合表示為α(B)\{A}) 同樣對(duì)于選手C后，存在D、E，使去掉C后，D、E的對(duì)手集相同，即去掉C后，α(D)＝α(E)，又設(shè)C∈α(D)且Cα(E)，于是D∈α(C)，Eα(C)． 由于Aα(C)，D∈α(C)，故D≠A：又D∈α(C)，故D∈α(B)，即B∈α(D) ＝α(E)∪{C}，從而B(niǎo)∈α(E)，Cα(E)，而去掉A后，B、C的對(duì)手集相同，從而E＝A． 于是α(A) ＝α(E)

24、＝α(D)\{C}，即α(A)比α(D)少一個(gè)元素C，這與A是“對(duì)手集中元素最多的”矛盾．故證． 說(shuō)明 證法1是根據(jù)如下結(jié)論：如果n個(gè)點(diǎn)間連了n條線(xiàn)，則必出現(xiàn)“圈”：即從某一點(diǎn)出發(fā)，沿邊前進(jìn)，最后還能回到出發(fā)點(diǎn)． 證法2用最小數(shù)原理對(duì)集合的元素進(jìn)行討論，較難理解，可對(duì)照?qǐng)D理解相應(yīng)的結(jié)論． 鏈接 樹(shù)與圈 若在一個(gè)圖G=(V；E)中取n+1個(gè)頂點(diǎn) v1、v2、…、vn+1，每?jī)蓚€(gè)相鄰的頂點(diǎn)vi、vi+1間連有一條邊li,則邊l1,l2,…,ln就稱(chēng)為從v1到vn+1的一條鏈．一個(gè)圖中的任意兩個(gè)頂點(diǎn)間如果都有一條鏈，該圖就是連通的．一條鏈的兩個(gè)端點(diǎn)v1與vn+1重合時(shí)，就稱(chēng)為圈．沒(méi)有圈的連通

25、圖稱(chēng)為樹(shù)．n階樹(shù)可以記為T(mén)n．在一個(gè)圖中，次數(shù)為1的頂點(diǎn)稱(chēng)為懸掛點(diǎn)． 定理1 如果樹(shù)T的頂點(diǎn)數(shù)≥2，那么，它至少有兩個(gè)懸掛點(diǎn)． 從樹(shù)的任何一個(gè)頂點(diǎn)出發(fā)，沿某個(gè)方向前進(jìn)，已走過(guò)的邊不重復(fù)走，由于樹(shù)是無(wú)圈的，故每個(gè)頂點(diǎn)至多走過(guò)1次，如果，經(jīng)過(guò)的一個(gè)頂點(diǎn)不是懸掛點(diǎn)，則還可以前進(jìn)到下一個(gè)頂點(diǎn)，由于樹(shù)的頂點(diǎn)只有有限個(gè)，故前進(jìn)到某個(gè)頂點(diǎn)(如果圖中共有n個(gè)頂點(diǎn)，則至多前進(jìn)n－1步)后就無(wú)法再繼續(xù)前進(jìn)，即到達(dá)一個(gè)次數(shù)為1的頂點(diǎn)．此頂點(diǎn)即為一個(gè)懸掛點(diǎn)．再?gòu)拇藨覓禳c(diǎn)出發(fā)，沿鏈走一次(第一步是按剛才的反方向前進(jìn))，則又可以到達(dá)一個(gè)懸掛點(diǎn)．此懸掛點(diǎn)與剛才第一個(gè)懸掛點(diǎn)不同．即圖中至少有兩個(gè)懸掛點(diǎn)． 定理2一個(gè)n階

26、的連通圖是1個(gè)樹(shù)，當(dāng)且僅當(dāng)它有n－1條邊． 先證明：如果樹(shù)T的頂點(diǎn)數(shù)為n，則其邊數(shù)為n－1． 證明 對(duì)于n＝1或2，定理顯然成立． 設(shè)定理對(duì)于k個(gè)頂點(diǎn)時(shí)成立，即若一個(gè)樹(shù)有k個(gè)頂點(diǎn)，則其邊有k－1條．對(duì)于k+1個(gè)頂點(diǎn)的樹(shù)，只要去掉一個(gè)懸掛點(diǎn)及與之相鄰的一條邊，就成為有k個(gè)頂點(diǎn)的情形，此時(shí)的樹(shù)有k個(gè)頂點(diǎn)與k－1條邊，此時(shí)再把去掉的1個(gè)頂點(diǎn)及1條邊添入，就成為k+1個(gè)頂點(diǎn)，k條邊的樹(shù)．故證． 再證明：如果圖G是連通的，且有n個(gè)頂點(diǎn)與n－1條邊，則G是一個(gè)樹(shù)． 取G的生成樹(shù)T，則此生成樹(shù)有n個(gè)頂點(diǎn)，因是樹(shù)，故有n－1條邊．但TG，故T＝G．故證． 定理3 樹(shù)T具有以下性質(zhì)： ⑴ 在T中去

27、掉任一邊后，所得的圖是不連通的； ⑵ 在T中添上1條邊后，所得的圖有圈； ⑶ T中的任兩個(gè)頂點(diǎn)v1與v2間有且僅有1條鏈． 證明 ⑴ 設(shè)樹(shù)T有n個(gè)頂點(diǎn)與n－1條邊，在T中去掉1條邊后得到圖G，如果G仍連通，則G仍是一個(gè)樹(shù)(因無(wú)圈且連通)．應(yīng)有n－1條邊，矛盾． ⑵ 如添上1邊后仍無(wú)圈，則仍為樹(shù)，有n個(gè)頂點(diǎn)與n條邊，矛盾． ⑶ 由T連通，故v1與v2間必有鏈，若v1與v2間有不完全相同的兩條鏈，則此圖中有圈，即不是樹(shù)．矛盾，故v1與v2間有且僅有1條鏈． 情景再現(xiàn) 7．某個(gè)團(tuán)體有1982個(gè)人，其中任意4人都至少有一人認(rèn)識(shí)其他三個(gè)人，認(rèn)識(shí)其他所有人的人數(shù)最少是多少？(1982年美國(guó)

28、數(shù)學(xué)競(jìng)賽) 8．⑴在一所房子里有10個(gè)人，其中任意3人中至少有2人互相認(rèn)識(shí)，證明：其中有4人，他們?nèi)我?人都互相認(rèn)識(shí)．(1980英國(guó)數(shù)學(xué)競(jìng)賽) ⑵如果把⑴中的數(shù)10改為9，結(jié)論仍成立否？(1977年波蘭數(shù)學(xué)競(jìng)賽) 習(xí)題13 1．如果每個(gè)點(diǎn)的出次都是2，那么，一個(gè)點(diǎn)經(jīng)過(guò)兩條弧就可以到達(dá)的點(diǎn)至多有幾個(gè)？經(jīng)過(guò)一條弧或兩條弧可以到達(dá)的點(diǎn)至多有幾個(gè)？ 2．在競(jìng)賽圖中必有一個(gè)點(diǎn)，從它到其它的頂點(diǎn)，只需經(jīng)過(guò)一條弧或兩條?。? 3．一個(gè)有n個(gè)點(diǎn)的競(jìng)賽圖，各點(diǎn)的出次為w1≥w2≥…≥wn．如果w1＝n－1，w2＝n－2，…，wk－1＝n－(k－1)，但wk≠n－k(1≤k≤n)．證明：wk＜n－k

29、． 4．⑴ 如果在點(diǎn)數(shù)n≥3的競(jìng)賽圖中，有兩個(gè)點(diǎn)的出次相等．證明，圖中必有三角形回路(即有三個(gè)選手A、B、C，其中A勝B，B勝C，C又勝A)． ⑵ 在一個(gè)n人參加的循環(huán)賽中，每?jī)扇吮荣愐粓?chǎng)，如果沒(méi)有平局，參賽者贏的場(chǎng)數(shù)分別是w1，w2，…，wn．求證：出現(xiàn)三個(gè)參賽者A，B，C，滿(mǎn)足A勝B，B勝C，C勝A的充分必要條件是 w＋w＋…＋w＜． 5．亞洲區(qū)足球小組賽，每組有4個(gè)隊(duì)，進(jìn)行循環(huán)賽，每?jī)蓚€(gè)隊(duì)賽一場(chǎng)，勝者得3分，負(fù)者得0分，平局各得1分，賽完后，得分最高的前兩名出線(xiàn)．如果幾個(gè)隊(duì)得分相同，那么便抽簽決定這些隊(duì)的名次，問(wèn)一個(gè)隊(duì)至少要得多少分，才能保證一定出線(xiàn)？ 6．條件同上題，問(wèn)一個(gè)隊(duì)

30、如果出了線(xiàn)，它至少得了多少分？ 7．在88棋盤(pán)上填入1～64的所有整數(shù)，每格一數(shù)，每數(shù)只填一次， 證明：總可以找到兩個(gè)相鄰的方格（具有公共邊的兩個(gè)方格叫相鄰）， 在此兩個(gè)方格中填入的數(shù)的差不小于5？ 8．平面上有n條直線(xiàn)，把平面分成若干個(gè)區(qū)域.證明:用兩色就足以使相鄰的區(qū)域都涂上不同的顏色. 9．在某個(gè)國(guó)家，任意兩個(gè)城市之間用下列交通工具之一進(jìn)行聯(lián)絡(luò)：汽車(chē)，火車(chē)和飛機(jī)．已知沒(méi)有一個(gè)城市擁有這三種交通工具，并且不存在這樣三個(gè)城市，其中任意兩個(gè)在聯(lián)絡(luò)時(shí)都用同一種交通工具．而且這個(gè)國(guó)家用了這三種工具．這個(gè)國(guó)家最多有多少個(gè)城市？(1981年保加利亞，美國(guó)數(shù)學(xué)競(jìng)賽) 10．一個(gè)大三角形的三個(gè)頂點(diǎn)

31、分別涂紅、黑、蘭三色，在三角形內(nèi)部取若干點(diǎn)也任意涂紅、黑、蘭三色之一，這些點(diǎn)間連有一 些線(xiàn)段，把大三角形分成若干互相沒(méi)有重疊部分的一些小三角形.求證:不論怎樣涂，都有一個(gè)小三角形，其三個(gè)頂點(diǎn)涂的顏色全不同. 11．證明：在2色K6中一定存在兩個(gè)同色三角形（即同色K3）． 12．某個(gè)國(guó)家有21個(gè)城市，由若干個(gè)航空公司擔(dān)負(fù)著這些城市之間的空運(yùn)任務(wù)．每家公司都在5個(gè)城市之間設(shè)有直達(dá)航線(xiàn)(無(wú)需著陸，且兩城市間允許有幾家航空公司的航線(xiàn))，而每?jī)蓚€(gè)城市之間都至少有一條直達(dá)航線(xiàn)．問(wèn)至少應(yīng)有多少家航空公司？(1988年前蘇聯(lián)數(shù)學(xué)競(jìng)賽) 本節(jié)“情景再現(xiàn)”解答： 1．解 如圖的5個(gè)點(diǎn)即不存在同色三角形

32、，故例2中把6個(gè)人改為5個(gè)人后，結(jié)論可能不再成立． 2．證明 計(jì)算每個(gè)頂點(diǎn)引出的邊的條數(shù)(次數(shù))，如果每個(gè)頂點(diǎn)的次數(shù)都≤2，則統(tǒng)計(jì)得到的邊數(shù)≤2n，但每條邊都被統(tǒng)計(jì)過(guò)2次，故應(yīng)統(tǒng)計(jì)得到邊數(shù)=2(n+1)．矛盾．故至少有一個(gè)頂點(diǎn)，其次數(shù)≥3． 3．解 ⑴點(diǎn)A：出次3，入次1；點(diǎn)B：出次1，入次1；點(diǎn)C：出次0，入次2；點(diǎn)D：出次1，入次1． R J ⑵ 出次的和=3+1+0+1=5；入次的和=1+1+2+1=5． 出次的和=入次的和． ⑶證明 由于每條弧起點(diǎn)所是出次的點(diǎn)，終點(diǎn)都是入次的點(diǎn)，故出次和與入次和相等，都等于弧的條數(shù)． A B C D 4．解 不一定，例如右面的一

33、個(gè)圖中，就沒(méi)有兩個(gè)點(diǎn)的出次相同．A、B、C、D四點(diǎn)的出次依次為3，2，1，0． 一般的n個(gè)點(diǎn)的競(jìng)賽圖中，可以出現(xiàn)n個(gè)點(diǎn)的出次分別為n－1，n－2，n－3，…，2，1，0這n個(gè)值，于是不一定有兩個(gè)點(diǎn)的出次相同． 5．解 S中有3個(gè)元素是可以的，a→b→c→a．滿(mǎn)足要求． 若S至少有4個(gè)元素，取其中4點(diǎn)，由⑴， S中每?jī)牲c(diǎn)間都要連出1條有向線(xiàn)段，4點(diǎn)間連出6條有向線(xiàn)段．每條有向線(xiàn)段都記一個(gè)出次，共有6個(gè)出次．因此至少有一個(gè)點(diǎn)至少有2個(gè)出次．設(shè)a→b，a→c，則無(wú)論b→c或是c→b均引出矛盾．即S的元素個(gè)數(shù)≤3．故S最多有3個(gè)元素． 6．證明 ⑴ 設(shè)共有n個(gè)點(diǎn)，由于各點(diǎn)出次互不相等，故這n

34、個(gè)點(diǎn)的出次取得0，1，2，…，n－1這n－1個(gè)值中的每個(gè)值． 把出次為0的點(diǎn)排在最后，其余各點(diǎn)均到達(dá)此點(diǎn)．出次為1的點(diǎn)必到達(dá)此點(diǎn)，由于出次為1的點(diǎn)只到達(dá)1個(gè)點(diǎn)，故出次為1的點(diǎn)只到達(dá)出次為0的點(diǎn)，把出次為1的點(diǎn)排在倒數(shù)第二位；再考慮出次為2的點(diǎn)，由于此點(diǎn)只到達(dá)2個(gè)點(diǎn)，故它只到達(dá)已排的兩個(gè)點(diǎn)而不能到達(dá)其余的點(diǎn)，把出次為2的點(diǎn)排在倒數(shù)第3位；……，依此類(lèi)推，把出次為k的點(diǎn)排在倒數(shù)第k+1位，直到出次為n－1的點(diǎn)排在第1位．這就得到滿(mǎn)足題目要求的排法． ⑵ 反設(shè)圖中所有各點(diǎn)的出次均互不相等，則由上題，可把這些點(diǎn)排成一列，使前面的點(diǎn)到達(dá)后面的點(diǎn)．而后面的點(diǎn)不能到達(dá)前面的點(diǎn)，于是該圖中沒(méi)有回路，與已知

35、此圖有回路矛盾．故必有兩點(diǎn)出次相等． 7．解 先證明：任意4人中都有1人與其余n－1人認(rèn)識(shí)． 用n個(gè)點(diǎn)表示這n個(gè)人，若兩個(gè)人認(rèn)識(shí)，則在表示這兩個(gè)人的點(diǎn)間連一條實(shí)線(xiàn)，否則連一條虛線(xiàn)． 設(shè)任取4人v1、v2、v3、v4，其中v1與v2、v3、v4都認(rèn)識(shí)，但此四人中無(wú)人與n－1人都認(rèn)識(shí)．即每個(gè)點(diǎn)都有與之不相鄰的點(diǎn)．設(shè)與v1、v2、v3、v4不相鄰的點(diǎn)分別為v1?、v2?、v3?、v4?，顯然v1?≠v2，v2?≠v1，若v1?≠v2?，則四點(diǎn)v1、v2、v1?、v2?不滿(mǎn)足題意．于是v1?=v2?，同理v1?=v3?，于是得v1?=v2?=v3?，此時(shí)v1、v2、v3、v1?這四點(diǎn)仍不滿(mǎn)足已知

36、條件．故證． 又證 設(shè)圖G中度數(shù)小于n－1的點(diǎn)為v1、v2、…、vk，記F={v1、v2、…、vk}，用實(shí)線(xiàn)表示相鄰(認(rèn)識(shí))，用虛線(xiàn)表示不相鄰． 若k＜4，則命題正確(因?yàn)閳D中找不到4個(gè)人，他們中任1人都沒(méi)有與其余n－1人認(rèn)識(shí))． 若k≥4，由于vk+1、vk+2、…、vn的度數(shù)都=n－1，故與v1不相鄰的點(diǎn)都在F中，設(shè)為v2，此時(shí)若還能找到v3、v4∈F，且v3與v4不相鄰．則此四人不滿(mǎn)足題目要求(圖7⑴)．若在F中除v1、v2外無(wú)不相鄰的人，則v3、…、vk均至少與v1、v2中某一人不相鄰．則如圖⑵、⑶，亦與已知矛盾．故k≥4不可能．故證． 再考慮本題：把1982個(gè)人中的任意4人組

37、成一組，該組中必有1人認(rèn)識(shí)其余所有的人．去掉這個(gè)人，在余下的人中再任取4人，又成一組，又可找出一個(gè)認(rèn)識(shí)其余所有人的人；…，這樣一直做下去．直到余下3人為止，此3人可能與其余的人不全認(rèn)識(shí)． 故至少有1979人認(rèn)識(shí)其余所有的人． 8．解 ⑴用10個(gè)點(diǎn)表示這10個(gè)人，如果某2人互相認(rèn)識(shí)，則在表示這兩人的點(diǎn)間連1條線(xiàn)． 即任3點(diǎn)都至少連了1條線(xiàn)，要求證明存在一個(gè)K4． 設(shè)不存在K4，即任意4點(diǎn)中總有2點(diǎn)沒(méi)有連線(xiàn)， ① 設(shè)某一點(diǎn)A與4點(diǎn)都沒(méi)有連線(xiàn)，則由假設(shè)此4點(diǎn)中有2點(diǎn)未連線(xiàn)，則此2點(diǎn)與A共3點(diǎn)均未連線(xiàn)，與題設(shè)矛盾．故A至多與3點(diǎn)未連線(xiàn)，即至少與6點(diǎn)連了線(xiàn)． ② 設(shè)A與A1、A2、…，A6連

38、線(xiàn)，則A1，…，A6中任意3點(diǎn)必有2點(diǎn)未連線(xiàn)，否則存在K4， ③ 設(shè)A1與Bi、Bj、Bk都未連線(xiàn)，則Bi、Bj、Bk間若有兩點(diǎn)未連線(xiàn)，則出現(xiàn)3點(diǎn)，都未連線(xiàn)，與已知矛盾．故此三點(diǎn)間都連了線(xiàn)，于是此三點(diǎn)與A成為K4． ④ 由③知A1，…，A6中任一點(diǎn)至多與其余5點(diǎn)中的2點(diǎn)未連線(xiàn)．即與其余5點(diǎn)中至少3點(diǎn)連了線(xiàn)．設(shè)A1與A2、A3、A4連了線(xiàn)．此時(shí)A2、A3、A4間至少連了1條線(xiàn)，設(shè)A2A3連了線(xiàn)，則A、A1、A2、A3成為K4． 由上證可知，不存在K4的假設(shè)不成立． ⑵ 若有某點(diǎn)連出6條線(xiàn)，則如上證． 若每點(diǎn)連線(xiàn)數(shù)＜6，當(dāng)每點(diǎn)連線(xiàn)數(shù)都=5時(shí)．此時(shí)9個(gè)點(diǎn)連線(xiàn)統(tǒng)計(jì)為45，為奇數(shù)．不可能．

39、若有某點(diǎn)連線(xiàn)數(shù)＜5，即該點(diǎn)至少與4點(diǎn)未連線(xiàn)，則如上①，矛盾．從而必有點(diǎn)連線(xiàn)數(shù)＝6的點(diǎn)． “習(xí)題67”解答： A B C D E F G 1．解 一個(gè)點(diǎn)經(jīng)過(guò)兩條弧就能到達(dá)的點(diǎn)至多有4個(gè)．經(jīng)過(guò)一條弧或兩條弧就能到達(dá)的點(diǎn)至多有6個(gè)．如圖，每個(gè)點(diǎn)的出次都是2，點(diǎn)A經(jīng)過(guò)1條弧能到達(dá)B、C，點(diǎn)B、C分別經(jīng)過(guò)1條弧可以到達(dá)D、E、F、G，故點(diǎn)A經(jīng)過(guò)1條或2條弧可以到達(dá)至多6個(gè)點(diǎn)．其中如果有些點(diǎn)重合，則點(diǎn)A可以到達(dá)的點(diǎn)就少于6個(gè)． 2．證明 取出次最多的點(diǎn)為A，則A的出次≥(n－1)．他可以經(jīng)一條線(xiàn)到達(dá)的點(diǎn)為B1，B2，…，Bm，m≥(n－1)．對(duì)于A不能到達(dá)的點(diǎn)C，若B1，B2，…，

40、Bm中沒(méi)有點(diǎn)到達(dá)C，則不能到達(dá)C的點(diǎn)至少有m+1個(gè)，即C的出次比A多，與A為出次最多的點(diǎn)矛盾．故所有A不能到達(dá)的點(diǎn)，都可經(jīng)2條線(xiàn)到達(dá)．故證． 3．證明 k＝1時(shí)，若w1≠n－1，則w1＜n－1． 設(shè)w1＝n－1，即w1到達(dá)所有其余的點(diǎn)．把出次為w1的點(diǎn)去掉，這對(duì)余下的點(diǎn)的出次都不受影響．此時(shí)就得到一個(gè)只有n－1個(gè)點(diǎn)的競(jìng)賽圖．若w2≠n－2，則w2＜n－2． 設(shè)w1＝n－1，w2＝n－2，同上兩次去掉出次為w1，w2的點(diǎn)，則得到一個(gè)有n－2個(gè)點(diǎn)的競(jìng)賽圖．其中每個(gè)點(diǎn)的出次≤n－3．于是若w3≠n－3，就有w3＜n－3． 依此類(lèi)推，若各點(diǎn)的出次為w1≥w2≥…≥wn．如果w1＝n－1，w2＝

41、n－2，…，wk－1＝n－(k－1)，但wk≠n－k(1≤k≤n)，則依次去掉k－1個(gè)點(diǎn)，而不影響余下點(diǎn)的出次，此時(shí)余下點(diǎn)的出次≤n－(k－1)－1＝n－k．若wk≠n－k，則必有wk＜n－k．證畢． 4．⑴證明 設(shè)A與B出次相等，由于A、B必連有線(xiàn)，不妨設(shè)A勝B，于是A、B的出次不為0．取所有負(fù)于B的點(diǎn)集M，設(shè)此集中有k個(gè)點(diǎn)，其中k必大于0．于是負(fù)于A的點(diǎn)集中也有k個(gè)點(diǎn)，若M中沒(méi)有點(diǎn)勝A，則M中的點(diǎn)均負(fù)于A，于是A勝M(fèi)中所有點(diǎn)且勝B，即A的出次至少比B多1，與A、B出次相等矛盾．故M中必有點(diǎn)C，C勝A，于是A勝B，B勝C，C勝A．證畢． ⑵證明：不論何種比賽結(jié)果，所有參賽者出次的和都等

42、于1＋2＋…＋(n－1)＝n(n－1)． 若每個(gè)參賽者的出次都互不相同，則出次分別為0，1，2，…，n－1．此時(shí)不存在滿(mǎn)足“A勝B，B勝C，C又勝A”的三個(gè)參賽者． 此時(shí)w＋w＋…＋w＝02+12+…+(n－1)2＝． 當(dāng)有兩個(gè)參賽者的出次相同時(shí)，就存在三角形回路．設(shè)出次為wk的點(diǎn)為Ak． 設(shè)w1≥w2≥…≥w1．且設(shè)w1＝n－1，…，wk－1＝n－(k－1)，但wk≠n－k，則wk＜n－k，逐個(gè)把A1，A2，…，Ak－1去掉，這樣做不會(huì)影響剩下點(diǎn)的出次．這樣去掉點(diǎn)后，余下點(diǎn)中必有引向Ak的線(xiàn)，設(shè)從Aj(j>k)有引向Ak的線(xiàn)，把這條線(xiàn)的方向改變，則Ak的出次變?yōu)閣k+1，而Aj的出次

43、變?yōu)閣j－1．此時(shí)(wk＋1)2＋(wj－1)2＝w＋w＋2(wk－wj)＋2＞w＋w，即這樣操作可使和w＋w＋…＋w增加，繼續(xù)這樣做，直到使wk＝n－k，這時(shí)去掉wk，再做下去，直到每個(gè)wi都等于n－(i－1)(i＝1，2，…，n)為止．此時(shí)和式w＋w＋…＋w已嚴(yán)格遞增至．這說(shuō)明w＋w＋…＋w＜成立． 5．解 共計(jì)比賽6場(chǎng)，最多共可得18分．若有三個(gè)隊(duì)都是二勝一負(fù)得6分(如圖中A、B、C隊(duì))，則不能保證一定出線(xiàn)(因要抽簽才能決定是否出線(xiàn))． 若一個(gè)隊(duì)得7分，則保證一定出線(xiàn)，因不可能有三個(gè)隊(duì)至少得7分，否則73=21>18．故得分不少于7分的至多有2個(gè)隊(duì)．故得到7分一定能出線(xiàn)． A

44、B C D 6．解 若三個(gè)隊(duì)都互相打成平局，都輸給另一隊(duì)(圖中B、C、D三隊(duì))，則此三個(gè)隊(duì)都得2分，其中有一個(gè)隊(duì)出線(xiàn)． 若某隊(duì)只得1分，則該隊(duì)1平2負(fù)，贏該隊(duì)的兩個(gè)隊(duì)都至少得了3分，于是名次都在該隊(duì)之前，該隊(duì)不可能出線(xiàn)． 即某個(gè)隊(duì)出線(xiàn)了，則該隊(duì)至少得了2分． 7．解 把相鄰的兩格中心用一條邊相連，于是就有一個(gè)8行，每行8個(gè)點(diǎn)的圖，從88棋盤(pán)的左上角一格到右下角一格需要經(jīng)過(guò)14條邊，如果所有相鄰方格中填入數(shù)的差小于5，則由于連填“1”的格與填“64”的格之間的路至多經(jīng)過(guò)14條邊．于是這兩格中數(shù)的差不會(huì)超過(guò)144=56.但64－1=63．矛盾．故結(jié)論成立． 8．證明 當(dāng)n＝1時(shí)，1條

45、直線(xiàn)把平面分成兩部分，用兩色可以區(qū)分這兩部分，如果增加1條直線(xiàn)，可以把這條直線(xiàn)某一旁的區(qū)域中原來(lái)涂的顏色變成另一種顏色．則所有相鄰的區(qū)域涂色都不同．以后每多畫(huà)出1條線(xiàn)都把線(xiàn)一旁的部分的每個(gè)區(qū)域中顏色重涂成與原來(lái)不同的顏色，就可使相鄰區(qū)域涂色不同． 9．解 設(shè)共有n個(gè)城市，每?jī)蓚€(gè)城市之間連一條線(xiàn)，每條線(xiàn)染三種顏色之一．例如：汽車(chē)用紅色，火車(chē)用藍(lán)色，飛機(jī)用黃色．已知沒(méi)有任何一點(diǎn)引出3種顏色的線(xiàn)．且不存在同色三角形． 首先證明：任一點(diǎn)不能連出3條同色線(xiàn)，否則，設(shè)AB、AC、AD連紅線(xiàn)，則B、C、D間都不能連紅線(xiàn)．設(shè)BC連藍(lán)線(xiàn)，由于B只能連出兩種顏色，故BD只能是藍(lán)色線(xiàn)，此時(shí)，C、D都連了紅藍(lán)兩色

46、線(xiàn)，它們之間無(wú)論連紅線(xiàn)還是藍(lán)線(xiàn)均出現(xiàn)同色三角形． 于是每點(diǎn)引出的同色線(xiàn)不超過(guò)2條，線(xiàn)的顏色不超過(guò)2種，即不能超過(guò)4條線(xiàn)．即城市數(shù)≤5． 若城市數(shù)＝5．由于每點(diǎn)都引出某色線(xiàn)2條，另一色線(xiàn)2條，設(shè)AB、AC紅色，AD、AE藍(lán)色，由于B應(yīng)引出2條紅色，現(xiàn)BA紅，故還要引出1條紅線(xiàn)，BC不能紅色(出現(xiàn)同色三角形)，故BE紅．由于EA、EB一紅一藍(lán)，故E應(yīng)引出2紅2藍(lán)，由于ED不能藍(lán)，故ED紅．EC藍(lán)，此時(shí)C、D都用了2色，從而它們也只能用紅藍(lán)兩色，于是B也只能用紅藍(lán)兩色，與要用3色矛盾． 若城市數(shù)＝4．可以構(gòu)成滿(mǎn)足條件的圖． 10．解法1 按頂點(diǎn)顏色分類(lèi)，三角形共有10類(lèi)：三紅，兩紅一藍(lán)，兩紅

47、一黑，一紅兩藍(lán)，一紅兩黑，紅藍(lán)黑，三藍(lán)，兩藍(lán)一黑，一藍(lán)兩黑，三黑．按線(xiàn)段兩端顏色分類(lèi)，線(xiàn)段共有6類(lèi)：紅紅，紅藍(lán)，紅黑，藍(lán)藍(lán)，藍(lán)黑，黑黑． 現(xiàn)在統(tǒng)計(jì)兩端分別為紅、藍(lán)的邊，在兩紅一藍(lán)或兩藍(lán)一紅這兩類(lèi)三角形中，每個(gè)三角形都有2條紅藍(lán)邊，每個(gè)紅藍(lán)黑三角形都有1條紅藍(lán)邊，設(shè)前兩類(lèi)三角形共有p 個(gè)，后一類(lèi)三角形共有q個(gè)．則兩端紅藍(lán)的邊共有2p＋q條． 而每條兩端紅藍(lán)的邊，在大三角形內(nèi)的紅藍(lán)邊設(shè)有k條，每條都被計(jì)算了2次，大三角形的紅藍(lán)邊有1條，計(jì)算了1次．故 2p＋q＝2k＋1，于是q≠0，即紅藍(lán)黑三角形至少有1個(gè)． 解法2 在每個(gè)劃出的小三角形內(nèi)取一個(gè)點(diǎn)，在三角形形外也取一個(gè)點(diǎn)．如果兩個(gè)三角形有

48、一條紅藍(lán)的公共邊，則在相應(yīng)點(diǎn)間連一條線(xiàn)．于是得到了圖G，此時(shí)，兩紅一藍(lán)或兩藍(lán)一紅的三角形都是圖G的偶頂點(diǎn)，而紅藍(lán)黑三角形則對(duì)應(yīng)著圖G的奇頂點(diǎn)，大三角形外的那個(gè)頂點(diǎn)也是奇頂點(diǎn)，由奇頂點(diǎn)的成對(duì)性，知圖G中至少還有一個(gè)奇頂點(diǎn)，于是，至少還有一個(gè)紅藍(lán)黑三角形． 11．證明：每個(gè)異色K3的三個(gè)角中必有兩個(gè)角的兩邊異色，即每個(gè)異色三角形對(duì)應(yīng)2個(gè)異色角．反之每個(gè)異色角都在一個(gè)異色三角形內(nèi)．設(shè)第i個(gè)頂點(diǎn)引出了xi(0≤xi≤5，i=1，2，3，4，5，6)條紅邊，5－xi條藍(lán)邊．則該頂點(diǎn)為頂點(diǎn)的異色角共有xi(5－xi)個(gè)．當(dāng)xi=2或3時(shí)xi(5－xi)=6取得最大值．故異色三角形數(shù)≤662=18個(gè)．

49、但K6中共可連出C=20個(gè)三角形，即至少有20－18=2個(gè)同色三角形． 存在只有2個(gè)同色三角形的二染色K6，把6點(diǎn)分成兩組，每組3點(diǎn)，同組連紅線(xiàn)，不同組連藍(lán)線(xiàn)．由于任取三點(diǎn)，必有兩點(diǎn)同組，于是必有紅線(xiàn)，但如有不同組的點(diǎn)，則必有藍(lán)線(xiàn)． 12．解 共有C=210條航線(xiàn)，而每個(gè)航空公司有C=10條航線(xiàn)，故至少要21家航空公司． 畫(huà)一個(gè)21邊形，用頂點(diǎn)表示城市，依次編為1~21號(hào)．取一個(gè)五邊形它可以由連1，3，8，9，12這五個(gè)點(diǎn)而成．其邊及對(duì)角線(xiàn)分別對(duì)著分圓為1，2，3，4，5，6，7，8，9，11等分的?。@個(gè)五邊形的邊長(zhǎng)互不重復(fù)，且含有了該正21邊形的邊及對(duì)角線(xiàn)的所有長(zhǎng)度．讓這個(gè)五邊形每次旋轉(zhuǎn)1等分，旋轉(zhuǎn)k次所在的五個(gè)點(diǎn)即為第k家公司所在的城市．每個(gè)長(zhǎng)度的對(duì)角線(xiàn)總會(huì)在某次旋轉(zhuǎn)中出現(xiàn)．于是相應(yīng)城市間的航線(xiàn)存在． - 12 -