本篇介紹一些筆者認為重要的整數規劃-圖形，邏輯建模技巧與概念，關於整數規劃的用途，可先參考之前這篇: http://discoverforgottenmath.blogspot.tw/2017/09/why-integer-programming-is-important-in.html 而建模技巧是把日常生活中的邏輯給正確的連結到方程式上!! 以下我們都把 $X \in \{0,1\}$ 視為  boolean 決策變數 ======================================= 刻劃出點 Node $i , j$ 跟邊 Arc $(i,j)$ 關係 ======================================= 定義: $X_{i} = 1  \text{ iff }  $ 我選擇了點 $i$ $X_{ij} = 1  \text{ iff }  $ 我選擇了邊 $(i,j)$ $$(E1) \quad \text{if  $(i,j)$ is selected  then ($i$ and $j$) are selected} $$ $$ \left\{\begin{array}{c} X_{(i,j)}\leq X_i \\ X_{(i,j)}\leq X_j \\ \end{array}\right.$$ $$(E2) \quad \text{if ($i$ and $j$) are selected then $(i,j)$ is selected } $$ $$ X_{i}+X_{j} \leq 1+X_{(i,j)} $$ $(E1)$ 是現實生活中自然的邏輯: 意涵代表，我選擇了這條邊 $(i,j)$ 則我自然會 cover $i , j$ 這兩個點 $(E2)$ 則不一定會有的邏輯，需思考 $(i,j)$ 的定義 例如:  我定義 $(i,j)$ 為直接從 $i$ 走到 $j$ 則走路徑 $(i \rightarrow j \rightarrow k \rightarrow w)$ 則 $X_{i}=1 , X_{w} =1 $ 但是 $X_{(i,w)} = 0$ ，就不滿足 $(E2)$ 的邏輯 註: 結合 $(E1)$ and $(E2)$ 兩個

本篇以隨筆平易近人的方式，寫一些如何降低演算法"計算量"的一些核心抽象概念。 [利用分配律尋找完全多分圖] 相信大家都知道加法$(+)$ ，乘法$(\times)$ 分配律的概念，複習一下 $$   (A+B)\times (C+D)   =A \times C + B \times C + A \times D + B \times D$$ 左式推廣我們可以寫成 $$ \underbrace{(A_1+A_2+....+A_{L_1})}_{\text{第一組}}\times  \underbrace{(B_1+B_2+....+B_{L_2})}_{\text{第二組}} \times ...  \times \underbrace{( ... )}_{\text{第 $m$ 組}}  $$ 每一組 有$L_{i}$ 個元素，總共有 $L$ 個元素(字母) 而且每一組有 $L_{i} -1$ 個加法，總共就有 $$\displaystyle{\sum^{m}_{i=1}(L_i - 1) =  L - m } \text{ 個加法} $$ 由於每一組中間穿叉乘法，有 $m-1$ 個乘法。我們分別把加法，乘法個數記做 ~ $\otimes $ , $ \oplus$，所以左式總共的運算數為 $$  \text{左式運算量 = } (m-1) \cdot \otimes  + (L-m) \cdot \oplus    $$ 右式完全展開，非常多項，要完整寫出來並非容易的事，但是我們知道它應該是長這樣 $$ (\text{第一組連乘}) + (\text{第二組連乘} ) + (\text{第三組連乘} ) + ........ $$ 至於究竟有幾組連乘呢 ?? 答案是 $\displaystyle{ \prod^{m}_{i=1}L_i }$ 組，而每一組中間穿叉 $L_i -1$ 乘法 右式總運算量為 $$ \text{右式運算量 = } (L-m)\cdot \otimes  + \displaystyle{ \prod^{m}_{i=1}L_i } \cdot \oplus    $$ 如果符號間加法 $+$ 運算時間 $\leq$ 乘法符號間 $ \times $ 運算的