Constraint Programming on Graph Connectedness

本文介紹在一張簡單無向圖 $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)息息相關 !!

[以上純為學術經驗交流知識分享，如有錯誤或建議可留言~~] 

by Plus & Minus 2018.06