本文介紹在一張簡單無向圖 $G(V,E^{<})$上，點記做 $i,j \in V$。
每個邊 $e := \{i,j\} \in E^{<}$ ，Either 連通=0 or 不連通=1。今給定起訖點 $o,d \in V , o \neq d$ ，od-pair 記做 $<o,d>$ ，由於可能有很多替代的路徑可以從 $o$ 走到 $d$
如何描述(表達集合) $<o,d>$ 為連通/不連通時"邊集"的情況 ??
======================================================
預備知識:
$$\displaystyle{ \bigwedge_{s \in S}} Equation(s) $$
是邏輯大 And 或可嚴謹讀作 $\forall s \in S , Equation(s) \text{ is true}$
$$ \displaystyle{\bigvee_{s \in S} } Equation(s) $$
是邏輯的大 Or 或可讀作 $ \exists s \in S , Equation(s) \text{ is true }$
======================================================
符號定義:
1. $\mathcal{P}_{<o,d>}$ 為起點為 $o$，終點為 $d$ 所有"路徑名稱(下標 index)"的集合
2. $ E^{<}_{p} \subseteq E^{<}$ 路徑 $p \in \mathcal{P}_{<o,d>}$ 經過的無向邊集
3. 起訖點$<o,d>$可能會經過的所有無向邊的集合(路徑是由"邊"組成的) $$\displaystyle{E^{<}_{<o,d>} := \bigcup_{p \in \mathcal{P}_{<o,d>}} E^{<}_{p} } \subseteq E^{<}$$
4. 令向量 $ y \in \{0,1\}^{E^{<}_{<o,d>}}$ 為連通性可能情況，其中 $$ y \equiv (y_{e})_{e\in E^{<}_{<o,d>}} \quad , \bigwedge_{e\in E^{<}_{<o,d>}} \bigg( y_{e} = 1 \Longleftrightarrow e \text{ 不連通} \bigg) $$
5. 兩點下標表示法: $y_{e} \equiv y_{ij}$
==================================================
實作小技巧:
$\mathcal{P}_{<o,d>}$ , $E^{<}_{p}$ 可由 $DFS$ 窮舉路徑演算法獲得，詳細可看~
https://www.geeksforgeeks.org/find-paths-given-source-destination/
但實作上演算法可能為"有向邊"思維，儲存時須特別注意!!
例如某路徑 $p$，經過的順序為 $5 \rightarrow 2 \rightarrow 3 \rightarrow 2 \rightarrow 4$
由於 $2 \rightarrow 3$ , $3 \rightarrow 2$ 事實上是經過同一個邊 $e = \underbrace{\{2,3\} = \{3,2\}}_{ \{ \cdot , \cdot \} \text{ 表示無向邊化}} = (2,3)$
所以紀錄 $E^{<}_{p}$ 時應該為 $\{ (2,5),(2,3),(2,4) \}$ 註: 給定排序 $i<j$ 記法 ，可以定義 $y_{25} , y_{23} , y_{24}$ 二元布林值 !!!
而非單純 bi-gram $\{ (5,2),(2,3),(3,2),(2,4) \}$
=================================================
$<o,d>$ 不連通邊集 :
$$Y^{disconnected}_{<o,d>}:= \bigg\{ y \in \{0,1\}^{|E^{<}_{<o,d>}|} : \bigwedge_{p \in \mathcal{P}_{<o,d>}}\left(\sum_{e \in E^{<}_{p}} y_{e} \geq 1 \right) \bigg\}$$
邏輯意義: 對於每條可以走的路徑 $p \in \mathcal{P}_{<o,d>}$ ，都存在至少一個無向邊 $e \in E^{<}_{p}$ 是不連通的 $y_{e} = 1$，即沒有任何一條路可以通，代表 $<o,d>$ 不連通!!
=================================================
關於連通邊集，就是下面的集合 !!
$$Y^{connected}_{<o,d>}:= \bigg\{ y \in \{0,1\}^{|E^{<}_{<o,d>}|} : \bigvee_{p \in \mathcal{P}_{<o,d>}}\left(\sum_{e \in E^{<}_{p}} y_{e} = 0 \right) \bigg\} $$
==================================================
定義 $y_{p}$:
但我們希望把連通集轉換成 Big-And 形式 !!
需要先另外新定義向量 $(y_p)_{p \in \mathcal{P}_{<o,d>}} \in \{0,1\}^{|\mathcal{P}_{<o,d>}|}$，表示路徑 $p$ 是否連通的布林值!! 註: $y_e$ , $y_p$ 是不同的定義
而且以下三個邏輯也成立:
[1]
$$\bigwedge_{p \in \mathcal{P}_{<o,d>}}\bigwedge_{e \in E^{<}_{p}} \bigg(y_e = 1 \Longrightarrow y_p = 1 \bigg)$$
邏輯白話解釋: 如果邊 $e$ 不連通，則整條含$e$的路徑$p$就不連通
[2]
$$\bigwedge_{p \in \mathcal{P}_{<o,d>}}\left[y_p = 1 \not\Longrightarrow \left( \bigwedge_{e \in E^{<}_{p}} (y_e = 1) \right) \right] $$
邏輯白話解釋 : 如果路徑 $p$ 不連通，不代表 所有在路徑上的邊 $e$ 都不連通
[3]
$$\bigwedge_{p \in \mathcal{P}_{<o,d>}}\left[y_p = 1 \Longrightarrow \left( \bigvee_{e \in E^{<}_{p}} (y_e = 1) \right) \right] $$
邏輯白話解釋: 如果路徑 $p$ 不連通，代表 存在路徑上的邊 $e$ 不連通
可以使用之前整數規劃的技巧文章詳細如下:
http://discoverforgottenmath.blogspot.com/2017/09/why-integer-programming-is-important-in.html
[1] 可寫成:
$$\bigwedge_{p \in \mathcal{P}_{<o,d>}}\bigwedge_{e \in E^{<}_{p}} \left( y_e \leq y_p \right) $$
[3] 可寫成:
$$ \bigwedge_{p \in \mathcal{P}_{<o,d>}}\left( y_{p} \leq \sum_{e\in E^{<}_{p}}y_{e} \right) $$
由於我們已經有 $y_{e}$ , $y_{p}$ 的邏輯關係，$<o,d>$連通性可以直接用 $ \exists p \in \mathcal{P}_{<o,d>} , y_{p} = 0 $ 表示，也就是以下 [4]
$$ \sum_{p\in \mathcal{P}_{<o,d>}} y_{p} \leq \underbrace{\left(|\mathcal{P}_{<o,d>}| - 1\right)}_{\text{不讓 $y_{p}$ 全部塞 $1$}} $$
重新把 $y$ 向量定義成兩個向量 $(y_{p})_{p \in \mathcal{P}_{<o,d>}}$,$(y_{e})_{e\in E^{<}_{<o,d>}}$的 concatenate，則我們有連通邊集的 Big-And 形式 (但需要增加 $y$ 的維度 !! )
$$Y^{connected}_{<o,d>} \equiv \left\{ y \in \{0,1\}^{|E^{<}_{<o,d>}|+|\mathcal{P}_{<o,d>}|} : [4] \wedge \bigwedge_{p \in \mathcal{P}_{<o,d>}}\left\{ \begin{array}{cc} \bigwedge_{e \in E^{<}_{p}} \left( y_e \leq y_p \right) & [1] \\ y_{p} \leq \sum_{e\in E^{<}_{p}}y_{e} &[3] \\ \end{array} \right. \quad \right\} $$
==================================================
[演算法相關]
關於為何我們需要 Big-And 邏輯形式是因為可以寫成"線性矩陣系統" :D
$$ \bigwedge_{r \in \text{rows}} \left( \sum_{c \in \text{columns} } a_{rc}y_c \leq b_r \right) \Longleftrightarrow \text{Create Set} Y:= \bigg\{y \in \{0,1\}^{|columns|} : Ay \leq b \bigg\} $$
而線性矩陣系統如 $Y$ 可以使用 Constraint Programming (CP) 高效率演算法窮舉出其每個元素 :) 其演算法 Google 有開源有興趣可以詳見:
https://developers.google.com/optimization/
而如果要更高速計算 $|Y|$ 可以使用高深理論的 Barvinok algorithm :D，但因為筆者功力目前不夠深厚無法詳細解釋，但有連結: http://www.maths.ed.ac.uk/~v1ranick/papers/barvpomm.pdf
[小結]
本文利用邏輯觀念與限制式，建構出"連通方程式/集合"，連通的概念是重要的，跟系統可靠度(reliability)息息相關 !!
每個邊 $e := \{i,j\} \in E^{<}$ ，Either 連通=0 or 不連通=1。今給定起訖點 $o,d \in V , o \neq d$ ，od-pair 記做 $<o,d>$ ，由於可能有很多替代的路徑可以從 $o$ 走到 $d$
如何描述(表達集合) $<o,d>$ 為連通/不連通時"邊集"的情況 ??
======================================================
預備知識:
$$\displaystyle{ \bigwedge_{s \in S}} Equation(s) $$
是邏輯大 And 或可嚴謹讀作 $\forall s \in S , Equation(s) \text{ is true}$
$$ \displaystyle{\bigvee_{s \in S} } Equation(s) $$
是邏輯的大 Or 或可讀作 $ \exists s \in S , Equation(s) \text{ is true }$
======================================================
符號定義:
1. $\mathcal{P}_{<o,d>}$ 為起點為 $o$，終點為 $d$ 所有"路徑名稱(下標 index)"的集合
2. $ E^{<}_{p} \subseteq E^{<}$ 路徑 $p \in \mathcal{P}_{<o,d>}$ 經過的無向邊集
3. 起訖點$<o,d>$可能會經過的所有無向邊的集合(路徑是由"邊"組成的) $$\displaystyle{E^{<}_{<o,d>} := \bigcup_{p \in \mathcal{P}_{<o,d>}} E^{<}_{p} } \subseteq E^{<}$$
4. 令向量 $ y \in \{0,1\}^{E^{<}_{<o,d>}}$ 為連通性可能情況，其中 $$ y \equiv (y_{e})_{e\in E^{<}_{<o,d>}} \quad , \bigwedge_{e\in E^{<}_{<o,d>}} \bigg( y_{e} = 1 \Longleftrightarrow e \text{ 不連通} \bigg) $$
5. 兩點下標表示法: $y_{e} \equiv y_{ij}$
==================================================
實作小技巧:
$\mathcal{P}_{<o,d>}$ , $E^{<}_{p}$ 可由 $DFS$ 窮舉路徑演算法獲得，詳細可看~
https://www.geeksforgeeks.org/find-paths-given-source-destination/
但實作上演算法可能為"有向邊"思維，儲存時須特別注意!!
例如某路徑 $p$，經過的順序為 $5 \rightarrow 2 \rightarrow 3 \rightarrow 2 \rightarrow 4$
由於 $2 \rightarrow 3$ , $3 \rightarrow 2$ 事實上是經過同一個邊 $e = \underbrace{\{2,3\} = \{3,2\}}_{ \{ \cdot , \cdot \} \text{ 表示無向邊化}} = (2,3)$
所以紀錄 $E^{<}_{p}$ 時應該為 $\{ (2,5),(2,3),(2,4) \}$ 註: 給定排序 $i<j$ 記法 ，可以定義 $y_{25} , y_{23} , y_{24}$ 二元布林值 !!!
而非單純 bi-gram $\{ (5,2),(2,3),(3,2),(2,4) \}$
=================================================
$<o,d>$ 不連通邊集 :
$$Y^{disconnected}_{<o,d>}:= \bigg\{ y \in \{0,1\}^{|E^{<}_{<o,d>}|} : \bigwedge_{p \in \mathcal{P}_{<o,d>}}\left(\sum_{e \in E^{<}_{p}} y_{e} \geq 1 \right) \bigg\}$$
邏輯意義: 對於每條可以走的路徑 $p \in \mathcal{P}_{<o,d>}$ ，都存在至少一個無向邊 $e \in E^{<}_{p}$ 是不連通的 $y_{e} = 1$，即沒有任何一條路可以通，代表 $<o,d>$ 不連通!!
=================================================
關於連通邊集，就是下面的集合 !!
$$Y^{connected}_{<o,d>}:= \bigg\{ y \in \{0,1\}^{|E^{<}_{<o,d>}|} : \bigvee_{p \in \mathcal{P}_{<o,d>}}\left(\sum_{e \in E^{<}_{p}} y_{e} = 0 \right) \bigg\} $$
==================================================
定義 $y_{p}$:
但我們希望把連通集轉換成 Big-And 形式 !!
需要先另外新定義向量 $(y_p)_{p \in \mathcal{P}_{<o,d>}} \in \{0,1\}^{|\mathcal{P}_{<o,d>}|}$，表示路徑 $p$ 是否連通的布林值!! 註: $y_e$ , $y_p$ 是不同的定義
而且以下三個邏輯也成立:
[1]
$$\bigwedge_{p \in \mathcal{P}_{<o,d>}}\bigwedge_{e \in E^{<}_{p}} \bigg(y_e = 1 \Longrightarrow y_p = 1 \bigg)$$
邏輯白話解釋: 如果邊 $e$ 不連通，則整條含$e$的路徑$p$就不連通
[2]
$$\bigwedge_{p \in \mathcal{P}_{<o,d>}}\left[y_p = 1 \not\Longrightarrow \left( \bigwedge_{e \in E^{<}_{p}} (y_e = 1) \right) \right] $$
邏輯白話解釋 : 如果路徑 $p$ 不連通，不代表 所有在路徑上的邊 $e$ 都不連通
[3]
$$\bigwedge_{p \in \mathcal{P}_{<o,d>}}\left[y_p = 1 \Longrightarrow \left( \bigvee_{e \in E^{<}_{p}} (y_e = 1) \right) \right] $$
邏輯白話解釋: 如果路徑 $p$ 不連通，代表 存在路徑上的邊 $e$ 不連通
可以使用之前整數規劃的技巧文章詳細如下:
http://discoverforgottenmath.blogspot.com/2017/09/why-integer-programming-is-important-in.html
[1] 可寫成:
$$\bigwedge_{p \in \mathcal{P}_{<o,d>}}\bigwedge_{e \in E^{<}_{p}} \left( y_e \leq y_p \right) $$
[3] 可寫成:
$$ \bigwedge_{p \in \mathcal{P}_{<o,d>}}\left( y_{p} \leq \sum_{e\in E^{<}_{p}}y_{e} \right) $$
由於我們已經有 $y_{e}$ , $y_{p}$ 的邏輯關係，$<o,d>$連通性可以直接用 $ \exists p \in \mathcal{P}_{<o,d>} , y_{p} = 0 $ 表示，也就是以下 [4]
$$ \sum_{p\in \mathcal{P}_{<o,d>}} y_{p} \leq \underbrace{\left(|\mathcal{P}_{<o,d>}| - 1\right)}_{\text{不讓 $y_{p}$ 全部塞 $1$}} $$
重新把 $y$ 向量定義成兩個向量 $(y_{p})_{p \in \mathcal{P}_{<o,d>}}$,$(y_{e})_{e\in E^{<}_{<o,d>}}$的 concatenate，則我們有連通邊集的 Big-And 形式 (但需要增加 $y$ 的維度 !! )
$$Y^{connected}_{<o,d>} \equiv \left\{ y \in \{0,1\}^{|E^{<}_{<o,d>}|+|\mathcal{P}_{<o,d>}|} : [4] \wedge \bigwedge_{p \in \mathcal{P}_{<o,d>}}\left\{ \begin{array}{cc} \bigwedge_{e \in E^{<}_{p}} \left( y_e \leq y_p \right) & [1] \\ y_{p} \leq \sum_{e\in E^{<}_{p}}y_{e} &[3] \\ \end{array} \right. \quad \right\} $$
==================================================
[演算法相關]
關於為何我們需要 Big-And 邏輯形式是因為可以寫成"線性矩陣系統" :D
$$ \bigwedge_{r \in \text{rows}} \left( \sum_{c \in \text{columns} } a_{rc}y_c \leq b_r \right) \Longleftrightarrow \text{Create Set} Y:= \bigg\{y \in \{0,1\}^{|columns|} : Ay \leq b \bigg\} $$
而線性矩陣系統如 $Y$ 可以使用 Constraint Programming (CP) 高效率演算法窮舉出其每個元素 :) 其演算法 Google 有開源有興趣可以詳見:
https://developers.google.com/optimization/
而如果要更高速計算 $|Y|$ 可以使用高深理論的 Barvinok algorithm :D，但因為筆者功力目前不夠深厚無法詳細解釋，但有連結: http://www.maths.ed.ac.uk/~v1ranick/papers/barvpomm.pdf
[小結]
本文利用邏輯觀念與限制式，建構出"連通方程式/集合"，連通的概念是重要的，跟系統可靠度(reliability)息息相關 !!
[以上純為學術經驗交流知識分享，如有錯誤或建議可留言~~]
by Plus & Minus 2018.06
留言
張貼留言