---
# System prepended metadata

title: 課程｜離散數學
tags: [課程]

---

# 離散數學


# 1.Counting
## Principle of Inclusion and Exclusion排容原理
- The Principle
    - $N(\bar{c_1}\bar{c_2}\bar{c_3})=N$
    &emsp;&emsp;&emsp;&emsp;&emsp;$-(~N(c_1)+N(c_2)+N(c_3)~)$
    &emsp;&emsp;&emsp;&emsp;&emsp;$+(~N(c_1c_2)+N(c_1c_3)+N(c_2c_3)~)$
    &emsp;&emsp;&emsp;&emsp;&emsp;$-N(c_1c_2c_3)$
    - $S$：是一個集合，大小為 $N$
    - $c_i$：表示某個 $condition$，是 $S$ 的 subset
    - $N(c_i)$表示S中滿足$c_i$的個數
        - $Pf_1$：集合論+數學歸納法
        - $Pf_2$：Combinatorial method.
            - Case 1. x satisfies none of the conditions.
            - Case 2. x satisfies r of the conditions, where 1 ≤ r ≤ t.
    - 其他公式：
        - $N(c_1$+$c_2$+$c_3)=N-N(\bar{c_1}\bar{c_2}\bar{c_3})$
        - **Satisfy exactly m of t conditions**
        - **Satisfy at least m of t conditions**
- Euler’s phi function
    - 若 $n=p_1^{e_1}~p_2^{e_2}~...~p_n^{e_n}$，則 $1$ ~ $n$ 中和 $n$ 互質的個數
      $\phi(n)=n\times(1-\frac{1}{p_1})\times(1-\frac{1}{p_2})\times ...\times(1-\frac{1}{p_n})$
- Derangements 
    - **Derangement** is an arrangement s.t. every number is not in its natural position.
        - The numbers of derangement of 1, ..., 10 is
          $N(\bar{c_1}\bar{c_2}...\bar{c_{10}})=10!-\begin{pmatrix}10\\1\end{pmatrix}9!+...+\begin{pmatrix}10\\10\end{pmatrix}0!=1334960$
- Rook Polynomials 
    - 給定棋盤 $C$，$r_k$ 表示放 $k$ 個車在棋盤上的可能數。
    - Rook polynomial：$R(C,x)=\sum r_ix^i$
    - 若C可拆成disjoint的 $C_1$ 和 $C_2$ ，則 $R(C, x) = R(C_1, x) \cdot R(C_2, x)$
    - $R(C, x) = xR(C_s, x) + R(C_e, x)$
    - ![](https://i.imgur.com/xQlBjl2.png) $R(C,x)=(1+3x+x^2)\cdot(1+4x+3x^2)\\~~~~~~~~~~~~~=1+7x+16x^2+13x^3+3x^4$
    - $N(\bar{c_1}\bar{c_2}\bar{c_3}\bar{c_4})=5!-r_14!+r_23!-r_32!+r_41!=25$
## Generating Functions 生成函數
- $F(x) = a_0\mu_0+a_1\mu_1+a_2\mu_2+…$ , 是 $(a_0, a_1, a_2, …)$ 的 **ordinary generating function**。
    - $\mu_0,\mu_1,\mu_2...$ are indicator functions，滿足不同的 sequence 對應到不同的生成函數。
        - ex：$1,1+x,1-x,1+x^2,1-x^2,...$cannot be used as indicator functions.
    - 最常見的 indicator functions 是 $\mu_i$ is $x^i$ 
        - $F(x)=a_0+a_1x+a_2x^2+…+a_ix^i+…$
        - $\frac{1}{1-x}$ is the generating function for $1,1,1,...$
        - $\frac{1}{(1-x)^2}$ is the generating function for $1,2,3,...$
    - 馬克勞林級數展開
        - $\begin{pmatrix}n\\r\end{pmatrix}=\frac{(n)(n-1)...(n-r+1)}{r!}$
        - $(1+x)^n=1+\sum\limits_{r=1}^{\infty}\begin{pmatrix}n\\r\end{pmatrix}x^r$
        
- 整數拆分問題
    - $p(10)$ = the coefficient of $x^{10}$ in $\frac{1}{1-x}\times\frac{1}{1-x^2}\times...\times\frac{1}{1-x^{10}}$
    - $p(n)$ = the coefficient of $x^n$ in $\prod\limits_{i=1}^{\infty}\frac{1}{1-x^i}$

- Ferrers graphs：dot representation of partitions
    - There is a one-to-one correspondence between a Ferrers graph and its transposition.

- $F(x)=a_0\mu0+a_1\mu1+a_2\frac{\mu_2}{2!}+a_3\frac{\mu_3}{3!}+…$ 是 **(a0, a1, a2, …)** 的 **exponential generating function**
    - **Combinations $\rightarrow$ Ordinary Generation Functions**
    - **Permutations $\rightarrow$ Exponential Generation Functions**
## Recurrence Relations 遞迴關係
- 線性遞迴關係
    - $c_na_n+c_{n-1}a_{n-1}+…+c_{n-k}a_{n-k}=f(n)$
- 一階齊性($f(n)=0$)
    - $a_n = 7a_{n-1}$
    - $a_{n+1}^2 = 5a_{n}^2$
- 二階齊性
    - $c_na_n+c_{n-1}a_{n-1}+c_{n-2}a_{n-2}=0$
        - **characteristic equation**
            - $r_1\ne r_2$
                - $a_n=c_1r_1^n+c_2r_2^n$
            - $r_1,~r_2$ are complex numbers
                - $r_1=a+bi=\sqrt{(a^2+b^2)}(cos\theta+isin\theta)$
                - $r_2=a-bi=\sqrt{(a^2+b^2)}(cos\theta-isin\theta)$
                - 棣美弗定理 $z^n=r^n(cos(n\theta)\pm i~sin(n\theta))$
                - $a_n=c_1r_1^n+c_2r_2^n=\sqrt{(a^2+b^2)}^n~(k_1cos(n\theta)+k_2sin(n\theta))$
            - $r_1=r_2$
                - $a_n=c_1r^n+c_2nr^n$
- 高階齊性
    - 令$a_n=c~r^n$帶入，看看 characteristic equation 是否有重根
        - 不重：$a_n=c_1r_1^n+c_2r_2^n+c_3r_3^n$
        - 重根：$a_n=c_1r_1^n+c_2nr_2^n+c_3n^2r_3^n$
- 非齊性
    - $a_n = a_n^h+a_n^p$
    - Examples
        - $a_n+2a_{n-1}=n+3$ 則 $a_n^p=cn+d$
        - $a_n-a_{n-1}=n-1$ 則 $a_n^p=cn^2+dn+e$
        - $a_n-3a_{n-1}=5(7^n)$ 則 $a_n^p=k7^n$
        - $a_n-3a_{n-1}=5(3^n)$ 則 $a_n^p=kn3^n$
    - General Cases：如果 $f(n)=c\cdot g(n)$
        - ![](https://i.imgur.com/g3Ekym0.png)
            - 沒撞齊性解 ： $a_n^p=h(g(n))$
            - 如果撞解 ： $a_n^p=h(g(n))\cdot n^s$
- **Method of Generating Functions**
    - $c_na_n+c_{n-1}a_{n-1}+…+c_{n-k}a_{n-k}=f(n)$
    - 1.Multiply both sides by $x^n$
    - 2.Add $\sum\limits_k^\infty$ to both sides 使其和 generating function 扯上關係
    - 3.Solve for $A(x)$
    - 4.$a_n$ = $A(x)$ 中 $x^n$ 的 coefficient
- 一些變形(平常不太會遇到，需要時再查書)：
    - Nonlinear Recurrence Relations
        - Type 1 ： $b_{n+1} = b_0b_n + b_1b_{n-1} + … + b_{n-1}b_1 + b_nb_0$
        - Type 2 ： $b_{n+1} = a_0b_n + a_1b_{n-1} + … + a_{n-1}b_1 + a_nb_0$
    - Two Indices
        - $c(n, r) = c(n-1, r) + c(n-1, r-1)$
    - Simultaneous Recurrence
        - $a_{n+1} = 2a_n + b_n$
        - $b_{n+1} = a_n + b_n$
    - General Factors
        - $a_n = p(n)a_{n-1} + f(n)$
            - 1.Find $a_n^h$
            - 2.Find $b_n$

# 2.Algebra
## Logic
- Statements：具有真假值的陳述句
-  Non-primitive Statements
    - $\neg$ p (not p)
    - p $\land$ q (p and q)
    - p $\lor$ q (p or q)
    - p $\rightarrow$ q (p implies q)
        - p ： hypothesis, sufficient condition
        - q ： conclusion, necessary condition
    - p $\leftrightarrow$ q (p if and only if q)
- Proof Method
    - Truth Table
    - Based on **$p\rightarrow q~~\leftrightarrow ~~\neg q\rightarrow\neg p$**
    - Proof by Contradiction
## Relations
- Tuples
    - $(a_1,a_2,...,a_n)$
- Cartesian Product
    - $A_1\times A_2\times ...\times A_n=\{(a_1,a_2,...,a_n)\}$
        - $A=\{0,1\},B=\{a,b\}$
        - $A\times B=\{(0,a),(0,b),(1,a),(1,b)\}$
    - $A\times\phi=\phi\times A=\phi$
- Relation
    - $A_1\times A_2\times ...\times A_n$ 的任何一個子集合稱為：relation on $A_1,A_2,...,A_n$
        - 共有$2^{|A_1|\times...\times|A_n|}$個
    - $x~R~y~$ iff $x-y是7的倍數~~\leftrightarrow~~R=\{(a,b)|~~a-b=7k~~\}$
- Binary Relations：可以用 Relation matrix 或 Graph 來表示
    - reflexive：$x~R~x$
    - irreflexive：$x$![](https://i.imgur.com/YW4Fh9f.png)$x$
    - symmetric：$x~R~y\leftrightarrow y~R~x$
    - asymmetric：$x~R~y\nleftrightarrow y~R~x$ , $~~~x$![](https://i.imgur.com/YW4Fh9f.png)$x$
    - antisymmetric：$x~R~y\nleftrightarrow y~R~x$ , $~~~x~R~x$可以存在
    - transitive：$x~R~y~$ and $~y~R~z~~~\rightarrow~~~x~R~z$
    - Suppose $A=\{1,2,...,n\}$
        - reflexive：$2^{n^2-n}$
        - symmetric：$2^{(n^2+n)/2}$
        - reflexive and symmetric ：$2^{(n^2-n)/2}$
        - antisymmetric ：$2^n\times3^{(n^2-n)/2}$
- Composition
    - $R_1=\{(1,2),(3,4),(2,4),(4,2)\},~~R_2=\{(2,4),(2,3),(4,1)\}$
    - $R_1\circ R_2=\{(1,4),(1,3),(3,1),(2,1),(4,4),(4,3)\}$
    - $R^0$：Identity Relation
    - $R^+=\cup_{i=1}^{\infty}~R^i$： transitive closure of R
    - $R^*=R^0\cup R^i$： reflexive transitive closure of R
- Equivalence Relation
    - Equivalence Relation 定義為 Relation 同時滿足
        - reflexive
        - symmetric 
        - transitive
    - 一個Equivalence Relation，可以把集合拆成多個Equivalence Class
    - Number of equivalence relations on A = {1,2, ..., 6}
        - 1+31+90+65+15+1=203
        - [貝爾數](https://zh.wikipedia.org/wiki/%E8%B4%9D%E5%B0%94%E6%95%B0)
            - $B_k$表示把k個元素集合拆分的方法數
            - ![](https://i.imgur.com/0LVgI8c.png)
            - $B_{n+1}=\sum\limits_{k=0}^nC(n,k)B_k$，考慮元素k+1和幾個元素一堆
            - $B_n=\sum\limits_{k=0}^nS(n,k)$
        - [Stirling數](https://zh.wikipedia.org/wiki/%E6%96%AF%E7%89%B9%E7%81%B5%E6%95%B0)
            - $S(n,k)$表示把n個相異數字分成k堆方法數
            - $S(n,n-1)=C(n,2)$
            - $S(n,2)=(2^n-2)/2$
            - $S(n,n)=S(n,1)=1$
            - $S(n,k)=S(n-1,k-1)+kS(n-1,k)$
            - ![](https://i.imgur.com/ukmpr96.png)
        - $\frac{1}{1-x}\frac{1}{1-x^2}\frac{1}{1-x^3}\frac{1}{1-x^4}\frac{1}{1-x^5}\frac{1}{1-x^6}的x^6項$
        - onto functions from A = {1,2, ..., 6} to B = {# equivalece class}
- Partial Ordering, Total Ordering
    - Partial Ordering 定義為 Relation 同時滿足
        - reflexive
        - antisymmetric
        - transitive
    - 符號為 $\preccurlyeq$
    - 該relation所定義在的那個集合 A 稱為 POSET
    - Hasse diagram：在 A 是有限集合時可以表示 partial ordering
        - ![](https://i.imgur.com/LP7Ng7R.png)
    - Lattice
        - A中每兩個元素都有upper bound和lower bound。
    - Topological order
        - 可能有多個
        - 把Hasse diagram展成一數列，滿足$a_i\le a_j \rightarrow i\le j$
    - Total ordering on A
        - A裡任兩元素 x,y，必有$x\le y~或~y\le x$
        - Hasse diagram 是一條 chain
    - Atom
        - If $b\le a$ implies b = 0 or b = a, 我們稱a為K的 atom
## Boolean Algebra
- $(K,~\cdot~,+)$
    - 1.封閉性 $\cdot$ and $+$
    - 2.結合律 $\cdot$ and $+$
    - 3.分配律 $\cdot$ and $+$
    - 4.identity 和 zero 存在
    - 5.complement 存在
    - 6.$K$ 裡至少有兩相異元素
- Example
    - ( {true, false} ,$\land,\lor$)
        - true 是 identity，false 是 zero
    - ({1, 2, 3, 5, 6, 10, 15, 30}, lcm, gcd)
        - 30 是 identity，1 是 zero
- Principle of Duality
    - Dual 的意義
        - Replace all occurrences of $\cdot$ by + and + by $\cdot$.
        - Replace all occurrences of 0 by 1 and 1 by 0
    - If S is a therorem of Boolean Algebra, then its dual is likewise a theorem
- Boolean Algebra會滿足的Theorem
    - (1) The identity and zero are unique.
    - (2) $a\cdot a=a=a+a$
    - (3) $a\cdot 0=0，a+1=1$
    - (4) $\overline{a}$ is unique
    - (5) $\overline{\bar{a}}=a$
    - (6) The identity and zero are distinct, also, $\overline{1}=0,~\overline{0}=1$
    - (7) $a\cdot(a+b)=a,~and~a+(a\cdot b)=a$
    - (8) $a\cdot b=a\cdot c,~~\overline{a}\cdot b=\overline{a}\cdot c~~~~~\rightarrow b=c$
          $~~~~~a+b=a+c,~~\overline{a}+ b=\overline{a}+c~~\rightarrow b=c$
    - (9) $(a\cdot b)\cdot c=a\cdot (b\cdot c),~and~(a+b)+c=a+(b+c)$
    - (10) $\overline{a\cdot b}=\overline{a}+\overline{b},~and~\overline{a+b}=\overline{a}\cdot\overline{b}$
## Rings
- **RING**
    - $(R,+,\cdot)$
        - 1.$+$ 是 Abelian group
        - 2.$\cdot$ 是semi group
        - 3.$\cdot對+$ 有分配律
    - 性質
        - Commutative Ring：表示 $『\cdot』$ 也有交換律
        - 如果 $a\ne 0,b\ne 0$ 而且 $a\cdot b = z$，我們稱a, b 為 **zero divisors**
        - 如果存在 $u$ 使得 $a\cdot u=u\cdot a=a$，則稱ring with unity
        - 如果 $a\cdot b=b\cdot a = u$，則
            - a, b 互為彼此的 **multiplicative inverses**
                - a, b 稱為 **units**
        - zero：加法單位元
        - unity：乘法單位元
    - Example
        - $(Z,+,\cdot)$
        - $(Z,\oplus,\odot)$ with $a\oplus b=a+b-1,~~~a\odot b=a+b-ab$
- **Ring 的子集合**
    - **Subring**
        - $(S,+,\cdot)$ 是subring
            - $S$ is subset of $R$
            - $(R,+,\cdot)$ 是ring
        - 定理：$(S,+,\cdot)$是否為subring，只需要檢查
            - 1.封閉性：$a,b\in S~~\rightarrow~~a+b\in S, a\cdot b\in S$
            - 2.反元素：$a\in S~~\rightarrow~~-a\in S$
        - 定理：只需要檢查
            - $a,b\in S~~\rightarrow~~a+(-b)\in S, a\cdot b\in S$
        - 定理：$S$ 是finite的，則只需要檢查
            - $a,b\in S~~\rightarrow~~a+b\in S, a\cdot b\in S$
    - **Integral Domain**
        - $(R,+,\cdot)$ 是ring
            - 1.$R$ 可交換
            - 2.$R$ 有unity
            - 3.$R$ 沒有 zero divisors $\leftrightarrow$ 有乘法消去律
    - **Field**
        - $(R,+,\cdot)$ 是ring
            - 1.$R$ 可交換
            - 2.$R$ 有unity
            - 3.$R$ 中非零元素有 multiplicative inverse
    - **Ideal**
        - $I$ 是 Ideal
            - $I$ 是 $R$ 的 Subring
            - $ar\in I$ 對於 $a\in I, r\in R$
        - Example
            - $2Z$ in $Z$
- **Ring 要滿足的 Theorem**
    - 1.zero 是唯一的
    - 2.additive inverse 的 是唯一的
    - 3.『+』有 左消去律 和 右消去律
        - 『$\cdot$』因為有 0 不一定有消去律
    - 4.任何數乘以 zero 等於 zero
    - 5.$-(-a)=a$
    - 6.$a\cdot(–b)=(–a)\cdot b=–(a\cdot b)$ 
    - 7.$(–a)\cdot(–b)=a\cdot b$
    - 8.如果有unity，則unity是唯一的
    - 9.如果有unity且a是unit，則multiplicative inverse是唯一的
    - **10. no zero divisor $\leftrightarrow$ 乘法消去律**
        - **乘法消去律 $\nrightarrow$ 乘法反元素存在**
    - **11. 如果 $R$ 是 field，則 $R$ 是 integral domain**
    - **12. 如果 $R$ 是 finite integral domain，則 $R$ 是 field**
- **The Integer Modulo n**
    - 定義：a $R$ b $~~\leftrightarrow~~$ a $\equiv$ b (mod n)
    - 定理：R 是 equivilance class
        -  $Z_n$ = $\{$ [0], [1], [2], …, [n-1] $\}$
    - **定理：$Z_n$ 是 field $~~\leftrightarrow~~$ n是質數**
    - **定理：$Z_n$中，[a]有乘法反元素 $~~\leftrightarrow~~$ gcd(a,n)=1**
    - **定理：$Z_n$中，[a]是proper divisor $~~\leftrightarrow~~$ gcd(a,n)>1**
- **The Chinese Remainder Theorem**
    - x $\equiv$ 14 (mod 31)
    - x $\equiv$ 16 (mod 32)
    - x $\equiv$ 18 (mod 33)
    - $M_1=1056, M_2=1023, M_3=992$
    - $x_1=16, ~~~~~x_2=31, ~~~~~x_3=17$
    - $x=14M_1x_1+16M_2x_2+18M_3x_3=1047504=32688$ mod 32736
- **A Cryptosystem Based on the Chinese Remainder Theorem**
    - **該演算法建立在，把很大的 $M$ 分解成 $m_1m_2m_3$ 很困難**
        - 1.假設A要傳遞三個數字 a, b, c
        - 2.B先選好$m_1,m_2,m_3$，告訴A
            - $M=m_1m_2m_3$
            - $M_1x_1,M_2x_2,M_3x_3$
        - 3.A傳遞數字$aM_1x_1~+~bM_2x_2~+~cM_3x_3$ mod $M$
        - 4.B解密得到 a, b, c
- **Ring Homomorphism and Isomorphism**
    - $f:R\rightarrow S$ 是 isomorphism
        - 1.$f$ is bijective
        - 2.$f$ 是 homomorphism
            - $f(a+b)=f(a)\oplus f(b)$
            - $f(a\times b)=f(a)\otimes f(b)$
    - **定理：若$f:R\rightarrow S$ 是homomorphism**
        - 1.$f(z_R)=z_S$
        - 2.$f(-a)=-f(a)$
        - 3.$f(na)=nf(a),n\in Z$
        - 4.$f(a^n)=f(a)^n,n\in Z$
        - 5.$A$ is subring $\rightarrow$ $f(A)$ is subring
    - **定理：若$f:R\rightarrow S$ 是homomorphism 且 onto**
        - 1.若 $u_R$ 是unity $\rightarrow$ $f(u_R)$ 是unity
        - 2.若 $a,a^{-1}$ 互相為inverse $\rightarrow$ $f(a),f(a^{-1})$ 互相為inverse
        - 3.若 $R$ 可交換 $\rightarrow$ $S$ 可交換
        - 4.若 $I$ 是 $R$ 的 Ideal $\rightarrow$ $f(I)$ 是 $S$ 的 Ideal
## Group
- **Group**
    - $(G,~\cdot~)$
        - 1.封閉律
        - 2.結合律
        - 3.單位元存在
        - 4.反元素存在
    - **Abelian group** 表示 $G$ 滿足交換律
        - Permutations、矩陣乘法：不可以交換
    - **SubGroup**
        - 定理：$(G,\cdot)$ 是 subgroup，只需檢查
            - 1.封閉性
            - 2.反元素存在
        - 定理：$(G,\cdot)$ 是 finite subgroup，只需檢查
            - 封閉性
    - **Group 要滿足的 Theorem**
        - 1.identity 是唯一的
        - 2.inverse 是唯一的
        - 3.有左消去律
        - 4.有右消去律
        - 5.Abelian $\leftrightarrow~~(ab)^2=a^2\cdot b^2$ 
- **Group Homomorphism and Isomorphism**
    - $f:G\rightarrow H$ 是 **isomorphism**
        - 1.$f$ is **bijective**
        - 2.$f$ 是 **homomorphism**
            - $f(a。b)=f(a)*f(b)$
    - **定理：若$f:R\rightarrow S$ 是homomorphism**
        - 1.$f(e_G) = e_H;$
        - 2.$f(a^{-1}) = [f(a)]^{-1}~for~any~a\in G;$
        - 3.$f(a^n) = [f(a)]^n~for~any~a\in G~and~n\in Z;$
        - 4.$f(S)~is~a~subgroup~of~H~for~any~subgroup~S~of~G.$
- **Cyclic Group 循環群**
    - G is cyclic
        - G = **\<a\>**
        - a 是 generator
    - **Cyclic group $\rightarrow$ Abelian group**
    - **\<a\>** 必定是 subgroup
    - **o(a) = |\<a\>|**
        - $m$ 是滿足 $a^m = e$ 的最小正整數
        - $<a> = \{e,a^1,a^2,…,a^{m-1}\};$
        - **o(a) = m**
    - 定理：$G$ 是 size $\infty$ 的 Cyclic group, 則 $G$ 同構於 $(Z, +)$ 
    - 定理：$G$ 是 size $n$ 的 Cyclic group, 則 $G$ 同構於 $(Z_n, +)$
    - 定理：Cyclic group 的子群必定 cyclic

- **Cosets**
    - **H 是 subgroup**
        - $a\cdot H=\{a\cdot h|h\in H\}$ 是 left coset of H in G
        - $H\cdot a=\{h\cdot a|h\in H\}$ 是 right coset of H in G
- **Lagrange’s Theorem**
    - **對任意 subgroup H, elememt a, b**
        - 1.$|aH| = |H|;$
        - 2.$|Ha| = |H|;$
        - 3.$aH = bH~~$ or $~~aH\cap bH = \phi;$
        - 4.$Ha = Hb~~$ or $~~Ha\cap Hb = \phi$
        - 5.**Left cosets of H 形成 G 的 partition**
        - 6.**Right cosets of H 形成 G 的 partition**
    - **定理：If H is a subgroup of a finite group G, then |H| divides |G|.**
    - 定理：If $|G|$ is prime, then $G$ is cyclic.
- **RSA Cryptosystem**
    - **該演算法建立在，把很大的 $n$ 分解成 $pq$ 很困難**
        - 1.假設 A 要傳送數字 $L$
        - 2.B 產生 Key
            - 1.選定大質數 p, q，算 $n=p\times q$
            - 2.$\phi(n)=(p-1)(q-1)$
            - 3.選定 $e$ 和 $\phi(n)$ 互質
            - 4.計算 $d$ 使 $d\times e=1$ mod $\phi(n)$
            - 5.『公鑰：$(n,e)$，私鑰：d』
        - 3.B 告訴 A 公鑰 = $(n,e)$
        - 4.A 用公鑰傳送密文，$C=L^e$ mod n
        - 5.B 用私鑰得到明文，$L=C^d$ mod n
# 3.Graph
## Preliminaries
- Graphs $G = (V, E)$ 的一些定義：
    - Digraph：邊有方向性的圖
    - Multigraph：允許兩點間有多邊
    - Simple Graph：沒有自己指向自己(loop)
    - Complete Graph：任兩點有邊
    - Bipartite Graph：頂點可分兩 disjoint set
    - Degree：鄰居數量
        - $\sum d^{in}=\sum d^{out}=|E|$
    - Subgraph：子圖
    - Induced Subgraph by S：由 S 中點形成的子圖
    - Spanning Subgraph：包含原圖所有頂點的子圖
    - Regular graph：每個點 degree 相同
    - Isomorphism：存在點和邊的對應，可以 relabel 成同一張圖
    - Walk：沒有限制的路徑
    - Path：頂點不重複的路徑
    - Trail：邊不重複的路徑
    - Cycle：頂點不重複的環
    - Circuit：邊不重複的環
    - Connected Graphs：只有一個 Connected Components 的圖
    - Underlying Graph：去掉方向形成的圖
    - 定理：Connected Graphs中，必定有 degree 1 的點或是 cycle
    - 性質：n 個點的 Connected Graphs 至少有 n-1 個邊
    - 性質：n 個點的 Tree 恰好有 n-1 個邊
    - 定理：n 個點的 strongly connected digraph 至少有 n 個邊
## Spanning Trees
- Search
    - Breadth First Search (BFS)
        - ![](https://i.imgur.com/w5RmuZF.png)
        - {1} → {2,3,4} → {5,6,7} → {8,9}
    - Depth First Search (DFS)
        - 1 → 4 → 7 → 9 → 8 → 6 → 3 → 5 → 2
- Spanning Trees
    - 定義： Subgraph 本身是 Tree
    - Number of Spanning Trees
        - $S(G)=S(G-e)+S(G\cdot e)$
    - Minimum Spanning Tree 
        - Kruskal’s algorithm
            - sort 所有的邊再從小選到大
        - Prim’s algorithm
            - 每次把 weight 最小鄰居加入集合(小樹長大樹)
        - Sollin(Boruvka)’s algorithm
            - 維持一個 forest，每次找每顆樹 weight 最小鄰居，合併對應的兩棵樹
- Cycle Basis
    - 定義：$A\oplus B=A\cup B-A\cap B$
    - Independent Cycles：Cycles的集合，沒有cycle是其他兩cycle的XOR
    - Cycle Basis：Cycles的集合，每一個cycle都可以由此集合XOR組合而成
    - 尋找 G 的 Cycle Basis 的方法：
        - 1.先找到 G 的 spanning tree T
        - 2.加入不在 T 中的邊，每一個加入的邊 $a_i$ 可以對應的 Cycle Basis 裡的一個 cycle $c_i$，C = { $c_1,...,c_n$ } 即為 Cycle Basis
    - 定理：Cycles 之間做 XOR，會形成一個cycle或多個disjoint cycles
    - 定理：以上演算法找到的 C = { $c_1,...,c_n$ } 即為 Cycle Basis
        - 1.C 是 Independent Cycles
        - 2.任意一個Cycle，可以由 C 裡的 cycles 組出。
## Connectivity
- 定義：
    - k-vertex cut：k個點的集合，拔掉後圖變 disconnect
        - vertex connectivity：至少要拔掉多少點
    - k-edge cut：k個邊的集合，拔掉後圖變 disconnect
        - edge connectivity：至少要拔掉多少邊
- **演算法**
    - 對 G 跑一次 DFS，會得到 DFS Spanning Tree T
        - $DFN(i)$ ： DFS 拜訪順序
        - $L(i)$ ： 至多一個 back edge 所可以到達的最小 DFN
    - **尋找圖的 Articulation Points**
        - 定理： G 的每個 edge 在 T 上都是祖孫關係
        - 定理： Articulation Point 的充要條件
            - 1.$i$ 是 root，有兩個 child
            - 2.$i$ 不是 root，有一個 child $j$ 滿足 $L(j)\ge DFN(i)$
    - **尋找圖的 Bridges**
        - 定理：$(i,j)$ 是 Bridge 的充要條件
            - $i$ 有一個 child $j$ 滿足 $L(j)=DFN(j)$
## Paths
- Euler Trails, Euler Circuits
    - Euler Trail：恰好走過 G 的每個邊一次的 Trail
    - Euler Circuit：恰好走過 G 的每個邊一次的 Circuit
    - 定理：
        - 1.無向圖 G 有 Euler Trail $\leftrightarrow$ G 有兩個奇點
        - 2.無向圖 G 有 Euler Circuit $\leftrightarrow$ G 沒有奇點
        - 3.有向圖 G 有 u → v 的 Euler Trail $\leftrightarrow$ 
            - 1.u=v
                - 所有點的 indegree = outdegree
            - 2.u≠v 
                - u點的 indegree+1 = outdegree
                - v點的 indegree = outdegree+1
                - 其他點的 indegree = outdegree
- Hamiltonian Paths, Hamiltonian Cycles
    - Hamiltonian Path：恰好走過 G 的每個點一次的 Path
    - Hamiltonian Circuit：恰好走過 G 的每個點一次的 Circuit
    - 定理：
        - 1.若 $G=(V,E)$ 中的任兩點 $u,v$ 都有 arc，則 $G$ 有 Directed Hamiltonian Path。
        - 2.若 $G=(V,E)$ 中，$d_i+d_j\ge n-1$ 對所有 $(i,j)\notin E$，則 $G$ 有 Hamiltonian Path。
        - 3.若 $G=(V,E)$ 中，$d_i+d_j\ge n$ 對所有 $(i,j)\notin E$，則 $G$ 有 Hamiltonian Cycle。\
- Shortest Paths
    - Bellman-Ford Algorithm：$O(mn)$
    - Dijkstra Algorithm：$O(m+nlogn)$
- Transitive Closure
    - 每一個 $G=(V,E)$ 可以用一個矩陣 $A$ 來表示。
        - $A^1$ 表示一步可以到的 pair。
        - $A^2$ 表示兩步可以到的 pair。
        - $A^+$ 表示可以走的到的 pair。
    - Transitive Closure of A：
        - $A^+=\sum\limits_{i=1}^\infty A^i$
        - 其實只要加到第 $|V|-1$ 項就好。
    - Reflexive Transitive Closure of A：
        - $A^*=\sum\limits_{i=0}^\infty A^i$

## Miscellaneous Topics
- Planar Graphs
    - 可以畫成沒有任何兩個邊交叉
    - 定理：任意一個 connected planar graph
        - $|V|-|E|+r=2$
        - $|E|\le 3|V|-6$ 當 $|E|\ge2$
    - Corollary
        - 每一個 planar graph 的不同畫法，都有相同的 region 數。
        - 若 planar graph 有 k 個 connected component，則 $|V|-|E|+r=k+1$
        - $K_5,K_{3,3}$ 都不是 planar graph
    - 定理：
        - G 是 planar graph $\iff$ $G$ 沒有任何子圖 contractible to $K_5$ 或 $K_{3,3}$
        - G 是 planar graph $\iff$ $G$ 沒有任何子圖 homeomorphic to $K_5$ 或 $K_{3,3}$
- **Matching**
    - $M\subseteq E$ 沒有連到相同的點上。
        - Maximum Matching：邊數最多的 matching。
        - Perfect Matching：邊數恰好為點數的一半。
        - 二分圖 $G=(R\cup S,E)$ 滿足 $|R|\le |S|$
            - Complete Matching：恰好包含某一(小)側所有的點。
            - $ADJ(W)=\{\text{v|v is adjacent to a vertex in W}\}$
    - 定理：$G$ 有 complete matching $\iff$ $|W|\le|ADJ(W)|$ 對所有 $W\subseteq R$。
        - $\rightarrow$：Trivially
        - $\leftarrow$：Induction
            - 全部子集 $|W|<|ADJ(W)|$
            - 只有 $R$ 相等
            - 有一些子集相等
- NP hard 問題等價
    - $V_2$ 是 $G$ 的 **Clique**
    - $V_2$ 是 $\bar G$ 的 **Independent Set**
    - $V-V_2$ 是 $\bar G$ 的 **Vertex Cover**
- **Maximum Flow and Minimum Cut**
    - 給定有向圖，source node $a$ and sink node $z$，則 flow 是一個把每個 edge 分配一個自然數的 function。
        - Capacity Constraint：$0\le f(e)\le c(e)$
        - Conservation Constraint：$\psi^+(v)=\psi^-(v)$
        - $F=\psi^-(a)=\psi^+(z)$
    - 符號
        - $\bar S=V-S$
        - $a\in S,~z\in\bar S$
        - $E(S:\bar S)$ be the set of arcs from $S$ to $\bar S$
        - **Cut** ： $E(S:\bar S)\cup E(\bar S:S)$
        - $c(S)=\sum\limits_{e\in E(S:\bar S)} c(e)$ 是 capacity of cut
        - $f(S:\bar S)=\sum\limits_{e\in E(S:\bar S)}f(e)$
    - 定理：
        - $F=f(S:\bar S)-f(\bar S:S)$ for $a\in S$
        - 如果 $F=c(S)$，則 $F$ 是 maximum 且 $c(S)$ 是 minimum
        - $F=c(S)\iff$
            - (a).$f(e)=c(e)$ 對所有 $e\in E(S:\bar S)$
            - (b).$f(e)=0$ 對所有 $e\in E(\bar S:S)$
        - $F$ 是 maximum $\iff$ 圖上沒有從 $a$ 到 $z$ 的 augmenting path。
    - [演算法：](http://pisces.ck.tp.edu.tw/~peng/index.php?action=showfile&file=f6cdf7ef750d7dc79c7d599b942acbaaee86a2e3e)
        - Ford & Fulkerson’s algorithm：
            - 每次找 augmenting path，更新 flow
            - 時間：$O(|E|f)$
        - Edmonds & Karp’s algorithm：
            - 每次用 BFS 找 augmenting path，更新 flow
            - 時間：$O(|E|^2|V|)$
        - Dinic：$O(|V|^2|E|)$
        - Karzanov：$O(|V|^3)$
        - Malhotra, Pramodh Kumar, Maheshwari：$O(|V|^3)$
        - Cherkassky：$O(|V|^2|E|^{0.5})$
- Coloring Problem
    - Proper Coloring：把每點塗色，使相鄰兩點異色
    - Chromatic Number $\chi(G)$：最少需要幾種顏色
    - 定理：$G$ 是 2-colorable (**Bipartite**) $\iff$ $G$ 沒有奇數長度的 cycle。
    - Chromatic Polynomial $P(G,\lambda)$：最多用 $\lambda$ 種顏色下，有幾種不同的圖法。
        - $P(K_n,\lambda)$
            - 如果 $\lambda<n$，0
            - 如果 $\lambda\ge n$，$\lambda(\lambda-1)...(\lambda-n+1)$
        - $P(P_n,\lambda)$
            - $\lambda(\lambda-1)^{n-1}$


