【正文】 ＝ 2， K7＝ λ 7＝ 0， K8＝ λ 8＝ 0。 圖 λ ＝ 1， 它只能是 1邊 連通圖。 若 λ( G)≥ r， 則稱 G是 r 邊 連通圖 。 K5的點連通度 K＝ 4， 所以 K5是 1連通圖， 2連通圖， 3連通圖， 4連通圖。 說明 連通度是為了產(chǎn)生一個不連通圖需要刪去的點的最少數(shù)目。 無向圖的邊割集 定義 設(shè)無向圖 G＝ V,E， 若存在 E ??E， 且 E ?≠ ?， 使得 p(GE ?)p(G)， 而對于任意的 E ???E?， 均有 p(GE ??)＝p(G)， 則稱 E?是 G的 邊割集 ，或簡稱為 割集 。 如何定義連通度 ?問題 ：如何定量地比較無向圖的連通性的強與弱？ ?點連通度 ：為了破壞連通性，至少需要刪除多少個頂點？ ?邊連通度 ：為了破壞連通性，至少需要刪除多少條邊？ ?“ 破壞連通性 ” 是指 “ 變得更加不連通 ” 。 距離有以下性質(zhì)： (1)d(u,v)≥0 ， u＝ v時，等號成立。 若 G為非連通圖，則 p(G)≥2 。 連通圖與連通分支 若無向圖 G是平凡圖或 G中任何兩個頂點都是連通的，則稱 G為 連通圖 ，否則稱 G是 非連通圖 或 分離圖 。 (4)在非簡單標(biāo)定圖中，當(dāng)只用頂點序列表示不出某些通路 (回路 )時，可在頂點序列中加入一些邊 (這些邊是平行邊或環(huán) )，可稱這種表示法為 混合表示法 。定義 Г 可以表示成 ej1 ,ej2 ,… ,ejl。 ?若 Г 中有 邊重復(fù) 出現(xiàn)，則稱 Г 為 復(fù)雜通路 ， 又若 vi0＝ vil， 則稱 Г 為 復(fù)雜回路 。 若 Г的 所有邊各異 ， 則稱 Г為 簡單通路 ， 又若 vi0＝ vil， 則稱 Г為 簡單回路 。 (4)設(shè) u,v∈ V(u,v可能相鄰，也可能不相鄰 )， 用 G∪( u,v)(或G+(u,v))表示在 u,v之間加一條邊 (u,v)， 稱為 加新邊 。 設(shè) E ??E， 用 GE ?表示從 G中刪除 E ?中所有的邊，稱為 刪除 E ?。 定義 定義 設(shè) G＝ V,E為 n階無向簡單圖， 以 V為頂點集 ，以所有 使 G成為完全圖 Kn的添加邊組成的集合 為邊集的圖，稱為 G的 補圖 ，記作 G。 設(shè) G＝ V,E為一圖， V1?V且 V1≠ ?， 稱以 V1為頂點集，以G中 兩個端點都在 V1中的邊 組成邊集 E1的圖為 G的 V1導(dǎo)出的子圖 ，記作 G[V1]。 當(dāng) k為奇數(shù)時， n必為偶數(shù)。 設(shè) D為 n階有向簡單圖，若 D中每個頂點都鄰接到其余的 n1個頂點，又鄰接于其余的 n1個頂點，則稱 D是 n階有向完全圖 。 ??n1iid可圖化，不可簡單圖化。 例 (3) (3,3,3,1) 可圖化，不可簡單圖化。 證明 因為 G既無平行邊也無環(huán)， 所以 G中任何頂點 v至多與其余的 n1個頂點均相鄰， 于是 d(v)≤ n1， 由于 v的任意性，所以△ (G)≤ n1。 由已知條件可知， d中有偶數(shù)個奇數(shù)度點。 度數(shù)列舉例 按頂點的標(biāo)定順序，度數(shù)列為 4,4,2,1,3。 對于頂點標(biāo)定的無向圖，它的度數(shù)列是唯一的。 說明： (1)很多離散問題可以用圖模型求解。 證明 設(shè) G＝ V， E為任意一圖，令 V1＝ {v|v∈V∧ d(v)為奇數(shù) } V2＝ {v|v∈V∧ d(v)為偶數(shù) } 則 V1∪V 2＝ V， V1∩V 2＝ ? ， 由握手定理可知 ???Vvvdm )(2 ??????21)()(VvVvvdvd由于 2m和 ?? 2)(Vvvd，所以 ?? 1)(Vvvd為偶數(shù) ， 但因 V1中頂點度數(shù)為奇數(shù)， 所以 |V1|必為偶數(shù)。 d+(a)＝ 4， d(a)＝ 1 (環(huán) e1提供出度 1，提供入度 1)， d(a)＝ 4+1＝ 5。 稱 d+(v)+d(v)為 v的 度數(shù) ，記做 d(v)。 頂點的度數(shù) 定義 設(shè) G＝ V,E為一無向圖， ?v∈V ， 稱 v作為邊的端點次數(shù)之和為 v的度數(shù) ，簡稱為 度 ，記做 dG(v)。 含平行邊的圖稱為 多重圖 。 稱 Г +D(v)∪Г D(v)為 v的 鄰域 ，記做 ND(v)。 稱 NG(v)∪{ v}為 v的 閉鄰域 ，記做 NG(v)。 ?設(shè)有向圖 D＝ V， E， vi， vj∈V ， ek， el∈E 。 ?無論在無向圖中還是在有向圖中，無邊關(guān)聯(lián)的頂點均稱為 孤立點 。 若 vi＝ vj， 則稱 ek與 vi的 關(guān)聯(lián)次數(shù)為 2，并稱 ek為 環(huán) 。 ?將有向圖各 有向邊均改成無向邊后的無向圖 稱為原來圖的 基圖 。 ?若 |V(G)|與 |E(G)|均為有限數(shù)，則稱 G為 有限圖 。 圖的一些概念和規(guī)定 ?G表示無向圖，但有時用 G泛指圖 (無向的或有向的 )。 （ 2） E為 邊集 ，它是 笛卡兒積 V V的多重子集，其元素稱為 有向邊 ，簡稱 邊 。 定義 一個 無向圖 是一個有序的二元組 V， E,記作 G， 其中 （ 1） V≠ ?稱為 頂點集 ，其元素稱為 頂點 或 結(jié)點 。 例如 在多重集合 {a,a,b,b,b,c,d}中， a,b,c,d的重復(fù)度分別為 2,3,1,1。 定義 一個 有向圖 是一個有序的二元組 V， E， 記作 D， 其中 （ 1） V≠ ?稱為 頂點集 ，其元素稱為 頂點 或 結(jié)點 。 畫出 G與 D的圖形。 ?若 |V(G)|＝ n， 則稱 G為 n階圖 。 標(biāo)定圖與非標(biāo)定圖、基圖 ?將圖的集合定義轉(zhuǎn)化成圖形表示之后，常用 ek表示 無向邊(vi,vj)（ 或 有向邊 vi,vj）， 并稱 頂點或邊用字母標(biāo)定的圖 為 標(biāo)定圖 ，否則稱為 非標(biāo)定圖 。 若 vi≠ vj， 則稱 ek與 vi或 ek與 vj的 關(guān)聯(lián)次數(shù)為 1。 若