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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

32、，故例2中把6個人改為5個人后，結(jié)論可能不再成立． 2．證明 計算每個頂點(diǎn)引出的邊的條數(shù)(次數(shù))，如果每個頂點(diǎn)的次數(shù)都≤2，則統(tǒng)計得到的邊數(shù)≤2n，但每條邊都被統(tǒng)計過2次，故應(yīng)統(tǒng)計得到邊數(shù)=2(n+1)．矛盾．故至少有一個頂點(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、個圖中，就沒有兩個點(diǎn)的出次相同．A、B、C、D四點(diǎn)的出次依次為3，2，1，0． 一般的n個點(diǎn)的競賽圖中，可以出現(xiàn)n個點(diǎn)的出次分別為n－1，n－2，n－3，…，2，1，0這n個值，于是不一定有兩個點(diǎn)的出次相同． 5．解 S中有3個元素是可以的，a→b→c→a．滿足要求． 若S至少有4個元素，取其中4點(diǎn)，由⑴， S中每兩點(diǎn)間都要連出1條有向線段，4點(diǎn)間連出6條有向線段．每條有向線段都記一個出次，共有6個出次．因此至少有一個點(diǎn)至少有2個出次．設(shè)a→b，a→c，則無論b→c或是c→b均引出矛盾．即S的元素個數(shù)≤3．故S最多有3個元素． 6．證明 ⑴ 設(shè)共有n個點(diǎn)，由于各點(diǎn)出次互不相等，故這n

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

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

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

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

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

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

40、Bm中沒有點(diǎn)到達(dá)C，則不能到達(dá)C的點(diǎn)至少有m+1個，即C的出次比A多，與A為出次最多的點(diǎn)矛盾．故所有A不能到達(dá)的點(diǎn)，都可經(jīng)2條線到達(dá)．故證． 3．證明 k＝1時，若w1≠n－1，則w1＜n－1． 設(shè)w1＝n－1，即w1到達(dá)所有其余的點(diǎn)．把出次為w1的點(diǎn)去掉，這對余下的點(diǎn)的出次都不受影響．此時就得到一個只有n－1個點(diǎn)的競賽圖．若w2≠n－2，則w2＜n－2． 設(shè)w1＝n－1，w2＝n－2，同上兩次去掉出次為w1，w2的點(diǎn)，則得到一個有n－2個點(diǎn)的競賽圖．其中每個點(diǎn)的出次≤n－3．于是若w3≠n－3，就有w3＜n－3． 依此類推，若各點(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個點(diǎn)，而不影響余下點(diǎn)的出次，此時余下點(diǎn)的出次≤n－(k－1)－1＝n－k．若wk≠n－k，則必有wk＜n－k．證畢． 4．⑴證明 設(shè)A與B出次相等，由于A、B必連有線，不妨設(shè)A勝B，于是A、B的出次不為0．取所有負(fù)于B的點(diǎn)集M，設(shè)此集中有k個點(diǎn)，其中k必大于0．于是負(fù)于A的點(diǎn)集中也有k個點(diǎn)，若M中沒有點(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)． 若每個參賽者的出次都互不相同，則出次分別為0，1，2，…，n－1．此時不存在滿足“A勝B，B勝C，C又勝A”的三個參賽者． 此時w＋w＋…＋w＝02+12+…+(n－1)2＝． 當(dāng)有兩個參賽者的出次相同時，就存在三角形回路．設(shè)出次為wk的點(diǎn)為Ak． 設(shè)w1≥w2≥…≥w1．且設(shè)w1＝n－1，…，wk－1＝n－(k－1)，但wk≠n－k，則wk＜n－k，逐個把A1，A2，…，Ak－1去掉，這樣做不會影響剩下點(diǎn)的出次．這樣去掉點(diǎn)后，余下點(diǎn)中必有引向Ak的線，設(shè)從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已嚴(yán)格遞增至．這說明w＋w＋…＋w＜成立． 5．解 共計比賽6場，最多共可得18分．若有三個隊都是二勝一負(fù)得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負(fù)，贏該隊的兩個隊都至少得了3分，于是名次都在該隊之前，該隊不可能出線． 即某個隊出線了，則該隊至少得了2分． 7．解 把相鄰的兩格中心用一條邊相連，于是就有一個8行，每行8個點(diǎn)的圖，從88棋盤的左上角一格到右下角一格需要經(jīng)過14條邊，如果所有相鄰方格中填入數(shù)的差小于5，則由于連填“1”的格與填“64”的格之間的路至多經(jīng)過14條邊．于是這兩格中數(shù)的差不會超過144=56.但64－1=63．矛盾．故結(jié)論成立． 8．證明 當(dāng)n＝1時，1條

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

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

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

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

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