然而在所有的連通圖中它們的連通程度是很不相同的

1、 上一節(jié)我們引進了圖的連通概念，利用圖的連通性，可以把圖分成兩類：連通圖和非連通圖。然而，在所有的連通圖中，它們的連通程度是很不相同的。 3 連通度返回 結(jié)束1 例1 去任一條邊或非懸 雖去任一條邊后 去任意一條邊 連通性最好 掛點都不連通。 仍連通，但去 或一個點仍連通， 的一個圖， 或 后不 但去 或 沒有頂點割 連通。 后不連通。 下面引進兩個參數(shù)：點連通度與邊連通度。 返回 結(jié)束2一、 點連通度 定義2.3.1 若 是一個連通圖， ，若 非連通，則稱 是圖 的頂點割。若頂點割 含 個頂點，也稱 是 頂點割。返回 結(jié)束設(shè) 是 階連通圖，令 稱 為 的連通度。定義2.3.23返回 結(jié)束若

2、是 的一個 頂點割，則稱 是 的一個最小頂點割。1V 一個非完全連通圖的連通度就是使這個圖成為非連通圖所需要去掉的最小點數(shù)。4 例1（續(xù)）在例1 中， 是最小頂點割，它的連通度為1； 中， 是最小頂點割，它的連通度為2。 返回 結(jié)束 例1 5返回 結(jié)束如果 非連通，規(guī)定 。因此 的圖或是平凡圖或是非連通圖。約定：6返回 結(jié)束定義2.3.3稱 是 連通的， 如果 。定理 2.3.1 圖 是 連通的當(dāng)且僅當(dāng) ，并且對于 的任意一個點數(shù)不超過 的點子集 ， 仍是連通的。 7二、 邊連通度 定義2.3.4 若 是一個連通圖， ，若 非連通，則稱 是圖 的邊割。若邊割 含 條邊，也稱 是 邊割。返回 結(jié)

3、束設(shè) 是 階連通圖，令 (G)= 稱(G)為 的邊連通度。從而一個非平凡連通圖的邊連通度就是使這個圖成為非連通圖所需要去掉的最小邊數(shù)。 定義2.3.58 例1（續(xù)）在例1 中， 是最小邊割，它的邊連通度為2； 中， 是 最小邊割，它的邊連通度為2。 返回 結(jié)束 例1 9若 是 的一個(G)邊割，則稱 是 的一個最小邊割。如果 非連通，規(guī)定(G)=0。因此(G)=0的圖或是平凡圖或是非連通圖。返回 結(jié)束10返回 結(jié)束定義2.3.6稱 是 邊連通的， 如果 。定理 2.3.2 圖 是 邊連通的當(dāng)且僅當(dāng)對 的任意一個 子集 ，若 ，則 仍是連通的。 11 三、點連通度、邊連通度、最小度間的關(guān)系 分析

4、：若 是 階完全圖，則(G) ；若 不是完全圖，則 ?？紤]頂點 ，使得 。返回 結(jié)束 定理2.3.3 是 階簡單圖，則以下幾條結(jié)論成立： 1、 , ； 2、 ，等號成立當(dāng)且僅當(dāng) ； 3、 ，等號成立當(dāng)且僅當(dāng) ； 4 、對 的任意一個頂點 , ; 5 、對 的任意一條邊 , . 12定理2.3.4 對任何簡單圖 ,都有 證明：由定理2.3.3知 。下面證明 如果 是非連通圖或平凡圖，或 階完全圖，易證 下面假設(shè) 是連通的非完全圖。設(shè)是的一個最小邊割，則恰好有兩個連通分支，記為 和 ，并且 與 分別存在一個頂點 和，使 ,否則，記 ， ，有由定理2.3.3，知 ，與假設(shè)矛盾?，F(xiàn)取 的一個點子集：則

5、 ,并且在 中不存在 路，所以 是的一個頂點。故13從前面的討論可看到，對某些圖有當(dāng)然也有一類圖滿足問題：使 成立的條件有哪些？14 思考方式 設(shè)令是G的一個最小邊割， 恰有兩個連連通分支 和 ，點數(shù)分別記為和不妨設(shè)，則下面考慮G中各頂點在G中的度的總和15推論2.3.7設(shè) 是 階簡單圖,若則16推論2.3.6 設(shè) 是 階簡單圖，若對于 的任意兩個不相鄰的頂點 和 ，均有 則 17定理2.3.5 設(shè) 是 階連通的簡單圖，若對于 的任意四個頂點 ， ， 和 ,由 就有則Gp18定義2.3.7 圖 的一族路稱為內(nèi)不交的, 如果這族路中任意兩條路除起點與終點外沒有公共頂點.四、 -連通圖的特征19定

6、理 2.3.8 一個 階的簡單圖 是2連通的充分必要條件是 的任兩個不同的頂點被兩個內(nèi)不交的路所連接. 證明： 設(shè) G 的任兩個不同頂點被兩條內(nèi)不交的路所連，則顯然連通，并且不存在這樣的頂點 v, 使 G-v 不連通。因此 G是2連通的。 設(shè)G是2連通的。我們對任兩個頂點u與v之間的距離用歸納法來證明。當(dāng)d(u,v)=1 時，uv是G的邊歸納假設(shè)對于距離小于k的任意兩個頂點定理結(jié)論成立現(xiàn)設(shè)d(u,v)=k(1).只要證明G中存在兩條內(nèi)不交的路即可20推論2.3.9 一個 階的簡單圖 是2連通的充分必要條件是 的任兩個不同的頂點含在 的某一個回路上定理2.3.10 一個 階的簡單圖 是 連通的充分必要條件是 的任兩個不同的頂點被 條內(nèi)不交的路所連接.定理2.3.11 連通圖G 是2 邊連通的充分必要條件是 G 的任意一條邊含在某一條回路上.21定理2.3.12 簡單圖 是 邊連通的充分必要條件是 對 的任意非空真子集,均有22證明：必要性是明顯的。因為對 V(G) 的任意非空真子