《提優(yōu)教程》2012江蘇省高中數學 第67講 圖論問題一競賽教案

《《提優(yōu)教程》2012江蘇省高中數學 第67講 圖論問題一競賽教案》由會員分享，可在線閱讀，更多相關《《提優(yōu)教程》2012江蘇省高中數學 第67講 圖論問題一競賽教案（12頁珍藏版）》請在裝配圖網上搜索。

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

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

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

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

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

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

7、)， 證明 w＋w＋…＋w＝e＋e＋…＋e． 分析 根據競賽圖的特點可知：⑴ 每點的出次與入次的和都等于n－1，⑵ 所有點的出次的和與入次的和相等．由此可以推出：所有點的出次和與入次和都等于n(n－1)．這是兩個基本的性質．在要證的式子中把ek用n－1－wk代替． 證明 對于每個點，出次與入次的和都是n－1，即 wk＋ek＝n－1(k＝1，2，…，n)， ① 所有出次的和與所有入次的和相等，且都等于圖中弧的條數： 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． 說明 本題的證明方法與《奇偶分析》中的例6相似． 例4 平面上給定7個點，用一些線段連接它們，每三個點中至少有兩點相連，問至少要有多少條線段？試給出一個圖．(1989蒙古數學競賽) 分析 首先找到連線條數的下界(即至少要連出多少條線)，再尋找是否可能達到這個下界，可以分別枚舉可能的連線方法，討論每種方法的連線條數，得到最小的結果． 解 7個點中共有三點組C=35個．每條線段共與其余5點組成5個三角形．故線段條數≥＝7條． 如果有

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

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

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

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

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

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

15、6個點不相鄰，故此8個點都至少連了(14－6－1＝)7條邊，于是此8點中的每個點又都新連了至少2條邊，故又新連出了822＝8條邊(除以2是因為每條邊可能在兩個點端點處被計算了2次)．這與只連了6條邊矛盾，所以存在S中的一點v2，至少與7個點不相鄰． 但8+7＝15＞14，必有一點v3與v1，v2均未連線．此三點即為所求． 鏈接 v3存在是根據容斥原理：把這14個人的集合記為S，與v1相鄰的點集記為A，與v2相鄰的點集記為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)， 現card(A)＋card(B)＝15，card(S)＝14，于是card(A∩B)＞0． 情景再現 A B C D 3．⑴右面的有向圖由4個頂點及一些弧(有向線段)組成，指出各點的出次(引出的弧的條數)與入次(引入的弧的條數)． ⑵求出上題中所有各點的出次的和與入次的和，它們與弧的條數有什么關系？ ⑶證明：任一有向圖中，出次的和與入次的和相等． 4．在n(n≥3)個點的競賽圖中，一定有兩個點的出次相同嗎？ 5．在集合S的元素之間引入關系“→”．⑴ 對于任意兩個元素a，b∈S，要么a→b，要么b→

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

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

19、只賽1場的隊已經與比賽30場的隊賽過1場，故不再與其它隊比賽)的隊不比賽外，與其余各隊都比賽，故它與比賽1場的隊同城；依次類推，知比賽k場的隊與比賽30－k場的隊同城，這樣，把各城都配對后，只有比賽15場的隊沒有與其余的隊同城，故比賽15場的隊就是A城乙隊．即A城乙隊比賽了15場． 說明 有些題的已知條件討論起來頭緒紛繁，如果利用圖來討論則可以化繁為簡．利用點與線的相鄰與否來研究這一類題目需要一定的技巧，也需要相當的抽象概括能力與邏輯推理能力．請大家多做些練習． 例8 n(n＞3)名乒乓球選手單打若干場后，任意兩個選手已賽過的對手恰好都不完全相同，試證明：總可以從中去掉一名選手，而使在

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

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

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

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

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

25、圖稱為樹．n階樹可以記為Tn．在一個圖中，次數為1的頂點稱為懸掛點． 定理1 如果樹T的頂點數≥2，那么，它至少有兩個懸掛點． 從樹的任何一個頂點出發(fā)，沿某個方向前進，已走過的邊不重復走，由于樹是無圈的，故每個頂點至多走過1次，如果，經過的一個頂點不是懸掛點，則還可以前進到下一個頂點，由于樹的頂點只有有限個，故前進到某個頂點(如果圖中共有n個頂點，則至多前進n－1步)后就無法再繼續(xù)前進，即到達一個次數為1的頂點．此頂點即為一個懸掛點．再從此懸掛點出發(fā)，沿鏈走一次(第一步是按剛才的反方向前進)，則又可以到達一個懸掛點．此懸掛點與剛才第一個懸掛點不同．即圖中至少有兩個懸掛點． 定理2一個n階

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

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

28、數學競賽) 8．⑴在一所房子里有10個人，其中任意3人中至少有2人互相認識，證明：其中有4人，他們任意2人都互相認識．(1980英國數學競賽) ⑵如果把⑴中的數10改為9，結論仍成立否？(1977年波蘭數學競賽) 習題13 1．如果每個點的出次都是2，那么，一個點經過兩條弧就可以到達的點至多有幾個？經過一條弧或兩條弧可以到達的點至多有幾個？ 2．在競賽圖中必有一個點，從它到其它的頂點，只需經過一條弧或兩條?。? 3．一個有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．⑴ 如果在點數n≥3的競賽圖中，有兩個點的出次相等．證明，圖中必有三角形回路(即有三個選手A、B、C，其中A勝B，B勝C，C又勝A)． ⑵ 在一個n人參加的循環(huán)賽中，每兩人比賽一場，如果沒有平局，參賽者贏的場數分別是w1，w2，…，wn．求證：出現三個參賽者A，B，C，滿足A勝B，B勝C，C勝A的充分必要條件是 w＋w＋…＋w＜． 5．亞洲區(qū)足球小組賽，每組有4個隊，進行循環(huán)賽，每兩個隊賽一場，勝者得3分，負者得0分，平局各得1分，賽完后，得分最高的前兩名出線．如果幾個隊得分相同，那么便抽簽決定這些隊的名次，問一個隊至少要得多少分，才能保證一定出線？ 6．條件同上題，問一個隊

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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