# 離散數學

# 1.Counting
## Principle of Inclusion and Exclusion排容原理
- The Principle
- $N(\bar{c_1}\bar{c_2}\bar{c_3})=N$
     $-(~N(c_1)+N(c_2)+N(c_3)~)$
     $+(~N(c_1c_2)+N(c_1c_3)+N(c_2c_3)~)$
     $-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)$
-  $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)$
- 
- 沒撞齊性解 ： $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$$x$
- symmetric：$x~R~y\leftrightarrow y~R~x$
- asymmetric：$x~R~y\nleftrightarrow y~R~x$ , $~~~x$$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個元素集合拆分的方法數
- 
- $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)$
- 
- $\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
- 
- 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)
- 
- {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}$