人教版初中數(shù)學競賽專題復習計劃《第29章圖論初步》競賽專題復習計劃含

精選文檔精選文檔精選文檔

第29章圖論初步

29.1.1*某大型晚會有2009個人參加，已知他們每一個人最少認識此中的一個人．證明：必有一個人最少認識此中的二個人．

解析2009這個數(shù)量較大，我們先考慮：某小型晚會有5人參加，已知他們每一個人最少認識此中的一個人．證明：必有一個人最少認識此中的二個人．

用5個點、、、、表示5個人，假如兩個人相互認識（本章中的“認識”都是指相互認識），

就在表示這兩個人的極點之間連一條邊．對極點功來說，因為所表示的人最少認識其余4個人的一

個，沒關系設與認識，即和相鄰，相同，設與相鄰，以以下列圖．關于極點來說，不論它

與、、、哪個相鄰，都會出現(xiàn)一個極點引出兩條邊的情況．于是問題得以解決．

用相同的方法能夠證明，對2009個人來說，命題成立．其實，把2009換成隨意一個大于l的奇數(shù)，

命題也成立．

29.1.2*在一間房子里有（>3）個人，最罕有一個人沒有和房子里每一個人握手，房子里可能與每

個人都握手的人數(shù)的最大值是多少？

解析用個極點表示個人，若某兩個人握過手，就在他們相應的極點之間連一條邊，這樣就獲得了

一個圖．因為不是任何兩個人都握過手，所以的邊數(shù)最多是完滿圖（即個點每兩點之間恰連

一條邊）的邊數(shù)減1，去掉的那條邊的兩個端點和所表示的兩個人未握過手．所以房子里可能與每

個人都握手的人數(shù)的最大值是．

29.1.3*九名數(shù)學家在一次國際數(shù)學會議上相遇，發(fā)現(xiàn)他們中的隨意三個人中，最罕有兩個人能夠用同一種語言對話．假如每個數(shù)學家至多可說三種語言，證明最罕有三個數(shù)學家能夠用同一種語言對話．

解析用9個點，，，表示這九名數(shù)學家，假如某兩個數(shù)學家能用某種語言對話，就在他們

相應的極點之間連一條邊并涂以相應的顏色．我們要證明的是：存在三個極點、、，使得邊（，

）和（，）是同色的．這樣的，、、這三名數(shù)學家就能用同一種語言對話．

下邊就極點，分兩種情況：

（1）與，，均相鄰，因為每個數(shù)學家至多能說三種語言，所以每一個極點引出的邊的顏色至多是三種．依據(jù)抽屜原理知，從發(fā)出的8條邊中最罕有2條是同色的，沒關系設為（，）、（，）．于是、、所表示的三名數(shù)學家能用同一種語言對話．見圖（）．

（2）與，，，中的最少一點不相鄰，沒關系設功與功不相鄰．因為隨意三個數(shù)學家中，最少有兩個人能夠用同一種語言對話，所以，，，，中的每一個不是和研相鄰就是和功相鄰，根據(jù)抽屜原理可知，此中最罕有4個點與或相鄰．沒關系設、、、與相鄰，如圖（），再對引出的這4條邊用抽屜原理可得，最罕有2條邊是同色的，設為（，）、（，）．于是、、所表示的三名數(shù)學家能用同一種語言對話．評注若本題中的九改成八，則命題不成立．反比方圖（）所示．圖中每條邊旁的數(shù)字表示不一樣樣的語種．29.1.4證明任何一群人中，最罕有兩個人，它們的朋友數(shù)量相同．解析設隨意給定的一群人有個．用極點表示這個人．當且僅當極點、表示的兩個人是朋友時令、相鄰，獲得個極點的簡單圖．對中隨意，因為它能夠和其余個極點相鄰，所以極點的度（）滿足，即圖的極點度只好是個非負數(shù)0，1，，中的一個．假如圖的極點的度都不一樣樣，則圖擁有0度極點和度極點．度極點和中其余極點都相鄰，特別地和極點相鄰．但0度極點和中任何極點都不相鄰，矛盾．這就證了然中必然有兩個極點，它們的度相同．也就是說，這群人必有兩個人，他們的朋友相同多．29.1.5*有一個觀光團，此中隨意四個成員中總有一名成員原來見過其余三名成員．證明：在隨意四名成員中，總有一名成員原來見過所有成員．解析用圖論語言表示即：圖的隨意四點中最罕有一個極點和其余三個極點相鄰．證明圖隨意四個極點中最少一個極點和中其余所有極點都相鄰．用反證法．假如命題不成立，則中有四個點、、、，它們和圖中的其余所有極點不都相

鄰．于是存在四個極點、、、（不用然不一樣樣）它們挨次與、、、都不相鄰．如圖．所

以不是、、中的一個，且與是兩個不一樣樣的極點．

假如與不一樣樣，則、、、中沒有一個極點和其余三個極點都相鄰，和已知矛盾．所以和

重合．同理可證，和重合．于是和、、都不相鄰，和已知矛盾．

這就證了然圖中隨意四個極點中最罕有一個極點和的其余所有極點都相鄰．

29.1.6能否存在這樣的多面體，它有奇數(shù)個面，每個面有奇數(shù)條棱？

解析不存在這樣的多面體．事實上，假如這樣的多面體存在，那么用極點表示這個多面體的面，并且僅當

、所代表的兩個面有公共棱時，在圖

相應的兩極點之間連一條邊，依題意

是奇數(shù)，

于是奇數(shù)個奇數(shù)和也是奇數(shù)．而這一個圖中的極點的和為偶數(shù)矛盾．

評注關于圖的極點和邊數(shù)之間的關系，有以下定理：圖

中邊數(shù)的兩倍等于極點度數(shù)之和．即若

中個極點為

，，，

，邊數(shù)為

，則

．

29.1.7*

名選手進行抗衡賽，每名選手至多賽一場，每場兩名選手參加，已賽完

場．證明：至

罕有一名選手勝過三次．解析

把選手看作極點．當且僅當

、所代表的兩名選手比勝過時，令

、相鄰，獲得含

個頂

點的簡單圖．因為總合勝過

場，所以，圖

的邊數(shù)是

．于是

．

假如圖中所有極點的度都不超出2，則由上式獲得

，

這不能夠能．所以圖中最罕有一個極點，它的度最少是3．于是，極點所表示的選手最少勝過三次．29.1.8一航空線路共連結50個城市，現(xiàn)要求從一個城市到另一城市至多需換乘兩次飛機，問航空線路最少要多少條（任兩城市之間的航空線路數(shù)為0或1）？解析沒關系將50個城市看作50個點，它們之間連的線構成一連通圖．圖論告訴我們，假如每一點的度（即出發(fā)的線條數(shù)）最少為2，則因為邊數(shù)為點度之和的一半，其數(shù)值不小于50；如有一個點的度為1（明顯連通圖不存在度為0的孤立點），則可經(jīng)過刪去該點證明。邊數(shù)必然最少為49，不然圖就不連通（只要對剩下的圖不停進行上述辦理過程）．于是找到一個城市為中轉站，其余城市與之相連，構成一“星形”即可．故線路最少要49條．

已知九個人

，，，

中，

和兩個人握過手，

、各和四個人握過手，

、、

、

各和五個人握過手，、各和六個人握過手．證明：這九個人中必然能夠找出三個人，他們相互

握過手．

解析用9個點，，，表示，，，這九個人，若兩個人握過手，就在他們相應的頂點之間連一條邊，這樣便獲得了一個圖

．因為

，所以存在一個不一樣樣于

，，的點

與

相鄰．明顯

≥5．考慮與功相鄰的其余

5個點，若此中隨意一點都不與

相鄰，則

，這不能夠能．故必有一點

與相鄰，從而

、、

兩兩相鄰．即它們表示的三個人相互握過手．

29.1.10*

參加某次學術議論會的共有

263個人，已知每一個人最少和三位與會者議論過問題．證明：至

罕有一個人和四位或四位以上的學者議論過問題．解析

用點

，，，

表示

263個人，兩個人議論過問題，就在相應的點之間連一條邊，

得圖

．在

圖中，任一極點的次數(shù)≥

3．若沒有一個極點的次數(shù)≥

4，則

中的所有極點的次數(shù)都是

3．于是

，是一個奇數(shù)，而這應是一個偶數(shù)，所以最罕有一個極點的次

數(shù)≥4．于是命題得證．

29.1.11*某地區(qū)網(wǎng)球俱樂部的20名成員舉行14場單打競賽，每人最少上場一次．求證：必有六場

競賽，其12個參賽者各不一樣樣．

解析用20個點表示這20名俱樂部成員，14條邊表示14場競賽，得圖．依據(jù)題意，，，2，，

20．

于是

．今在每個極點

處抹去

條邊（一條邊能夠同時在其兩端點處被抹去）

，抹去的邊數(shù)不超出

．

故余下的圖中最少還有6條邊，且中每個極點的次數(shù)都≤1，所以這6場競賽的參賽者各不一樣樣．

29.1.12*34個城市參加雙人舞競賽（每個城市一男一女），賽前，某些選手相互握手．同一城市的

兩人不握手．今后，來自城的男選手問其余參賽選手他們與人握手的次數(shù)，獲得的答案都不一樣樣．問城女選手和多少人握過手？解析用極點表示參賽選手．關于、，當且僅當、所表示的兩名隊員握過手時，令它們相鄰，獲得一個68個極點的簡單圖．因為同一個的兩名隊員之間不握手，所以對隨意，．城男選手用表示．圖中除外還有67個點，它們的度各不一樣樣，所以必有一個點度為0，即和中其余極點不相鄰．所以若極點表示的選手和極點所表示的選手來自一個城市，則．從圖中去掉和，獲得含66個極點的圖．則是中的極點，并且除外，其余極點的度也都不一樣樣．所以和前述證明相同，含有度分別為0和64的極點和，它們在原來圖中的度分別為1和65．這樣連續(xù)，可證0≤≤33，圖中含有極點、，它們的度分別為和，并且所代表的選手來自同一城市，此中，所以．所以城女選手握手次數(shù)為33．評注本題證明中，將的極點編號，按度的非降次序（≤≤≤）擺列，獲得（，，，）稱為圖的度序列．利用度序列解題是一種重要方法．29.1.13*有一個團意會議，有100人參加．此中隨意四個人都最罕有一個人認識三人．問：該集體中認識其余所有人的成員最罕有多少？解析先把問題翻譯成圖論語言．把該集體的成員視為極點．關于隨意兩個極點、所代表的成員，當且僅當相互認識，則在、之間聯(lián)一條邊（即相鄰）．獲得一個含100個極點的簡單圖．已知條件是，圖中隨意四個極點中都最罕有一極點和其余三個極點相鄰．要求圖中度為99的極點個數(shù)的最小值．當圖是完滿圖時，每個極點的度都是99，所以有100個度為99的極點．當圖是非完滿圖時，圖中必有兩個不相鄰的極點和．明顯，．所以圖中度為99的點的個數(shù)≤98．假如中除和外還有兩個極點、不相鄰，則、、和中不存在和其余三個極點都相鄰的極點，與題意矛盾．所以中除、外隨意兩個極點相鄰．這說明對中除、外的隨意點，均有≥97．假如中除、外的任何都和、相鄰，則．此時中度為99的極點個數(shù)為98．設中除、外有個極點和、不都相鄰，則有的性質(zhì)知，中除、、外的隨意極點和、、都相鄰．所以≤98，≤98，≤98，＝99．所以中度為99的極點個數(shù)為97．

這表示含100個極點的簡單圖中，假如隨意四個極點中必有一個極點和其余三個極點都相鄰，那么

中最罕有97個度為99的極點．

回到原問題，即得：該集體中認識其余所有人的成員最少是97個．

評注本題中的成員數(shù)100改為隨意的，其余條件不變，則結論為該集體最罕有人認識其余所

有人．

29.1.14*畢業(yè)舞會有男女學生各人參加，．每個男生都和一些但不是所有的女生跳過舞，每

個女生也都和一些但非所有的男生跳過舞．證明：總有兩名男生、和兩名女生、，使得和

，和跳過舞，但和，和都未跳過舞．解析用極點表示參加舞會的學生，男生的全體用來表示，女生的全體用來表示．對隨意的、，當且僅當所表示的男生和女生跳過舞季節(jié)、相鄰．的極點之間以及的極點之間都不相鄰．已知對隨意的、，都有，，要證明圖中含有兩條沒有公共端點的邊．設是中度最大的極點，在與不相鄰的的極點中任選．因為和不相鄰，且，所以和中某個相鄰．假如和所有與相鄰的極點相鄰，則，與是中度最大的極點矛盾．所以，必有是的極點但和不相鄰．于是邊、沒有公共端點．評注本題解法有必然典型性，抓住圖中度最大的極點來解決問題．自然，有時也能夠從圖中度最小的極點下手．29.1.15*設，，，，是平面上的6點，此中任3點不共線．假如這些點之間隨意連結了13條線段，求證：必存在4點，它們每兩點之間都有線段連結．

解折將已連結的13條線段全染成紅色，還未連上的兩條用藍線連上（因為所有兩點連一線段時應當共有15條）．于是必有一個同色三角形，此刻的藍色線只有兩條，所以同色三角形必為紅色的．沒關系

設△是紅色的．從、、引向△

極點各有

3條，這

9條線段中最多只有

2條藍色，最罕有

7條是紅色的，

所以，或許是

，或許是

，或許是

，引向△

極點的線段所有是紅色．比方說，

、、

所有是紅色，那么

4點

、、

、的每

2點連線所有是紅色的，命題得證．

29.1.16在某城有若干棟（>2）獨家住所，此中每棟住所住有1人．在一個晴日氣，每一個人都將自

己的家喬遷了一次．喬遷后每家仍住1人，但是大家都調(diào)換了住所．證明：在喬遷今后，可將這些住

宅分別漆上藍色、綠色和紅色，使得關于每個主人來說，他的新居和舊居顏色不一樣樣樣．

解析將住所一一編號，使得第一座住所搬出來的人住進第二座住所，第二座住所出來的人住進第三

座住所于是必然存在一個自，使得第矗座住所搬出的人住進第1座住所．這是個人形成一個“圈”．如

果志為偶數(shù)，明顯只要要2種顏色，假如＆是奇數(shù)，3種顏色足夠了．此后再考慮其余人，最后形成一

個個相互獨立的“圈”（自然也可能只有一個），每個圈獨自辦理即可．

29.1.17*某俱樂部共有99名成員，每一個成員都宣稱只愿意和自己認識的人一起打橋牌．已知每個成員都最少認識67名成員．證明必然有4名成員，他們能夠在一起打橋牌．

解析作一個圖：用99個點表示99名成員，假如兩名成員相互認識，就在相應的兩個極點之間連一條邊．已知條件是：對隨意極點，≥67．欲證中含有一個4階完滿圖．在中任取一個極點，因為≥67，所以存在極點，使得與相鄰且與不相鄰的極點至多為（99－1－67＝）31個．相同，與不相鄰且與相鄰的極點也至多31個．于是圖中最罕有（99－31－31－2＝）35個極點和、均相鄰．以以下列圖，設極點和極點、均相鄰．因為≥67，并且中至多只有（3l+31+2＝）64個不一樣樣時和、均相鄰的極點，所以極點最少還和一個與、均相鄰的極點相鄰．從而、、