Some Special Set On Path-Arc Structure

本文是記錄一些使用集合論語言，表達路徑(Path)/線段(Undirected Arc) 組成的關係:

令所有的路徑集為 $p \in P$，所有的線段集 $a \in A$

路徑是由許多線段(無方向性)所組成的，自然存在對應關係 $E \subseteq P\times A$，可使用圖論二分圖描述 $G(P\cup A,E)$
可以定義相依集： $$P_{a}:=\{p\in P : (p,a)\in E \},A_{p}:= \{a\in A :(p,a) \in E \}$$  

並且滿足以下自然對偶邏輯(Natural Dual Correspondence)

$$\bigwedge_{(p,a)\in P\times A} \left( p \in P_a  \Longleftrightarrow a \in A_{p}  \right)$$

如果$X_a$為線段長，則很明顯路徑長可寫為 $$\bigwedge_{p \in P}\left( X_{p}:= X(A_p) = \sum_{a\in A_p} X_{a} \right)$$

路徑長公式可以寫成線性系統　 $$X_{P} := M_{P\times A} X_{A}$$

(其中$X_P$,$X_{A}$ 為向量，$M_{P\times A}$ 為 $0-1$ adjacency sparse  matrix)

由線性系統可以求出反矩陣，而導出 $X_{A}= M^{-1}_{P\times A}X_{P}$)

定義 $p$ 損壞必定影響的路徑集

$$\bigwedge_{p\in P}\left( P^{\cap}_{p}:= \bigcap_{a\in A_{p}} P_{a} \right)$$

代表只要路徑 $p$ 斷了，則所有路徑 $p' \in P^{\cap}_{p}$ 也必定會斷，($p$是$p'$的一部分)  $$\bigwedge_{p \in P}\bigwedge_{p' \in P^{\cap}_{p}} \left(A_{p} \subseteq A_{p'}\right)$$

定義 $p$ 損壞可能影響的路徑集

$$\bigwedge_{p \in P} \left( P^{\cup}_{p}:= \bigcup_{a\in A_{p}}P_{a} \right)$$

也就是兩路徑有部分的線段共同組成 $$\bigwedge_{p \in P}\bigwedge_{p' \in P^{\cup}_{p}}\left(A_{p} \cap A_{p'} \neq \emptyset\right)$$

定義完全跟 $p$ 無關的路徑集(與 $p$ 獨立)　

$$\bigwedge_{p \in P} \left(P^{\times}_{p}:= P\setminus P^{\cup}_{p}\right)$$

也就是兩路徑沒有共同線段組成

$$\bigwedge_{p \in P}\bigwedge_{p' \in P^{\times}_{p}}\left(A_{p} \cap A_{p'} = \emptyset\right)$$

給定一些路徑集　$P' \subset P$ ，可以定義必定會經過的線段集

$$A^{kernel}(P'):=\bigcap_{p \in P'} A_{p}$$

系統核心線段可寫成　

$$A^{kernel} :=\bigcap_{p \in P}A_{p}$$


[小結]
這些集合口語上很難表達，而本文利用相依集交集聯集來描述，方便讀者能夠正確計算出集合!!

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

by Plus & Minus 2018.03