第67講-圖論問題(一)

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

2、確定了線的兩個(gè)端點(diǎn)中一個(gè)為“起點(diǎn)”，另一個(gè)為“終點(diǎn)”這時(shí)，線是點(diǎn)的“有序?qū)Α?，則得到“有向圖”；對有向圖的一個(gè)頂點(diǎn)v，degvk，若v是其中n條邊的起點(diǎn)，m條邊的終點(diǎn)(mnk)，則稱v的出次為n，入次為m鏈：若在一個(gè)圖G(V；E)中取n+1個(gè)頂點(diǎn) v1、v2、vn+1，每兩個(gè)相鄰的頂點(diǎn)vi、vi+1間連有一條邊li,則邊l1,l2,ln就稱為從v1到vn+1的一條鏈n稱為鏈的長度A類例題例1 證明任意的六人中一定有三個(gè)人互相認(rèn)識或互不認(rèn)識(約定甲認(rèn)識乙就意味著乙認(rèn)識甲) K6的邊染成紅藍(lán)兩色，求證：其中必有兩個(gè)三角形，其三邊同色分析 以點(diǎn)表示人，連紅、藍(lán)兩色的線分別表示“認(rèn)識”與“不認(rèn)識”，

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

4、則v1v2v3是紅色三角形)，如果這三點(diǎn)間都不連紅線，則出現(xiàn)藍(lán)色三角形(v2v3v4是藍(lán)色三角形)故證 考慮K6共連了C15條線，共得到C20個(gè)三角形設(shè)第i個(gè)頂點(diǎn)連了ri(0i5)條紅線，5ri條藍(lán)線由于ri(5ri)6所以，連出的異色角個(gè)數(shù)6×636個(gè)由于每個(gè)異色的三角形有2個(gè)異色角，所以圖中異色三角形個(gè)數(shù)18，故圖中同色三角形個(gè)數(shù)20182說明 題是早期匈牙利的一個(gè)圖論競賽題解這類“實(shí)際問題”時(shí)，重要的是會用圖的語言解釋題意，把實(shí)際問題改寫為圖的問題 用異色角來解相關(guān)問題是較好的方法例2 由5人組成一個(gè)公司，其中任意三人總有2人彼此認(rèn)識，也總有2人彼此不認(rèn)識證明：這五人可以圍桌而

5、坐，使每人兩旁都是他認(rèn)識的人(1978年保加利亞數(shù)學(xué)競賽)證明 用5個(gè)點(diǎn)表示這5個(gè)人，若兩人互相認(rèn)識，則在表示這2個(gè)人的點(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)了以v2、v3、v4為頂點(diǎn)的三角形，矛盾其次，若某點(diǎn)連出了3條線，則此三點(diǎn)間都不能連線，與已知矛盾故知：每點(diǎn)都恰連2條線它不能連成三角形，也不能連成四邊形，否則余下的點(diǎn)無法連線，故只能如圖所示，證畢說明 仔細(xì)體會上述兩例的特點(diǎn)，

6、明白什么時(shí)候應(yīng)該用圖來解相關(guān)的題：當(dāng)涉及多個(gè)元素的某些相互關(guān)系時(shí)，就可能用圖來解釋情景再現(xiàn)1在例1中，把6個(gè)人改為5個(gè)人，結(jié)論是否一定成立？2圖G有n個(gè)頂點(diǎn)，n+1條邊，證明：圖G至少有一個(gè)頂點(diǎn)的次數(shù)3B類例題例3 設(shè)競賽圖(每兩個(gè)點(diǎn)都連了1條線的有向圖)中，點(diǎn)Ak的出次與入次分別為wk與ek(k1，2，n)，證明 wwweee分析 根據(jù)競賽圖的特點(diǎn)可知： 每點(diǎn)的出次與入次的和都等于n1， 所有點(diǎn)的出次的和與入次的和相等由此可以推出：所有點(diǎn)的出次和與入次和都等于n(n1)這是兩個(gè)基本的性質(zhì)在要證的式子中把ek用n1wk代替證明 對于每個(gè)點(diǎn)，出次與入次的和都是n1，即wkekn1(k1，2，n)

7、， 所有出次的和與所有入次的和相等，且都等于圖中弧的條數(shù)：w1w2wne1e2enn(n1)所以 eee(n1w1)2(n1w2)2(n1wn)2n(n1)2www2(w1w2wn)(n1)wwwn(n1)22´(n1)(n1) www說明 本題的證明方法與奇偶分析中的例6相似例4 平面上給定7個(gè)點(diǎn)，用一些線段連接它們，每三個(gè)點(diǎn)中至少有兩點(diǎn)相連，問至少要有多少條線段？試給出一個(gè)圖(1989蒙古數(shù)學(xué)競賽)分析 首先找到連線條數(shù)的下界(即至少要連出多少條線)，再尋找是否可能達(dá)到這個(gè)下界，可以分別枚舉可能的連線方法，討論每種方法的連線條數(shù)，得到最小的結(jié)果解 7個(gè)點(diǎn)中共有三點(diǎn)組C=35個(gè)每條

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

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

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

11、兩人講同一種語言于是相應(yīng)三人可以用同一種語言來對話下面證明存在一點(diǎn)，其度不大于4從而該點(diǎn)至少與4點(diǎn)不相鄰如果degv14，則v1即為所求若degv14，則至少degv15，即至少有5個(gè)點(diǎn)與之連線，設(shè)為v2，v6，由于這些點(diǎn)不能連出三角形，故v2，v6的任何兩個(gè)之間都不能連線，從而v2與v3，v6均無連線，于是degv24即可證得原題說明 兩點(diǎn)間連了1條線，則說這兩點(diǎn)相鄰本題的兩種證明方法從兩個(gè)方向出發(fā)，一種是兩人可用同一種語言通話，就在相應(yīng)兩點(diǎn)間連一條邊，證法2是反過來，兩人不能通話時(shí)則連一條邊，都能應(yīng)用圖解決問題例6 俱樂部里有14個(gè)人想打橋牌，已知過去每個(gè)人都與其中的5個(gè)人合作過，現(xiàn)在規(guī)定

12、4個(gè)人中必須任兩個(gè)人都沒有合作過才準(zhǔn)許在一起打1局橋牌，這樣打了3局就無法再打下去了，如果這時(shí)又來了一人，他與原來的14個(gè)人都沒有合作過，證明：一定可以再打1局分析 打橋牌時(shí)，4人分成合作的兩對，合作的兩人坐在相對的位置打牌于是每局橋牌，都有兩對人合作把題目的條件與結(jié)論都轉(zhuǎn)述為圖的語言，并找出結(jié)論的等價(jià)命題是：找到三個(gè)人互相都沒有合作過，即存在3個(gè)點(diǎn)互不相鄰證明 用14個(gè)點(diǎn)表示這14個(gè)人，若某兩人合作過，則在表示這兩人的點(diǎn)間連一條線，于是，題目條件即：其中每個(gè)點(diǎn)都已連出了5條線，且在此14個(gè)點(diǎn)中，可以找出3組點(diǎn)(每組4個(gè)點(diǎn))，這三組點(diǎn)間，兩兩未連線，若這3組點(diǎn)之間共連出6條線后，對于任意4點(diǎn)，

13、都至少有兩點(diǎn)連了線(14個(gè)點(diǎn)間一共連了41條線)，證明此時(shí)一定存在3個(gè)點(diǎn)，兩兩都沒有連線(從而添入第15個(gè)點(diǎn)后，可與此3點(diǎn)合成4點(diǎn)，兩兩無連線)由于14個(gè)點(diǎn)中的每個(gè)點(diǎn)原來都與(1415)8個(gè)點(diǎn)不相鄰在又打3局連出了6條邊以后，至多有12個(gè)點(diǎ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)都至多與6個(gè)點(diǎn)不相鄰，故此8個(gè)點(diǎn)都至少連了(1461)7條邊，于是此8點(diǎn)中的每個(gè)點(diǎn)又都新連了至少2條邊，故又新連出了8×2÷28條邊(除以2是因?yàn)槊織l邊可能在兩個(gè)點(diǎn)端點(diǎn)

14、處被計(jì)算了2次)這與只連了6條邊矛盾，所以存在S中的一點(diǎn)v2，至少與7個(gè)點(diǎn)不相鄰但8+71514，必有一點(diǎn)v3與v1，v2均未連線此三點(diǎn)即為所求鏈接 v3存在是根據(jù)容斥原理：把這14個(gè)人的集合記為S，與v1相鄰的點(diǎn)集記為A，與v2相鄰的點(diǎn)集記為B，則ABÍS故card(AB)card(S)而 card(AB)card(A)card(B)card(AB)，故 card(A)card(B)card(AB)card(S)，現(xiàn)card(A)card(B)15，card(S)14，于是card(AB)0情景再現(xiàn)ABCD3右面的有向圖由4個(gè)頂點(diǎn)及一些弧(有向線段)組成，指出各點(diǎn)的出次(引出的弧的

15、條數(shù))與入次(引入的弧的條數(shù))求出上題中所有各點(diǎn)的出次的和與入次的和，它們與弧的條數(shù)有什么關(guān)系？證明：任一有向圖中，出次的和與入次的和相等4在n(n3)個(gè)點(diǎn)的競賽圖中，一定有兩個(gè)點(diǎn)的出次相同嗎？5在集合S的元素之間引入關(guān)系“” 對于任意兩個(gè)元素a，bS，要么ab，要么ba，二者有且只有一個(gè)成立； 對任意三個(gè)元素a，b，c，如果ab，bc，則ca問集合S中最多能有多少個(gè)元素？(1972年英國數(shù)學(xué)競賽)6證明： 如果競賽圖中各點(diǎn)的出次不等， 那么可將這些點(diǎn)排成一列，排在前面的點(diǎn)有弧到達(dá)排在后面的任一點(diǎn)(即排在前面的選手勝排在后面的所有選手) 如果點(diǎn)數(shù)n3的競賽圖中有三角形回路，那么，圖中必有兩點(diǎn)的

16、出次相等C類例題例7 某足球賽有16個(gè)城市參加，每市派出2個(gè)隊(duì)，根據(jù)比賽規(guī)則，每兩隊(duì)之間至多賽一場，同城兩隊(duì)之間不進(jìn)行比賽賽過一段時(shí)間后，發(fā)現(xiàn)除A城甲隊(duì)外，其他各隊(duì)已賽過的場數(shù)各不相同問A城乙隊(duì)已賽過幾場?證明你的結(jié)論分析 注意分析“各隊(duì)賽過場次各不相同”的含義，即能推知比賽場次的取值情況再從比賽場次最多的隊(duì)開始討論，與之比賽的隊(duì)是哪些隊(duì)？證明 用32個(gè)點(diǎn)表示這32個(gè)隊(duì)，如果某兩隊(duì)比賽了一場，則在表示這兩個(gè)隊(duì)的點(diǎn)間連一條線否則就不連線由于，這些隊(duì)比賽場次最多30場，最少0場，共有31種情況，現(xiàn)除A城甲隊(duì)外還有31個(gè)隊(duì)，這31個(gè)隊(duì)比賽場次互不相同，故這31個(gè)隊(duì)比賽的場次恰好從0到30都有就在表示

17、每個(gè)隊(duì)的點(diǎn)旁注上這隊(duì)的比賽場次考慮比賽場次為30的隊(duì)，這個(gè)隊(duì)除自己與同城的隊(duì)外，與不同城的隊(duì)都進(jìn)行了比賽，于是，它只可能與比賽0場的隊(duì)同城；再考慮比賽29場的隊(duì)，這個(gè)隊(duì)除與同城隊(duì)及比賽0場、1場(只賽1場的隊(duì)已經(jīng)與比賽30場的隊(duì)賽過1場，故不再與其它隊(duì)比賽)的隊(duì)不比賽外，與其余各隊(duì)都比賽，故它與比賽1場的隊(duì)同城；依次類推，知比賽k場的隊(duì)與比賽30k場的隊(duì)同城，這樣，把各城都配對后，只有比賽15場的隊(duì)沒有與其余的隊(duì)同城，故比賽15場的隊(duì)就是A城乙隊(duì)即A城乙隊(duì)比賽了15場說明 有些題的已知條件討論起來頭緒紛繁，如果利用圖來討論則可以化繁為簡利用點(diǎn)與線的相鄰與否來研究這一類題目需要一定的技巧，也需要

18、相當(dāng)?shù)某橄蟾爬芰εc邏輯推理能力請大家多做些練習(xí)例8 n(n3)名乒乓球選手單打若干場后，任意兩個(gè)選手已賽過的對手恰好都不完全相同，試證明：總可以從中去掉一名選手，而使在余下的選手中，任意兩個(gè)選手已賽過的對手仍然都不完全相同(1987年全國高中數(shù)學(xué)聯(lián)賽)分析 本題的求證暗示要用反證法，設(shè)去掉任一個(gè)選手，都會有兩個(gè)選手賽過的對手完全相同于是這兩人組成一個(gè)點(diǎn)對這樣就會得到n個(gè)點(diǎn)對每個(gè)點(diǎn)對連一條線，n個(gè)點(diǎn)連出了n條線，就可用圖的性質(zhì)得到圈，使問題得證這是證法1的思路每個(gè)選手的對手可以組成集合，研究對手集的性質(zhì)，用最小數(shù)原理來證明，這是證法2的思路證法1 把這些選手編為1至n號，以n個(gè)點(diǎn)表示這n個(gè)人，

19、各點(diǎn)也相應(yīng)編為1至n號反設(shè)去掉任何一個(gè)選手后，都有兩個(gè)選手的已賽過的對手完全相同于是，如果先去掉1號選手，則有兩個(gè)選手的已賽過的對手完全相同，設(shè)為第i號與第j號，在表示此二人的點(diǎn)間連一條線，并在線上注上“1號”這說明，此二人在去掉1號選手之前必是一人與1號賽過，另一人與1號沒有賽過而且不可能在去掉1號后有三人都相同，否則，此三人與1號選手比賽的情況只有兩種：賽過或沒有賽過，如果去掉1號后，此三人的情況完全相同，則去掉1號之前必有2人賽過的對手完全相同(如果去掉1號后有不止一對選手的已賽過對手完全相同，則只任取其中的一對連線，其余的對則不連線)同樣，如果再依次去掉2號、3號，直至n號，每去掉1個(gè)

20、選手，都會在某兩點(diǎn)之間連1條線這樣，就在n個(gè)點(diǎn)間連了n條線且這些線上分別注了1至n號，每條線注了1個(gè)號碼，每個(gè)號碼只注在1條線上由于在10個(gè)點(diǎn)間連了10條線，故圖中必存在一圈現(xiàn)從圈上一點(diǎn)i出發(fā)，經(jīng)過點(diǎn)j、k、最后回到點(diǎn)i注意到點(diǎn)i與點(diǎn)j所代表的兩個(gè)選手中1個(gè)是與1號比賽的，另一個(gè)是沒有與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是對手集中

21、元素最多的的選手若命題不成立，則存在兩個(gè)選手B、C使去掉A后，B、C的對手集相同，由于(B)(C)，故A必屬于(B)與(C)之一不妨設(shè)A(B)，于是，B(A)，CÏ(A)且(C)(B)A(在(B)中去掉它的一個(gè)元素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)，故DA：又D(C)，故D(B)，即B(D) (E)C，從而B(E)，CÏ(E)，而去掉A后，B、C的對手集相同，從而EA于是(A) (E) (D)

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

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

24、n1或2，定理顯然成立設(shè)定理對于k個(gè)頂點(diǎn)時(shí)成立，即若一個(gè)樹有k個(gè)頂點(diǎn)，則其邊有k1條對于k+1個(gè)頂點(diǎn)的樹，只要去掉一個(gè)懸掛點(diǎn)及與之相鄰的一條邊，就成為有k個(gè)頂點(diǎn)的情形，此時(shí)的樹有k個(gè)頂點(diǎn)與k1條邊，此時(shí)再把去掉的1個(gè)頂點(diǎn)及1條邊添入，就成為k+1個(gè)頂點(diǎn)，k條邊的樹故證再證明：如果圖G是連通的，且有n個(gè)頂點(diǎn)與n1條邊，則G是一個(gè)樹取G的生成樹T，則此生成樹有n個(gè)頂點(diǎn)，因是樹，故有n1條邊但TÍG，故TG故證定理3 樹T具有以下性質(zhì)： 在T中去掉任一邊后，所得的圖是不連通的； 在T中添上1條邊后，所得的圖有圈； T中的任兩個(gè)頂點(diǎn)v1與v2間有且僅有1條鏈證明 設(shè)樹T有n個(gè)頂點(diǎn)與n1條邊，

25、在T中去掉1條邊后得到圖G，如果G仍連通，則G仍是一個(gè)樹(因無圈且連通)應(yīng)有n1條邊，矛盾 如添上1邊后仍無圈，則仍為樹，有n個(gè)頂點(diǎn)與n條邊，矛盾 由T連通，故v1與v2間必有鏈，若v1與v2間有不完全相同的兩條鏈，則此圖中有圈，即不是樹矛盾，故v1與v2間有且僅有1條鏈 情景再現(xiàn)7某個(gè)團(tuán)體有1982個(gè)人，其中任意4人都至少有一人認(rèn)識其他三個(gè)人，認(rèn)識其他所有人的人數(shù)最少是多少？(1982年美國數(shù)學(xué)競賽)8在一所房子里有10個(gè)人，其中任意3人中至少有2人互相認(rèn)識，證明：其中有4人，他們?nèi)我?人都互相認(rèn)識(1980英國數(shù)學(xué)競賽)如果把中的數(shù)10改為9，結(jié)論仍成立否？(1977年波蘭數(shù)學(xué)競賽)習(xí)題1

26、31如果每個(gè)點(diǎn)的出次都是2，那么，一個(gè)點(diǎn)經(jīng)過兩條弧就可以到達(dá)的點(diǎn)至多有幾個(gè)？經(jīng)過一條弧或兩條弧可以到達(dá)的點(diǎn)至多有幾個(gè)？2在競賽圖中必有一個(gè)點(diǎn)，從它到其它的頂點(diǎn)，只需經(jīng)過一條弧或兩條弧3一個(gè)有n個(gè)點(diǎn)的競賽圖，各點(diǎn)的出次為w1w2wn如果w1n1，w2n2，wk1n(k1)，但wknk(1kn)證明：wknk4 如果在點(diǎn)數(shù)n3的競賽圖中，有兩個(gè)點(diǎn)的出次相等證明，圖中必有三角形回路(即有三個(gè)選手A、B、C，其中A勝B，B勝C，C又勝A) 在一個(gè)n人參加的循環(huán)賽中，每兩人比賽一場，如果沒有平局，參賽者贏的場數(shù)分別是w1，w2，wn求證：出現(xiàn)三個(gè)參賽者A，B，C，滿足A勝B，B勝C，C勝A的充分必要條件

27、是www5亞洲區(qū)足球小組賽，每組有4個(gè)隊(duì)，進(jìn)行循環(huán)賽，每兩個(gè)隊(duì)賽一場，勝者得3分，負(fù)者得0分，平局各得1分，賽完后，得分最高的前兩名出線如果幾個(gè)隊(duì)得分相同，那么便抽簽決定這些隊(duì)的名次，問一個(gè)隊(duì)至少要得多少分，才能保證一定出線？6條件同上題，問一個(gè)隊(duì)如果出了線，它至少得了多少分？7在8×8棋盤上填入164的所有整數(shù)，每格一數(shù)，每數(shù)只填一次， 證明：總可以找到兩個(gè)相鄰的方格（具有公共邊的兩個(gè)方格叫相鄰）， 在此兩個(gè)方格中填入的數(shù)的差不小于5？8平面上有n條直線，把平面分成若干個(gè)區(qū)域.證明:用兩色就足以使相鄰的區(qū)域都涂上不同的顏色.9在某個(gè)國家，任意兩個(gè)城市之間用下列交通工具之一進(jìn)行聯(lián)絡(luò)：

28、汽車，火車和飛機(jī)已知沒有一個(gè)城市擁有這三種交通工具，并且不存在這樣三個(gè)城市，其中任意兩個(gè)在聯(lián)絡(luò)時(shí)都用同一種交通工具而且這個(gè)國家用了這三種工具這個(gè)國家最多有多少個(gè)城市？(1981年保加利亞，美國數(shù)學(xué)競賽)10一個(gè)大三角形的三個(gè)頂點(diǎn)分別涂紅、黑、蘭三色，在三角形內(nèi)部取若干點(diǎn)也任意涂紅、黑、蘭三色之一，這些點(diǎn)間連有一 些線段，把大三角形分成若干互相沒有重疊部分的一些小三角形.求證:不論怎樣涂，都有一個(gè)小三角形，其三個(gè)頂點(diǎn)涂的顏色全不同.11證明：在2色K6中一定存在兩個(gè)同色三角形（即同色K3）12某個(gè)國家有21個(gè)城市，由若干個(gè)航空公司擔(dān)負(fù)著這些城市之間的空運(yùn)任務(wù)每家公司都在5個(gè)城市之間設(shè)有直達(dá)航線(

29、無需著陸，且兩城市間允許有幾家航空公司的航線)，而每兩個(gè)城市之間都至少有一條直達(dá)航線問至少應(yīng)有多少家航空公司？(1988年前蘇聯(lián)數(shù)學(xué)競賽)本節(jié)“情景再現(xiàn)”解答：1解 如圖的5個(gè)點(diǎn)即不存在同色三角形，故例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ì)過2次，故應(yīng)統(tǒng)計(jì)得到邊數(shù)=2(n+1)矛盾故至少有一個(gè)頂點(diǎn)，其次數(shù)33解 點(diǎn)A：出次3，入次1；點(diǎn)B：出次1，入次1；點(diǎn)C：出次0，入次2；點(diǎn)D：出次1，入次1RJ 出次的和=3+1+0+1=5；入次的和=1+1+2+1=5出次的和=入次的和證明 由

30、于每條弧起點(diǎn)所是出次的點(diǎn)，終點(diǎn)都是入次的點(diǎn)，故出次和與入次和相等，都等于弧的條數(shù)ABCD4解 不一定，例如右面的一個(gè)圖中，就沒有兩個(gè)點(diǎn)的出次相同A、B、C、D四點(diǎn)的出次依次為3，2，1，0一般的n個(gè)點(diǎn)的競賽圖中，可以出現(xiàn)n個(gè)點(diǎn)的出次分別為n1，n2，n3，2，1，0這n個(gè)值，于是不一定有兩個(gè)點(diǎn)的出次相同5解 S中有3個(gè)元素是可以的，abca滿足要求若S至少有4個(gè)元素，取其中4點(diǎn)，由， S中每兩點(diǎn)間都要連出1條有向線段，4點(diǎn)間連出6條有向線段每條有向線段都記一個(gè)出次，共有6個(gè)出次因此至少有一個(gè)點(diǎn)至少有2個(gè)出次設(shè)ab，ac，則無論bc或是cb均引出矛盾即S的元素個(gè)數(shù)3故S最多有3個(gè)元素 6證明 設(shè)

31、共有n個(gè)點(diǎn)，由于各點(diǎn)出次互不相等，故這n個(gè)點(diǎn)的出次取得0，1，2，n1這n1個(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位；，依此類推，把出次為k的點(diǎn)排在倒數(shù)第k+1位，直到出次為n1的點(diǎn)排在第1位這就得到滿足題目要求的排法 反設(shè)圖中所有各點(diǎn)的出次均互不相等，則由上題，可把這些點(diǎn)排成一列，使前面的點(diǎn)到達(dá)后面的點(diǎn)而后面的點(diǎn)不能到達(dá)前面的點(diǎn)，于是該圖中沒有回路，

32、與已知此圖有回路矛盾故必有兩點(diǎn)出次相等7解 先證明：任意4人中都有1人與其余n1人認(rèn)識用n個(gè)點(diǎn)表示這n個(gè)人，若兩個(gè)人認(rèn)識，則在表示這兩個(gè)人的點(diǎn)間連一條實(shí)線，否則連一條虛線設(shè)任取4人v1、v2、v3、v4，其中v1與v2、v3、v4都認(rèn)識，但此四人中無人與n1人都認(rèn)識即每個(gè)點(diǎn)都有與之不相鄰的點(diǎn)設(shè)與v1、v2、v3、v4不相鄰的點(diǎn)分別為v1、v2、v3、v4，顯然v1v2，v2v1，若v1v2，則四點(diǎn)v1、v2、v1、v2不滿足題意于是v1=v2，同理v1=v3，于是得v1=v2=v3，此時(shí)v1、v2、v3、v1這四點(diǎn)仍不滿足已知條件故證又證 設(shè)圖G中度數(shù)小于n1的點(diǎn)為v1、v2、vk，記F=v1

33、、v2、vk，用實(shí)線表示相鄰(認(rèn)識)，用虛線表示不相鄰若k4，則命題正確(因?yàn)閳D中找不到4個(gè)人，他們中任1人都沒有與其余n1人認(rèn)識)若k4，由于vk+1、vk+2、vn的度數(shù)都=n1，故與v1不相鄰的點(diǎn)都在F中，設(shè)為v2，此時(shí)若還能找到v3、v4F，且v3與v4不相鄰則此四人不滿足題目要求(圖7)若在F中除v1、v2外無不相鄰的人，則v3、vk均至少與v1、v2中某一人不相鄰則如圖、，亦與已知矛盾故k4不可能故證再考慮本題：把1982個(gè)人中的任意4人組成一組，該組中必有1人認(rèn)識其余所有的人去掉這個(gè)人，在余下的人中再任取4人，又成一組，又可找出一個(gè)認(rèn)識其余所有人的人；，這樣一直做下去直到余下3人

34、為止，此3人可能與其余的人不全認(rèn)識故至少有1979人認(rèn)識其余所有的人8解 用10個(gè)點(diǎn)表示這10個(gè)人，如果某2人互相認(rèn)識，則在表示這兩人的點(diǎn)間連1條線即任3點(diǎn)都至少連了1條線，要求證明存在一個(gè)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連線，則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成

35、為K4 由知A1，A6中任一點(diǎn)至多與其余5點(diǎn)中的2點(diǎn)未連線即與其余5點(diǎn)中至少3點(diǎn)連了線設(shè)A1與A2、A3、A4連了線此時(shí)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時(shí)此時(shí)9個(gè)點(diǎn)連線統(tǒng)計(jì)為45，為奇數(shù)不可能若有某點(diǎn)連線數(shù)5，即該點(diǎn)至少與4點(diǎn)未連線，則如上，矛盾從而必有點(diǎn)連線數(shù)6的點(diǎn)“習(xí)題67”解答：ABCDEFG1解 一個(gè)點(diǎn)經(jīng)過兩條弧就能到達(dá)的點(diǎn)至多有4個(gè)經(jīng)過一條弧或兩條弧就能到達(dá)的點(diǎn)至多有6個(gè)如圖，每個(gè)點(diǎn)的出次都是2，點(diǎn)A經(jīng)過1條弧能到達(dá)B、C，點(diǎn)B、C分別經(jīng)

36、過1條弧可以到達(dá)D、E、F、G，故點(diǎn)A經(jīng)過1條或2條弧可以到達(dá)至多6個(gè)點(diǎn)其中如果有些點(diǎn)重合，則點(diǎn)A可以到達(dá)的點(diǎn)就少于6個(gè)2證明 取出次最多的點(diǎn)為A，則A的出次(n1)他可以經(jīng)一條線到達(dá)的點(diǎn)為B1，B2，Bm，m(n1)對于A不能到達(dá)的點(diǎn)C，若B1，B2，Bm中沒有點(diǎn)到達(dá)C，則不能到達(dá)C的點(diǎn)至少有m+1個(gè)，即C的出次比A多，與A為出次最多的點(diǎn)矛盾故所有A不能到達(dá)的點(diǎn)，都可經(jīng)2條線到達(dá)故證3證明 k1時(shí)，若w1n1，則w1n1設(shè)w1n1，即w1到達(dá)所有其余的點(diǎn)把出次為w1的點(diǎn)去掉，這對余下的點(diǎn)的出次都不受影響此時(shí)就得到一個(gè)只有n1個(gè)點(diǎn)的競賽圖若w2n2，則w2n2設(shè)w1n1，w2n2，同上兩次去掉

37、出次為w1，w2的點(diǎn)，則得到一個(gè)有n2個(gè)點(diǎn)的競賽圖其中每個(gè)點(diǎn)的出次n3于是若w3n3，就有w3n3依此類推，若各點(diǎn)的出次為w1w2wn如果w1n1，w2n2，wk1n(k1)，但wknk(1kn)，則依次去掉k1個(gè)點(diǎn)，而不影響余下點(diǎn)的出次，此時(shí)余下點(diǎn)的出次n(k1)1nk若wknk，則必有wknk證畢4證明 設(shè)A與B出次相等，由于A、B必連有線，不妨設(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中沒有點(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，

38、于是A勝B，B勝C，C勝A證畢 證明：不論何種比賽結(jié)果，所有參賽者出次的和都等于12(n1)n(n1)若每個(gè)參賽者的出次都互不相同，則出次分別為0，1，2，n1此時(shí)不存在滿足“A勝B，B勝C，C又勝A”的三個(gè)參賽者此時(shí)www02+12+(n1)2當(dāng)有兩個(gè)參賽者的出次相同時(shí)，就存在三角形回路設(shè)出次為wk的點(diǎn)為Ak設(shè)w1w2w1且設(shè)w1n1，wk1n(k1)，但wknk，則wknk，逐個(gè)把A1，A2，Ak1去掉，這樣做不會影響剩下點(diǎn)的出次這樣去掉點(diǎn)后，余下點(diǎn)中必有引向Ak的線，設(shè)從Aj(j>k)有引向Ak的線，把這條線的方向改變，則Ak的出次變?yōu)閣k+1，而Aj的出次變?yōu)閣j1此時(shí)(wk1)

39、2(wj1)2ww2(wkwj)2ww，即這樣操作可使和www增加，繼續(xù)這樣做，直到使wknk，這時(shí)去掉wk，再做下去，直到每個(gè)wi都等于n(i1)(i1，2，n)為止此時(shí)和式www已嚴(yán)格遞增至這說明www成立5解 共計(jì)比賽6場，最多共可得18分若有三個(gè)隊(duì)都是二勝一負(fù)得6分(如圖中A、B、C隊(duì))，則不能保證一定出線(因要抽簽才能決定是否出線)若一個(gè)隊(duì)得7分，則保證一定出線，因不可能有三個(gè)隊(duì)至少得7分，否則7×3=21>18故得分不少于7分的至多有2個(gè)隊(duì)故得到7分一定能出線ABCD6解 若三個(gè)隊(duì)都互相打成平局，都輸給另一隊(duì)(圖中B、C、D三隊(duì))，則此三個(gè)隊(duì)都得2分，其中有一個(gè)隊(duì)出

40、線若某隊(duì)只得1分，則該隊(duì)1平2負(fù)，贏該隊(duì)的兩個(gè)隊(duì)都至少得了3分，于是名次都在該隊(duì)之前，該隊(duì)不可能出線即某個(gè)隊(duì)出線了，則該隊(duì)至少得了2分7解 把相鄰的兩格中心用一條邊相連，于是就有一個(gè)8行，每行8個(gè)點(diǎn)的圖，從8´8棋盤的左上角一格到右下角一格需要經(jīng)過14條邊，如果所有相鄰方格中填入數(shù)的差小于5，則由于連填“1”的格與填“64”的格之間的路至多經(jīng)過14條邊于是這兩格中數(shù)的差不會超過14´4=56.但641=63矛盾故結(jié)論成立8證明 當(dāng)n1時(shí)，1條直線把平面分成兩部分，用兩色可以區(qū)分這兩部分，如果增加1條直線，可以把這條直線某一旁的區(qū)域中原來涂的顏色變成另一種顏色則所有相鄰的區(qū)域涂色都不同以后每多畫出1條線都把線一旁的部分的每個(gè)區(qū)域中顏色重涂成與原來不同的顏色，就可使相鄰區(qū)域涂色不同9解 設(shè)共有n個(gè)城市，每兩個(gè)城市之間連一條線