初高中數學競賽訓練----圖論初步1 教育頭條網

2019-02-28 08:36:26 放手家長

羅馬尼亞大師賽，中國數學隊全軍覆沒。對競賽結果本次參賽的中國領隊瞿振華表示：“總體來說，我們選手都發揮了自身的水平，雖然沒有金牌有一些遺憾。有3名選手獲得35分，與金牌線37分差之毫釐。主要問題是第三題我們沒有一個同學做出來，顯示出我們的學生在遇到具有一些高等背景的組合問題時視野不夠寬闊，這是值得注意和改進的地方。”

我將寫幾篇圖論內容，供師生參考。

圖論的基本概念

圖：若干頂點構成一個集合，與若干連接頂點集合中兩個頂點的邊構成一個圖。頂點集合記為V，邊集合記為E，圖可以記為G={V,E}

圖1

圖1中，V={1,2,3,4},E={{1,2},{2,3},{2,4},{3,4}}

從一個點連出的不同邊的數目叫該頂點的度數，記為d（v）。圖1中d（2）=3，d（3）=d（4）=2，d（1）=1.

路徑:圖G中如果一組節點，依次有邊相互連接，就形成一條路徑。例如{{1，2}，{2，3}}就是連接1，3的一條路徑，也可以寫成路徑{1，2，3}。

環：圖G中如果存在一條非空路徑，經過這條路徑從起始頂點能夠再回到起始頂點，這條路徑就是一個環路或者環。如{2，3，4，2}就是一個環。

連通圖：如果從圖G中任意點出發，都有至少一條路徑到其它任意點，則這個圖叫聯通圖。

如果圖G1,G2存在一唯一方式實現點與點的對應關係，邊與邊的對應關係，則G1,G2同構。簡單地可以把頂點想象成小圓圈，邊是連接小圓圈的橡皮筋，小圓圈可以移動，而橡皮筋可以拉伸，則圖在變形中形成的圖都是同構的。

例題1.求證：每個碳氫化合物中，氫原子的個數是個偶數。

本題引出

定理：對任意的圖，我們有：

這在圖論裡是常用結論，做高聯題時可以直接使用。將圖1中刪去節點3，以及相連的邊，會得到一個新的圖G'如圖2，這個圖G‘就是圖G的子圖。

圖2

如果一個圖G中，任意兩個節點之間最多隻有一條邊，則圖G叫簡單圖。對於一個有n個節點的簡單圖Gn，我們添加一邊後，Gn還是簡單圖，我們再添加邊，直到再也添加不了了，我們就得到一個完全圖Kn。後面添加的邊連同涉及的節點構成的圖我們叫Gn的補圖，記為Kn,對於Kn中的任意頂點都有

d（v）=n-1.

例題2.求n個節點完全圖的邊數

解：任意兩個節點v1，v2之間都恰有一條邊，其邊數相當於從n個不同節點中選出兩個節點的組合數

例題3.求證世界上任選6人要麼3人互相認識，要麼三人互相不認識？

解：將六人對應到6個頂點的圖G6，如果兩人認識，那麼就在對應的兩點之間連一條邊。G6的補圖就是兩個人不認識則兩個人連一條邊。完全圖k6中任意頂點v都有d（v）=5,故對任何一個頂點，要麼G6中的連接數至少為3，要麼G6'中的連接數至少為3.考察如下的子圖

圖3

如果在2，3，4在母圖中都無邊相互連接，則2，3，4在母圖的補圖中必然相互連接，這就說明了世界上任意6人中要麼3人相互認識，要麼相互不認識。

例題4.平面上有2n個固定的點，假設用一些圓覆蓋了這2n個頂點，且能保證每個圓至少覆蓋n+1點，則這2n個點中任意兩點間存在一條線段（可以是曲線段），被這些圓的全部或者部分完全覆蓋。

解：設計這樣的一個圖G，頂點為這2n個點，邊由如下原則確定：如果任意兩點被一個圓覆蓋，則兩點就是鄰接的，即這兩點之間存在一條邊。由於每個圓覆蓋至少n+1個點，故形成的簡單圖中每個頂點的度至少為n。

下面我們證明：具有2n個頂點，每個頂點的度不小於n的圖一定連通。

反證法。假設不真，則這個圖必然至少可以分成兩個子圖，而這兩個子圖之間是沒有邊相互連接的。其中一個子圖的頂點數必然不大於n，結果在該子圖中的所有頂點的次數

與假設矛盾。這就表明，圖G具有連通性。這樣2n個點中的任意兩個點之間一定存在一條路徑，其中任意一條邊對應的兩個頂點之間的直線段都會在某個一個圓內，所有邊形成的折線就被若干圓完全覆蓋了。

例題5.證明：如果一個圖中每個頂點的度都不小於3，那麼不存在大於2的整數，能整除圖中每個環的長度。

證明：

圖的頂點有限，邊也是有限的，故不同的路徑有限。選擇最長路徑中的一條，假設a是路徑的一個端點，另外一個端點為b，那麼a的鄰接點必然在這條路徑上。否則的話，假設c不在這條路徑上，那麼c到a，再經過這最長的路徑會到b，也是圖上的一條路徑，這條路徑的長度比最長路徑長度多1，矛盾。由於每個頂點的度都不小於3，故圖中有子圖如下，a，b是最長路徑的端點。