連通性 (Connectivity) 將公司標幟插入此投影片 選取〔插入〕功能表 中的〔圖片〕選項 選取〔從檔案〕指令 選取該圖片檔案

Presentation on theme: "連通性 (Connectivity) 將公司標幟插入此投影片 選取〔插入〕功能表 中的〔圖片〕選項 選取〔從檔案〕指令 選取該圖片檔案"— Presentation transcript:

1 連通性 (Connectivity) 將公司標幟插入此投影片 選取〔插入〕功能表 中的〔圖片〕選項 選取〔從檔案〕指令 選取該圖片檔案
按下〔確定〕按鈕 調整商標的大小 於商標圖示內按一下﹐此時商標圖示外的白色小方塊即為可調整大小的圖框。 利用該圖框來調整物件大小 如果你在調整邊框之前﹐先按住Shift 鍵，便可維持該物件的比例。 連通性 (Connectivity)

2 1.切點與切集（Cut Vertices and Cut Set）
定義 1.1 在一個圖Ｇ中，如果 c(G-v)  c(G)，則ｖ稱為是G的一個切點（Cut Vertex）。 定義 1.2 ｖ是連通圖Ｇ切點之充要條件是存在兩個與ｖ不同的點ｕ及ｗ，同時滿足所有由ｕ到ｗ的路徑皆會通過ｖ點。

3 定理 1.3 一個兩點以上的圖，除了空圖（沒有邊）之外都至少含有兩點，它們都不是切點。 定理 1.4 （點連通數，Connectivity） 一個圖G的點連通數 且Ｇ-Ｓ為不連通圖或是剩下一點}.

4 所以，當Ｇ本身不連通時， ；如果G中含有切點而本身又是連通圖，則 。例如，樹圖或是 ；當然任意圈的點連通數都是２。爲了方便起見，一般把滿足 的圖Ｇ，稱為ｎ-連通圖，所以所謂的1-連通圖就是指一般的連通圖。同時，在一個ｎ-連通圖中，＂至少＂要拿走ｎ個點才可能得到一個不連通的子圖。

5 定義1.6（分隔集，Separating Set）
定理1.5 令Ｇ為具有ｐ個點的圖，它的度數列為 ，同時 ，如果對於所有的 ， ，則Ｇ為一個ｎ-連通圖。 定義1.6（分隔集，Separating Set） 一個 V(G) 的子集合Ｓ稱為是兩點ｕ與ｖ的分隔集，如果ｕ與ｖ分別落在Ｇ-Ｓ的兩個部份裡面。

6 令ｕ與ｖ為Ｇ中不相鄰的兩點，則 u,v 的分隔數恰好等於由ｕ到ｖ沒有共用點（Internally Disjoint）的路徑數。
定理 1.7 （Menger, 1927） 令ｕ與ｖ為Ｇ中不相鄰的兩點，則 u,v 的分隔數恰好等於由ｕ到ｖ沒有共用點（Internally Disjoint）的路徑數。 有了Menger的定理，Whitney很順利地刻劃出ｎ-連通圖。 定理 1.8 一個圖為ｎ-連通的充要條件為任兩點皆存在有ｎ條互斥的路徑相連。

7 定理 1.9 一個具有2ｎ個點的圖，它是ｎ-連通的充要條件為這個圖的點集合可以任意分割成兩個大小一樣的子集合 與 ，同時存在有ｎ條互斥路徑連接 與 的點。 定理 1.10 假如Ｇ是一個ｎ-連通圖，則Ｇ中的任意ｎ個點都會落在一個圈上。

8 一個圖Ｇ為3-連通圖的充要條件為Ｇ本身是一個輪圖（圖 一），或者是Ｇ可以由下列兩類型的運算從一個輪圖建構出來：
定理 1.11 一個圖Ｇ為3-連通圖的充要條件為Ｇ本身是一個輪圖（圖 一），或者是Ｇ可以由下列兩類型的運算從一個輪圖建構出來： (i) 加一個新邊； (ii) 把度數超過３的點ｖ，用相鄰的兩點 與 取代，使得 在新圖中，每個 在中點和 與 之一相連，同時維 持 及 。（圖二） 圖一 圖二

9 2.橋與邊切集（Bridge, Edge-Cut Set）
定義 2.1 在一個圖Ｇ中，如果 則ｅ稱為是Ｇ的橋。 定義 2.2（邊連通數, Edge-Connectivity） 一個圖Ｇ的邊連通數 且Ｇ－Ｔ為不連通圖｝。（這裡的Ｇ－Ｔ代表依次從Ｇ中扣掉Ｔ中的邊所得到的圖。）

10 定理 2.3 對於任意圖Ｇ，令 代表Ｇ中點的最小度數。則 。 定義 2.4 一個圖Ｇ在 時，稱為是ｎ-邊連通，亦即去掉Ｇ中的任何ｎ-1個邊都無法獲得不連通圖。

11 定理 2.5 一個圖Ｇ是ｎ－邊連通的充要條件為在 中不存在有一個非空子集合Ｗ，使得 中的邊數小於ｎ，這裡的 代表所有在Ｇ中由Ａ中點連到Ｂ中點的邊所成的集合。 定理 2.6 一個圖是ｎ－邊連通的充要條件為任兩點間皆可以找到ｎ條路徑，它們沒有共同使用的邊。

12 定理 2.7（Plesnik） 如果Ｇ的直徑為2，則 。 推論 2.8 在一個圖Ｇ中，如果不相鄰兩點的度數和皆大於 ，則 。 作業 6 任給三個正整數 ，證明必存在一個圖它滿足 ， 及 。

13 3.網路（Networks） 一個網路Ｎ是一個具有特殊性質的有向圖Ｄ，它具有下列特性： 有一個點ｓ叫出發點(Source)，有一個點ｔ叫
終點（Sink） (ii)Ｄ的弧上每一個弧都指定一個非負整數，稱為是容量(Capacity)，這個指定的動作也稱為是一個容量函數(Capacity function)。

14 定義 3.1（Flow） 令ｃ為網路Ｎ的一個容量函數，同時ｓ和ｔ分別為網路的出發點和終點。一個網路的物流是指一個定義在 上的一個整數值函數ｆ，它滿足下列兩個條件： (i) ；以及 (ii) 對於所有不同於ｓ和ｔ的點， ，其中 。 （保守方程，Conservation Equation）。

15 定理 3.2 令Ｎ為一個網路，它的起點與終點分別為ｓ、ｔ。同時Ｄ為決定Ｎ的有向圖，則對於Ｎ中的任一個物流ｆ， 。 定義 3.3（網路切集，Cut） 在一個網路Ｎ中，令Ｘ為包含起點ｓ的集合，同時 ，則 為網路Ｎ的一個切集。切集容量的大小為 ，一般也用capＫ表示。

16 定理 3.4 對於Ｎ中任意物流ｆ以任意切集 ， 推論 3.5（min-max性質） 令ｆ與ｋ分別為Ｎ中的一個物流及切集，同時滿足 ，則ｆ為最大物流，Ｋ為最小切集（容量和最小）。 推論 3.6　 如果ｆ與ｃ分別為網路Ｎ的物流及容量函數，同時滿足： （１）對於所有的 ， 及 （２）對於所有的 ， 。 則ｆ為最大物流， 為最小切集。

17 定理 3.7 網路Ｎ中的物流ｆ為最大物流的充要條件是在Ｎ中的Ｄ找不到ｆ－可增值的半路徑。 定理 3.8（Ford 及 Fulkerson） （最大流量－最小切集定理） 在一個網路中，最大流量恰等於最小切集的容量。