【正文】 G=V,E, V??V V?為 點割集 —— p(G?V?)p(G)且有極小性 v為 割點 —— {v}為點割集 定義： G=V,E, E??E E?是 邊割集 —— p(G?E?)p(G)且有極小性 e是 割邊 （橋） —— {e}為邊割集 ? 上例中 {v2,v5}是點割集嗎？ {e7,e9,e5,e6} 是邊割集嗎？ 例： {v1,v4}， {v6}是點割集，v6是割點。 ch gbadef例 ： 給定右圖所示 V/R={ {a,b,g}， {c,d,e,f}， {h} } School of Information Science and Engineering 143 圖的連通性 ［ G的連通性與連通分支 ］ ① 若 ?u, v?V， u?v，則稱 G是連通的 ② V/R={V1,V2,…, Vk}，稱 等價類構(gòu)成的子圖 G[V1], G[V2], …, G[Vk]為 G的連通分支 ，其個數(shù) p(G)=k (k?1)； k=1， G是連通的。 ［結(jié)點之間的連通關(guān)系是個等價關(guān)系］ 令 G=V, E是無向圖， R是 V上連通關(guān)系，即 R={u,v| u,v ?V且 u?v} 顯然 R具有自反、對稱和傳遞性。 School of Information Science and Engineering 142 通路與回路 [表示法 ] ① 定義表示法 ② 只用邊表示法 ③ 只用頂點表示法（在簡單圖中） ④ 混合表示法 環(huán) （長為 1的圈）的長度為 1，兩條平行邊構(gòu)成的圈長度為 2，無向簡單圖中，圈長 ?3，有向簡單圖中圈的長度 ?2. [不同的圈 ]（以長度 ?3的為例） ① 定義意義下 無向圖：圖中長度為 l（ l?3）的圈，定義意義下為 2l個 有向圖：圖中長度為 l（ l?3）的圈，定義意義下為 l個 ② 同構(gòu)意義下：長度相同的圈均為 1個 School of Information Science and Engineering 142 通路與回路 [定理 ] 在 n 階圖 G中，若從頂點 vi 到 vj（ vi?vj）存在通路，則從 vi 到 vj 存在長度小于或等于 n?1 的通路 . [推論 ] 在 n 階圖 G中，若從頂點 vi 到 vj（ vi?vj）存在通路，則 從 vi 到 vj 存在長度小于或等于 n?1的初級通路（路徑） . [定理 ] 在一個 n 階圖 G中，若存在 vi 到自身的回路，則一定存在 vi 到自身長度小于或等于 n 的回路 . [推論 ] 在一個 n 階圖 G中，若存在 vi 到自身的簡單回路，則一定存在長度小于或等于 n 的初級回路 . vi… . . . … . . .… . . .vi + 1vs 1vt + 1vjvs= vtvj 1 School of Information Science and Engineering 143 圖的連通性 1. 無向圖的連通性 ［兩個結(jié)點連通］ 在無向圖中，結(jié)點 u和 v之間如果存在一條通 路 ， 則稱 u與 v是連通的 。 (3) 初級通路 (路徑 )與初級回路 (圈 )： ? 中所有頂點各異，則稱 ? 為 初級通路 (路徑 )，又若除 v0=vl，所有的頂點各不相同且所有的邊各異，則稱 ? 為 初級回路 (圈 )。 (1) 通路與回路： ? 為 通路 ；若 v0=vl， ? 為 回路 ， l 為 回路長 度 。 相對于 K4, 求上面圖中所有圖的補圖，并指出哪些是自補圖。 School of Information Science and Engineering 141 圖 [補圖 ] 定義： 設(shè) G=V,E為 n階無向簡單圖，以 V為頂點集，以所有使G成為完全圖 Kn的添加邊組成的集合為邊集的圖，稱為 G的補圖 ，記作 。 簡單性質(zhì)：邊數(shù) ［競賽圖］ 基圖為 Kn的有向簡單圖。如果 G有 n個結(jié)點 , 則記作 Kn。 ② 度數(shù)序列相同 。 哪些是 可 簡單圖 化的 ? a) (1, 2, 3, 4, 5) b) (2, 2, 2, 2, 2) c) (1, 2, 3, 2, 4) G中 ,有 10條邊 ， 4個 3度結(jié)點 ,其余結(jié)點的度均小于或等于 2， 問 G中至少有多少個結(jié)點 ？ 為什么 ？ School of Information Science and Engineering 141 圖 [圖的同構(gòu) ] 設(shè) G1=V1,E1, G2=V2,E2為兩個無向圖 (兩個有向 圖 )，若存在雙射函數(shù) f:V1?V2, 對于 vi,vj?V1, (vi,vj)?E1 當且僅當 (f(vi),f(vj))?E2 （ vi,vj?E1 當且僅當 f(vi),f(vj)?E2 ) 并且 , (vi,vj)（ vi,vj）與 (f(vi),f(vj))（ f(vi),f(vj)）的重數(shù)相 同，則稱 G1與 G2是 同構(gòu) 的，記作 G1?G2。 [n階 k正則圖 ] 一個無向簡單圖 G中 ,如果 Δ(G)=δ(G)=k，則稱 G為 k正則圖 。 School of Information Science and Engineering 141 圖 [無向圖的結(jié)點度序列 ] V={v1, v2, …, vn}為無向圖 G的頂點集，稱 d(v1), d(v2), …, d(vn)為G的 度數(shù)序列 。 School of Information Science and Engineering 141 圖 [定義 ] (1) 設(shè) G=V,E為無向圖 , ?v?V, d(v)—— v的度數(shù) , 簡稱度 (2) 設(shè) D=V,E為有向圖 , ?v?V, d+(v)—— v的出度 d?(v)—— v的入度 d(v)—— v的度或度數(shù) (3) ?(G), ?(G) (4) ?+(D), ?+(D), ??(D), ??(D), ?(D), ?(D) (5) 奇度頂點與偶度頂點 Scho