《初中數(shù)學競賽專題復習 第四篇 組合 第29章 圖論初步試題 新人教版》由會員分享，可在線閱讀，更多相關《初中數(shù)學競賽專題復習 第四篇 組合 第29章 圖論初步試題 新人教版（8頁珍藏版）》請在裝配圖網上搜索。

1、 第29章 圖論初步 29.1.1* 某大型晚會有2009個人參加，已知他們每個人至少認識其中的一個人．證明：必有一個人至少認識其中的二個人． 解析 2009這個數(shù)目較大，我們先考慮：某小型晚會有5人參加，已知他們每個人至少認識其中的一個人．證明：必有一個人至少認識其中的二個人． 用5個點、、、、表示5個人，如果兩個人彼此認識（本章中的“認識”都是指相互認識），就在表示這兩個人的頂點之間連一條邊．對頂點功來說，由于所表示的人至少認識其他4個人的一個，不妨設與認識，即和相鄰，同樣，設與相鄰，如圖所示．對于頂點來說，無論它與、、、哪個相鄰，都會出現(xiàn)一個頂點引出兩條邊的情況．于是問題得

2、以解決． 用同樣的方法可以證明，對2009個人來說，命題成立．其實，把2009換成任意一個大于l的奇數(shù)，命題也成立． 29.1.2* 在一間房子里有（>3）個人，至少有一個人沒有和房子里每個人握手，房子里可能與每個人都握手的人數(shù)的最大值是多少？ 解析 用個頂點表示個人，若某兩個人握過手，就在他們相應的頂點之間連一條邊，這樣就得到了一個圖．因為不是任何兩個人都握過手，所以的邊數(shù)最多是完全圖（即個點每兩點之間恰連一條邊）的邊數(shù)減1，去掉的那條邊的兩個端點和所表示的兩個人未握過手．所以房子里可能與每個人都握手的人數(shù)的最大值是． 29.1.3*** 九名數(shù)學家在一次國際數(shù)學會議上相遇

3、，發(fā)現(xiàn)他們中的任意三個人中，至少有兩個人可以用同一種語言對話．如果每個數(shù)學家至多可說三種語言，證明至少有三個數(shù)學家可以用同一種語言對話． 解析 用9個點，，…，表示這九名數(shù)學家，如果某兩個數(shù)學家能用某種語言對話，就在他們相應的頂點之間連一條邊并涂以相應的顏色．我們要證明的是：存在三個頂點、、，使得邊（，）和（，）是同色的．這樣的，、、這三名數(shù)學家就能用同一種語言對話． 下面就頂點，分兩種情形： （1）與，…，均相鄰，由于每個數(shù)學家至多能說三種語言，所以每一個頂點引出的邊的顏色至多是三種．根據(jù)抽屜原理知，從發(fā)出的8條邊中至少有2條是同色的，不妨設為（，）、（，）．于是、、所表示的三名數(shù)學

4、家能用同一種語言對話．見圖（）． （2）與，，…，中的至少一點不相鄰，不妨設功與功不相鄰．由于任意三個數(shù)學家中，至少有兩個人可以用同一種語言對話，所以，，，…，中的每一個不是和研相鄰就是和功相鄰，根據(jù)抽屜原理可知，其中至少有4個點與或相鄰．不妨設、、、與相鄰，如圖（），再對引出的這4條邊用抽屜原理可得，至少有2條邊是同色的，設為（，）、（，）．于是、、所表示的三名數(shù)學家能用同一種語言對話． 評注 若本題中的九改成八，則命題不成立．反例如圖（）所示．圖中每條邊旁的數(shù)字表示不同的語種． 29.1.4** 證明任何一群人中，至少有兩個人，它們的朋友數(shù)目相同． 解析 設任意給定的

5、一群人有個．用頂點表示這個人．當且僅當頂點、表示的兩個人是朋友時令、相鄰，得到個頂點的簡單圖． 對中任意，由于它可以和其他個頂點相鄰，所以頂點的度（）滿足，即圖的頂點度只能是個非負數(shù)0，1，…，中的一個．如果圖的頂點的度都不相同，則圖具有0度頂點和度頂點．度頂點和中其他頂點都相鄰，特別地和頂點相鄰．但0度頂點和中任何頂點都不相鄰，矛盾．這就證明了中必定有兩個頂點，它們的度相同．也就是說，這群人必有兩個人，他們的朋友一樣多． 29.1.5*** 有一個參觀團，其中任意四個成員中總有一名成員原先見過其他三名成員．證明：在任意四名成員中，總有一名成員原先見過所有成員． 解析 用圖論語言表示

6、即：圖的任意四點中至少有一個頂點和其他三個頂點相鄰．證明圖任意四個頂點中至少一個頂點和中其他所有頂點都相鄰． 用反證法．如果命題不成立，則中有四個點、、、，它們和圖中的其他所有頂點不都相鄰．于是存在四個頂點、、、（不一定不同）它們依次與、、、都不相鄰．如圖．所以不是、、中的一個，且與是兩個不同的頂點． 如果與不同，則、、、中沒有一個頂點和其他三個頂點都相鄰，和已知矛盾．所以和重合．同理可證，和重合．于是和、、都不相鄰，和已知矛盾． 這就證明了圖中任意四個頂點中至少有一個頂點和的其他所有頂點都相鄰． 29.1.6** 是否存在這樣的多面體，它有奇數(shù)個面，每個面有奇數(shù)條棱？ 解析

7、 不存在這樣的多面體．事實上，如果這樣的多面體存在，那么用頂點表示這個多面體的面，并且僅當、所代表的兩個面有公共棱時，在圖相應的兩頂點之間連一條邊，依題意是奇數(shù)，于是奇數(shù)個奇數(shù)和也是奇數(shù)．而這一個圖中的頂點的和為偶數(shù)矛盾． 評注 關于圖的頂點和邊數(shù)之間的關系，有如下定理：圖中邊數(shù)的兩倍等于頂點度數(shù)之和．即若中個頂點為，，…，，邊數(shù)為，則 ． 29.1.7* 名選手進行對抗賽，每名選手至多賽一場，每場兩名選手參加，已賽完場．證明：至少有一名選手賽過三次． 解析 把選手看成頂點．當且僅當、所代表的兩名選手比賽過時，令、相鄰，得到含個頂點的簡單圖．由于總共賽過場，所以，圖的邊數(shù)是．于是

8、 ． 如果圖中所有頂點的度都不超過2，則由上式得到 ， 這不可能．因此圖中至少有一個頂點，它的度至少是3．于是，頂點所表示的選手至少賽過三次． 29.1.8** 一航空線路共連結50個城市，現(xiàn)要求從一個城市到另一城市至多需換乘兩次飛機，問航空線路最少要多少條（任兩城市之間的航空線路數(shù)為0或1）？ 解析 不妨將50個城市看成50個點，它們之間連的線構成一連通圖．圖論告訴我們，如果每一點的度（即出發(fā)的線條數(shù)）至少為2，則由于邊數(shù)為點度之和的一半，其數(shù)值不小于50；若有一個點的度為1（顯然連通圖不存在度為0的孤立點），則可通過刪去該點證明。邊數(shù)必須至少為49，否則圖就不連通（只需對剩

9、下的圖不斷進行上述處理過程）．于是找到一個城市為中轉站，其他城市與之相連，構成一“星形”即可．故線路最少要49條． 29.1.9 已知九個人，，…，中，和兩個人握過手，、各和四個人握過手，、、、各和五個人握過手，、各和六個人握過手．證明：這九個人中一定可以找出三個人，他們相互握過手． 解析 用9個點，，…，表示，，…，這九個人，若兩個人握過手，就在他們相應的頂點之間連一條邊，這樣便得到了一個圖．因為，所以存在一個不同于，，的點與相鄰．顯然≥5．考慮與功相鄰的另外5個點，若其中任意一點都不與相鄰，則 ， 這不可能．故必有一點與相鄰，從而、、兩兩相鄰．即它們表示的三個人互相握過手．

10、 29.1.10* 參加某次學術討論會的共有263個人，已知每個人至少和三位與會者討論過問題．證明：至少有一個人和四位或四位以上的學者討論過問題． 解析 用點，，…，表示263個人，兩個人討論過問題，就在相應的點之間連一條邊，得圖．在圖中，任一頂點的次數(shù)≥3．若沒有一個頂點的次數(shù)≥4，則中的所有頂點的次數(shù)都是3．于是，是一個奇數(shù)，而這應是一個偶數(shù)，所以至少有一個頂點的次數(shù)≥4．于是命題得證． 29.1.11*** 某地區(qū)網球俱樂部的20名成員舉行14場單打比賽，每人至少上場一次．求證：必有六場比賽，其12個參賽者各不相同． 解析 用20個點表示這20名俱樂部成員，14條邊表示1

11、4場比賽，得圖．根據(jù)題意， ，，2，…，20． 于是 ． 今在每個頂點處抹去條邊（一條邊可以同時在其兩端點處被抹去），抹去的邊數(shù)不超過 ． 故余下的圖中至少還有6條邊，且中每個頂點的次數(shù)都≤1，所以這6場比賽的參賽者各不相同． 29.1.12*** 34個城市參加雙人舞比賽（每個城市一男一女），賽前，某些選手互相握手．同一城市的兩人不握手．后來，來自城的男選手問其他參賽選手他們與人握手的次數(shù)，得到的答案都不相同．問城女選手和多少人握過手？ 解析 用頂點表示參賽選手．對于、，當且僅當、所表示的兩名隊員握過手時，令它們相鄰，得到一個68個頂點的簡單圖．由于同一個的兩名隊員之間不

12、握手，所以對任意，．城男選手用表示．圖中除外尚有67個點，它們的度各不相同，因此必有一個點度為0，即和中其他頂點不相鄰．所以若頂點表示的選手和頂點所表示的選手來自一個城市，則． 從圖中去掉和，得到含66個頂點的圖．則是中的頂點，并且除外，其他頂點的度也都不相同．因此和前述證明相同，含有度分別為0和64的頂點和，它們在原來圖中的度分別為1和65．如此繼續(xù)，可證0≤≤33，圖中含有頂點、，它們的度分別為和，而且所代表的選手來自同一城市，其中，所以．因此城女選手握手次數(shù)為33． 評注 本題證明中，將的頂點編號，按度的非降次序（≤≤…≤）排列，得到（，，…，）稱為圖的度序列．利用度序列解題是一種

13、重要方法． 29.1.13*** 有一個團體會議，有100人參加．其中任意四個人都至少有一個人認識三人．問：該團體中認識其他所有人的成員最少有多少？ 解析 先把問題翻譯成圖論語言．把該團體的成員視為頂點．對于任意兩個頂點、所代表的成員，當且僅當彼此認識，則在、之間聯(lián)一條邊（即相鄰）．得到一個含100個頂點的簡單圖．已知條件是，圖中任意四個頂點中都至少有一頂點和其他三個頂點相鄰．要求圖中度為99的頂點個數(shù)的最小值． 當圖是完全圖時，每個頂點的度都是99，所以有100個度為99的頂點． 當圖是非完全圖時，圖中必有兩個不相鄰的頂點和．顯然，．因此圖中度為99的點的個數(shù)≤98． 如果中除

14、和外另有兩個頂點、不相鄰，則、、和中不存在和其他三個頂點都相鄰的頂點，與題意矛盾．因此中除、外任意兩個頂點相鄰．這說明對中除、外的任意點，均有≥97． 如果中除、外的任何都和、相鄰，則．此時中度為99的頂點個數(shù)為98． 設中除、外有個頂點和、不都相鄰，則有的性質知，中除、、外的任意頂點和、、都相鄰．因此≤98，≤98，≤98，＝99．所以中度為99的頂點個數(shù)為97． 這表明含100個頂點的簡單圖中，如果任意四個頂點中必有一個頂點和其他三個頂點都相鄰，那么中至少有97個度為99的頂點． 回到原問題，即得：該團體中認識其他所有人的成員最少是97個． 評注 本題中的成員數(shù)100改為任意的

15、，其他條件不變，則結論為該團體至少有人認識其他所有人． 29.1.14*** 畢業(yè)舞會有男女學生各人參加，．每個男生都和一些但不是全部的女生跳過舞，每個女生也都和一些但非全部的男生跳過舞．證明：總有兩名男生、和兩名女生、，使得和，和跳過舞，但和，和都未跳過舞． 解析 用頂點表示參加舞會的學生，男生的全體用來表示，女生的全體用來表示．對任意的、，當且僅當所表示的男生和女生跳過舞時令、相鄰．的頂點之間以及的頂點之間都不相鄰． 已知對任意的、，都有，，要證明圖中含有兩條沒有公共端點的邊． 設是中度最大的頂點，在與不相鄰的的頂點中任選．由于和不相鄰，且，所以和中某個相鄰．如果和所有與相鄰的

16、頂點相鄰，則，與是中度最大的頂點矛盾．因此，必有是的頂點但和不相鄰．于是邊、沒有公共端點． 評注 本題解法有一定典型性，抓住圖中度最大的頂點來解決問題．當然，有時也可以從圖中度最小的頂點入手． 29.1.15*** 設，，，…，是平面上的6點，其中任3點不共線．如果這些點之間任意連結了13條線段，求證：必存在4點，它們每兩點之間都有線段連結． 解折 將已連結的13條線段全染成紅色，還未連上的兩條用藍線連上（因為所有兩點連一線段時應該共有15條）．于是必有一個同色三角形，現(xiàn)在的藍色線只有兩條，所以同色三角形必為紅色的．不妨設△是紅色的． 從、、引向△頂點各有3條，這9條線段中最

17、多只有2條藍色，起碼有7條是紅色的，因此，或者是，或者是，或者是，引向△頂點的線段全是紅色．比如說，、、全是紅色，那么4點、、、的每2點連線全是紅色的，命題得證． 29.1.16** 在某城有若干棟（>2）獨家住宅，其中每棟住宅住有1人．在一個好天氣，每個人都將自己的家搬遷了一次．搬遷后每家仍住1人，只是大家都調換了住宅．證明：在搬遷之后，可將這些住宅分別漆上藍色、綠色和紅色，使得對于每個主人來說，他的新居和舊居顏色不一樣． 解析 將住宅一一編號，使得第一座住宅搬出來的人住進第二座住宅，第二座住宅出來的人住進第三座住宅……于是一定存在一個自，使得第矗座住宅搬出的人住進第1座住宅．這是個

18、人形成一個“圈”．如果志為偶數(shù)，顯然只需要2種顏色，如果＆是奇數(shù)，3種顏色足夠了．然后再考慮其他人，最后形成一個個互相獨立的“圈”（當然也可能只有一個），每個圈獨自處理即可． 29.1.17*** 某俱樂部共有99名成員，每一個成員都聲稱只愿意和自己認識的人一起打橋牌．已知每個成員都至少認識67名成員．證明一定有4名成員，他們可以在一起打橋牌． 解析 作一個圖：用99個點表示99名成員，如果兩名成員相互認識，就在相應的兩個頂點之間連一條邊．已知條件是：對任意頂點，≥67．欲證中含有一個4階完全圖． 在中任取一個頂點，由于≥67，所以存在頂點，使得與相鄰且與不相鄰的頂點至多為（99－1

19、－67＝）31個．同樣，與不相鄰且與相鄰的頂點也至多31個．于是圖中至少有（99－31－31－2＝）35個頂點和、均相鄰．如圖所示，設頂點和頂點、均相鄰．由于≥67，并且中至多只有（3l+31+2＝）64個不同時和、均相鄰的頂點，因此頂點至少還和一個與、均相鄰的頂點相鄰．從而、、、是4個兩兩相鄰的頂點．于是命題得證． 評注l 若將題中的67人改為66人，則不一定能找出4個互相認識的人來．反例如圖所示．將頂點集分成三個子集{，，…，}，{，，…，}，{，，…，）．同一個子集中任意兩頂點均不相鄰，不同子集中的任意兩點均相鄰．顯然每個頂點的度都是66，任意4點中，至少有2點屬于同一子集，從而

20、它們不相鄰．也就是說圖中不存在兩兩相鄰的4頂點． 評注2 本題可推廣為： 俱樂部有（≥4）人，其中每人都至少認識其中的個人，則在這個人中必定可以找到4個人，他們是兩兩認識的． 29.1.18*** 已知五個城市兩兩相連所得的10條道路中，至少有一個交叉路口，如圖（）．又已知三個村莊和三個城市相連所需的9條道路中，至少有一個交叉路口，如圖（）．利用上述結論，問：用15條道路把六個城市兩兩相連，至少會產生多少個交叉路口？ 解析 如圖（），至少會有3個交叉路口． 假設最多只有兩個交叉路口．我們可以去掉兩條路使其余的路不產生交叉路口．考慮以下兩種情況． （1）若去掉的路與同一個城市相連． 考慮其余的五個城市，它們兩兩相連．但是根據(jù)已知條件，至少有一個交叉路口，矛盾． （2）若去掉的兩條路不與同一個城市相連． 選取其中一條去掉的路所關聯(lián)的兩個城市，再取一個與去掉的路不相連的城市，稱這三個城市為村莊．則這三個村莊和三個城市有路相連．由已知條件，必有一個交叉路口，矛盾． 8