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

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

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

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

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

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

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

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

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