初中數(shù)學(xué)競賽專題復(fù)習(xí) 第四篇 組合 第29章 圖論初步試題 新人教版

1、第2929章圖論初步圖論初步29.1.1某大型晚會有2009個人參加，已知他們每個人至少認識其中的一個人證明：必有一個人至少認識其中的二個人解析解析2009這個數(shù)目較大，我們先考慮：某小型晚會有5人參加，已知他們每個人至少認識其中的一個人證明：必有一個人至少認識其中的二個人用5個點、、、、表示5個人，如果兩個人彼此認識（本章中的“認識”都是指相互認1v2v3v4v5v識），就在表示這兩個人的頂點之間連一條邊對頂點功來說，由于所表示的人至

2、少認識其他4個1v人的一個，不妨設(shè)與認識，即和相鄰，同樣，設(shè)與相鄰，如圖所示對于頂點來說，1v2v1v2v3v4v5v無論它與、、、哪個相鄰，都會出現(xiàn)一個頂點引出兩條邊的情況于是問題得以解決1v2v3v4vv1v2v3v4v5用同樣的方法可以證明，對2009個人來說，命題成立其實，把2009換成任意一個大于l的奇數(shù)，命題也成立29.1.2在一間房子里有（3）個人，至少有一個人沒有和房子里每個人握手，房子里可能與每nn個人都握手的人數(shù)的最

3、大值是多少？解析解析用個頂點表示個人，若某兩個人握過手，就在他們相應(yīng)的頂點之間連一條邊，這樣就得到nn了一個圖因為不是任何兩個人都握過手，所以的邊數(shù)最多是完全圖（即個點每兩點之間GGnKn恰連一條邊）的邊數(shù)減1，去掉的那條邊的兩個端點和所表示的兩個人未握過手所以房子里可vv?能與每個人都握手的人數(shù)的最大值是2n?29.1.3九名數(shù)學(xué)家在一次國際數(shù)學(xué)會議上相遇，發(fā)現(xiàn)他們中的任意三個人中，至少有兩個人可以用同一種語言對話如果每個數(shù)學(xué)家至多可

4、說三種語言，證明至少有三個數(shù)學(xué)家可以用同一種語言對話解析解析用9個點，，…，表示這九名數(shù)學(xué)家，如果某兩個數(shù)學(xué)家能用某種語言對話，就在他們1v2v9v相應(yīng)的頂點之間連一條邊并涂以相應(yīng)的顏色我們要證明的是：存在三個頂點、、，使得邊（ivjvkv，）和（，）是同色的這樣的，、、這三名數(shù)學(xué)家就能用同一種語言對話ivjvivkvivjvkv下面就頂點，分兩種情形：1v（1）與，…，均相鄰，由于每個數(shù)學(xué)家至多能說三種語言，所以每一個頂點引出的邊的顏

5、色1v2v9v至多是三種根據(jù)抽屜原理知，從發(fā)出的8條邊中至少有2條是同色的，不妨設(shè)為（，）、（1v1v2v1v鄰于是存在四個頂點、、、（不一定不同）它們依次與、、、都不相鄰如x?y?z?w?xyzw圖所以不是、、中的一個，且與是兩個不同的頂點x?yzwy?x如果與不同，則、、、中沒有一個頂點和其他三個頂點都相鄰，和已知矛盾所以y?x?xyx?y?y?和重合同理可證，和重合于是和、、都不相鄰，和已知矛盾x?z?x?x?y?zw這就證明了圖

6、中任意四個頂點中至少有一個頂點和的其他所有頂點都相鄰GGxyzwxywz29.1.6是否存在這樣的多面體，它有奇數(shù)個面，每個面有奇數(shù)條棱？解析解析不存在這樣的多面體事實上，如果這樣的多面體存在，那么用頂點表示這個多面體的面，并且僅當(dāng)、所代表的兩個面有公共棱時，在圖相應(yīng)的兩頂點之間連一條邊，依題意是奇ivjvG??dv數(shù)，于是奇數(shù)個奇數(shù)和也是奇數(shù)而這一個圖中的頂點的和為偶數(shù)矛盾評注評注關(guān)于圖的頂點和邊數(shù)之間的關(guān)系，有如下定理：圖中邊數(shù)的兩

7、倍等于頂點度數(shù)之和即GG若中個頂點為，，…，，邊數(shù)為，則Gn1v2vnve??????122ndvdvdve?????29.1.7名選手進行對抗賽，每名選手至多賽一場，每場兩名選手參加，已賽完場證明：n1n?至少有一名選手賽過三次解析解析把選手看成頂點當(dāng)且僅當(dāng)、所代表的兩名選手比賽過時，令、相鄰，得到含個頂ivjvivjvn點的簡單圖由于總共賽過場，所以，圖的邊數(shù)是于是1n?G1n?????????1221ndvdvdvn??????如

8、果圖中所有頂點的度都不超過2，則由上式得到G，????????12212nndvdvdvn??????≤這不可能因此圖中至少有一個頂點，它的度至少是3于是，頂點所表示的選手至少賽過三Gxx次29.1.8一航空線路共連結(jié)50個城市，現(xiàn)要求從一個城市到另一城市至多需換乘兩次飛機，問航空線路最少要多少條（任兩城市之間的航空線路數(shù)為0或1）？解析解析不妨將50個城市看成50個點，它們之間連的線構(gòu)成一連通圖圖論告訴我們，如果每一點的度（即出發(fā)的線