112考資工研究所時寫的筆記，有錯歡迎留言指正
內文有引用他人筆記/教材/文章的地方
若有侵權十分抱歉，告知後將立刻撤除

[TOC]

# CH1 基本數學

## 1-1 集合論
需記得:
- A⊕B
- 基數Cardinality
- 冪集合power set $\mathcal{P}(A)$
- 卡氏積 $A \times B$
- A={a1,a2}
- B={b1,b2,b3}
- $A \times B = \{(a1,b1), (a1,b2), (a1,b3), (a2,b1), (a2,b2), (a2,b3)\}$

## 1-2 數學歸納法
None
之後如果有時間複習刷題，可以跳過1-1, 1-2，太浪費時間，重點都在1-3

## 1-3 基礎數論
- 輾轉相除法求$as+bt=\gcd(a,b)$
- 
- [ref](https://math.fandom.com/zh/wiki/%E4%BA%8C%E5%85%83%E4%B8%80%E6%AC%A1%E4%B8%8D%E5%AE%9A%E6%96%B9%E7%A8%8B?variant=zh-tw)
- 輾轉相除法求模反元素
- 費馬小定理
- p為質數, gcd(m,p)=1
- $m^{p-1}\equiv 1(\mod p)$
- 尤拉定理
- gcd(m,n)=1
- $m^{\phi(n)}\equiv 1(\mod n)$
- 已知n與n的質因數分解，求$\phi(n)$
- Let $n_1, n_2, ..., n_k$為n的質因數分解之質數
- $\displaystyle \phi(n) = n \times (1-\frac{1}{n_1}) \times (1-\frac{1}{n_2}) ... \times (1-\frac{1}{n_k})$
- 中國餘數定理
- Given the following, find x.
- $x = r_1(\mod\ n_1)$
- $x = r_2(\mod\ n_2)$
- $x = r_3(\mod\ n_3)$
- 求出$N_i, M_i$再求x
- $N = n_1 \times n_2 \times n_3$
- $N_1 = N / n_1$
- $N_2 = N / n_2$
- $N_3 = N / n_3$
- $M_1 = (N_1)^{-1} \mod n_1$
- $M_2 = (N_2)^{-1} \mod n_2$
- $M_3 = (N_3)^{-1} \mod n_3$
- $x = (r_1N_1M_1+r_2N_2M_2+r_3N_3M_3) \mod N$
- RSA
- pq=N
- $\phi(N) = (p-1)(q-1)$
- $gcd(e,\phi(N))=1$, (e,N)為私鑰
- $d=e^{-1}(\mod \phi(N))$, (d,N)為公鑰

## ch1總結
- 1-1用感覺寫
- 總體來說滿簡單的
- 中國餘數定理題型稍稍會有變化，需要練，解法需要背
- RSA很少考，但還是要會
- 輾轉相除法要熟
# CH2 關係與函數
## 2-1 關係
1. 反關係$R^{-1}$
2. 補關係$\overline{R}$
3. $R^0=\{(a,a),\forall a \in A\}$(關係矩陣即單位矩陣)

- 其他:
- 比較---
- 關係: $R\circ S = SR$
- 函數: $f\circ g = fg$
- Ch2習題1
## 2-2 基本關係
1. reflexive
- $\forall a \in A, (a,a) \in R$
- 矩陣: 對角線皆為1
- 數量: $2^{n^2 - n}$
2. irreflexive
- $\forall a \in A, (a,a) \notin R$
- 矩陣: 對角線皆不為1
- 數量: $2^{n^2 - n}$
3. symmetric
- $\forall a,b \in A, (a,b) \in R \implies (b,a) \in R$
- 矩陣: $R=R^T$
- $2^{\frac{1}{2} (n^2 + n)}$
4. asymmetric
- $\forall a,b \in A, (a,b) \in R \implies (b,a) \notin R$
- 所有1的元素$a_{ij}$的對稱位置$a_{ji}$必為0
- 數量: $3^{n \choose 2}$
5. antisymmetric
- $\forall a,b \in A, (a,b) \in R 且 (b,a) \in R \implies a=b$
- 除了對角線元素外，所有1的元素$a_{ij}$的對稱位置$a_{ji}$必為0
- 數量: $2^n 3^{n \choose 2}$
6. transitive
- $\forall a,b \in A, (a,b) \in R 且 (b,c) \in R \implies (a,c) \in R$
- $R=R^2$
- 其他:
- 關係的定義要背!也需從矩陣想!
- 台大近年超愛考這邊，一題10分錯了會想死

## 2-3 等價關係
- Equivalence
- reflexive
- symmetric
- transitive
- ex: 同餘congruence
- 分割partition
- 定理2-8: 集合的相異partition數量(例34)
- i個元素上的相異等價關係個數 = i個相異物的partition個數$=P_i$
- $P_0=1$
- $\displaystyle P_1={0 \choose 0}P_0=1$
- $\displaystyle P_2={1 \choose 0}P_0+{1 \choose 1}P_0=2$
- $\displaystyle P_3={2 \choose 0}P_0+{2 \choose 1}P_1+{2 \choose 2}P_2=5$
- $\displaystyle P_4={3 \choose 0}P_0+{3 \choose 1}P_1+{3 \choose 2}P_2+{3 \choose 3}P_3=15$
- 以此類推
- 也可用[second stirling](#3-4-排容原理)求解(p3-56)
- ex. $P_4 = S(4,1)+S(4,2)+S(4,3)+S(4,4)$ = 1+7+6+1=15
## 2-4 關係的包
- reflexive closure
- $r(R) = R \cup R^0$
- symmetric closure
- $s(R) = R \cup R^{-1}$
- transitive closure
- 畫圖在找關係矩陣
- 若$|A|=n$，關係矩陣$t(R)=M_R \wedge M^2_R \wedge M^3_R...\wedge M^n_R$
- $\pi_1 \cdot \pi_2\ and \ \pi_1 + \pi_2$
- 例41
- If $A=\{a,b,c,d,e,f,g,h,i,j,k\}$
- and if $\pi_1 = \{\{a,b,c,d\},\{e,f,g\},\{h,i\},\{j,k\}\}$
- and if $\pi_2 = \{\{a,b,c,h\},\{d,i\}, \{e,f,j,k\},\{g\}\}$
- $\pi_1 \cdot \pi_2 = \{\{a,b,c\}, \{d\}, \{e,f\}, \{g\},\{h\}, \{i\},\{j,k\}\}$
- $\pi_1 + \pi_2 = \{\{a,b,c,d,h,i\}, \{e,f,g,j,k\}\}$
- 應該看上面例子就能懂了
- 最細分割: 考古2-64.65

## 2-5 函數
- function函數定義
- domain定義域
- codomain對應域
- range值域
- one-to-one = injective
- $f(x_1)=f(x_2) \implies x_1 = x_2$
- onto = surjective
- $A \rightarrow B$ is a function
- $\forall b \in B, \exists a \in A\ s.t\ f(a)=b$
- one-to-one && onto = invertible = bijection
- $(f\circ g) (a)= f(g(a))$
- $f^{-1}$: 反函數

## 2-6 鴿籠原理
刷題就對了，經典題就那些

## 2-7 計數問題
- A~B(相同基數): one-to-one && onto
- 有限集、無限集
- 可數集、不可數集
- 其他:
- 練題目才會懂
## ch2總結
- 這邊真的要練題目，另外證明需要背很多基本定義，ex.
- equivalent(3項)
- 1-to-1
- onto
- antisymmetric
- asymmetric
- 偶爾會出現題目難以理解的狀況，視情況要skip

# CH3 排列組合與排容原理

## 3-1 基本計數問題
- easy, 憑感覺寫

## 3-2 排列
- A,B 為兩集合，|A|=m, |B|=n，問以下函數個數
- A到B的一對一函數: $P_m^n$
- A到B的函數: $n^m$
- A到B的映成函數: $onto(m,n)$
- 也幾乎憑感覺寫

## 3-3 組合
- 注意題型
- $(x_1+x_2+...+x_n)^k$展開後問某項的係數(p3-27)
- **相同物**r放**相異箱**n: $H_r^n$
- $1 \leq x_1 \leq x_2 \leq ... \leq x_r \leq n$ 的可能性$= H_r^n$
- $C_n^0+C_n^1+C_n^2+...+C_n^n = 2^n$
- 很多combinatorial argument，需多練
- 這邊題型變化不大，要記的公式定理也很少，練題目就行

## 3-4 排容原理
- $onto(m,n)=\displaystyle\sum_{i=0}^{n} (-1)^n {n \choose i}(n-i)^m$
- m**相異物**放入n**相異箱**不允許空相的方法數
- Stirling numbers of the second kind:
- $S(m,n)=\displaystyle\frac{onto(m,n)}{n!}$，m**相異物**到n**相同箱**不允許空相
- first kind: ex. $\dbinom{4}{2} = x(x+1)(x+2)(x+3)(x+4)取x^2的係數$
- $S(m+1,n)=S(m,n-1)+nS(m,n)$
- 跟組合相加的很像，只是最後有多乘一個n
- 類似問題: [分堆(partition)問題](#2-3-等價關係)
- 看到連續條件合成求數量，八成是排容
- 一定要練題目

## 3-5 亂序及禁位問題
- n個相異物亂序
- $\displaystyle D_n = n![1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+...(-1)^n \frac{1}{n!}] \approx \frac{n!}{e}$
- 城堡多項式r(C,x)
- 須自己寫一次題目:課本p3-72 兩例題
- 很多題目會讓你誤會以為用亂序Dn，其實他能用的場景很受限，必須皆為相異物
- 看習題3-177, 3-132

- 練題目!練爆!
- 寫題目時學到可以記起來的東西:
- poker hand = 5張牌
- 1~100的質數(不含1) 有25個
- 1不是質數也不是合數

## 3-6 離散機率
- 獨立事件(可能會證明)
- $P(E \cap F) = P(E)P(F)$
- 挺簡單，小練題目就能上手
## ch3總結
- 題目練爆就對了，有些真的不是人寫得出來的東西需跳過
- 常需注意要不要除n!
- 上面的東西，但因為太常搞混(ex. 習題3-128)寫在這邊
- $H_r^n$，m**相同物**放n**相異箱**允許空相
- $S(m,n)=\displaystyle\frac{onto(m,n)}{n!}$，m**相異物**到n**相同箱**不允許空相
- $onto(m,n)=\displaystyle\sum_{i=0}^{n} (-1)^n {n \choose i}(n-i)^m$， m**相異物**放入n**相異箱**不允許空相

# CH4 生成函數
## 4-1 一般生成函數
- 需要記的公式(應該算公式)
- $\displaystyle {-n \choose r} = (-1)^r {n+r-1 \choose r}$
- $\displaystyle (1+x)^n = {n \choose 0} + {n \choose 1}x + {n \choose 2}x^2 + ... + {n \choose n}x^n = \sum_{i=0}^{n} {n \choose i} x^i$
- $\displaystyle (1-x)^{-n} = \frac{1}{(1-x)^n} = \sum_{i=0}^{\infty} {n+i-1 \choose i} x^i$
- $\displaystyle \frac{1}{1-x} = 1 + x + x^2 + x^3 + ... = \sum_{i=0}^{\infty}x^i$
- $\displaystyle \frac{1-x^{n+1}}{1-x} = 1 + x + x^2 + ...+ x^n = \sum_{i=0}^{n}x^i$
- 要處裡沒看過的數列$a_n$，都要從$\sum$做微分積分等等的運算，比較不會出錯
- 習題4-1, 4-6
- 很愛考一個式子的$x^n$係數，練熟就會寫
- 4-11, 4-13
- 卷積(convolution)概念出現在這邊，不難
- 4-18，課本精選範例9(p4-22)
- $x_1+x_2+...x_n = C$的變化題: 限定$x_i$的上限，求可能解的數量
- 4-27, 4-35, 4-39(這題超難，出現過不只一次，背假設方法)
- 很多題目從他變化/延伸

## 4-2 整數的分割
- 算是一般生成函數的其中一種題型
- 不難，練過就會
- 4-49, 4-50
- Ferrer's graph能拿來解部分整數分割題目 (ex.證明兩種分割方式數量一樣)
## 4-3 指數生成函數
- 跟一般生成函數的使用差別
- 老師在p4-34有寫，一般生成函數用來解組合的題目，指數生成函數解排列的題目
- 要背的公式
- $\displaystyle a_0+a_1x+a_2 \frac{x^2}{2!}+ a_3 \frac{x^3}{3!} + ...= \sum_{i=0}^{\infty} a_i \frac{x^i}{i!}$
- $\displaystyle e^x = 1 + \frac{x}{1} + \frac{x^2}{2!} + \frac{x^3}{3!}+ ... = \sum_{i=0}^{\infty} \frac{x^i}{i!}$
- $\displaystyle \frac{e^x + e^{-x}}{2} = 1 + \frac{x^2}{2!} + \frac{x^4}{4!}+ ... = \sum_{i\in even}^{\infty} \frac{x^i}{i!}$
- $\displaystyle \frac{e^x - e^{-x}}{2} = \frac{x}{1} + \frac{x^3}{3!} + \frac{x^5}{5!}+ ... = \sum_{i\in odd}^{\infty} \frac{x^i}{i!}$
- 課本例30，經典中的經典，考到爛掉
- 習題4-54, 4-55, 4-60, 4-61能考的大概就這樣了
- 指數生成函數一開始寫起來的感覺比一般生成函數難，但寫多會發現題型變化小，務必要練習
## 4-4 求和算子
- 生成函數的變化題型
- 如果要求某個數列的總合的生成函數(該數列$a_n$的級數$S_n$)
- $\displaystyle S(x) = \frac{1}{1-x} A(x)$ 即為所求
- 習題4-67

# CH5 遞迴關係
## 5-1 遞迴關係式
- 數學歸納法在這張也是好朋友
- 習題5-21, 5-24, 5-25
- 少數要求一般式的題目，暴力累加或爆開就能找到: 習題5-1, 5-4, 5-5
- 很喜觀拿Fibonacci 數列考變化題: 習題5-20, 5-22, 5-23
- Fibonacci 數列
- 遞迴式
- $F_n = F_{n-1} + F_{n-2}, n \geq 2$
- $F_0 = 0,\ F_1 = 1$
- 一般式 (背! 也可用線性法, 生成函數推導)
- $\displaystyle F_n = \frac{1}{\sqrt{5}} \left[ \Bigl(\frac{1+\sqrt{5}}{2}\Bigl)^{n} - \Bigl(\frac{1-\sqrt{5}}{2}\Bigl)^{n}\right]$
- 合內塔 Tower of Hanoi
- 遞迴式
- $\displaystyle a_n = 2a_{n-1}+1, n \geq 2$
- $a_1 = 1$
- 一般式
- $a_n = 2^n -1, n \geq 1$ (把遞迴式暴力帶入即可得到)

## 5-2 常係數線性遞迴關係式
- 齊次 vs 非齊次 (Homogeneous vs Non-homogeneous)
- k階常係數遞迴關係式$C_n a_n + C_{n-1} a_{n-1} + ... + C_{n-k} a_{n-k} = f(n)$
- If $f(n)=0 \implies$ 齊次 (Homogeneous)
- 習題5-33, 5-36
- If $f(n)\not= 0 \implies$ 非齊次 (Non-homogeneous)
- 習題5-41, 5-42
- 假設通解$a_n^{(h)}$或特解$a_n^{(p)}$時，大原則是:
- 不可出現同型的假設，如果有要多乘上變數n
- ex. 令通解$a_n^{(h)}=A \cdot 2^n$，如果特解$a_n^{(p)}$也需要令$B \cdot 2^n$，改令為$B \cdot n2^n$
- ex. 令通解$a_n^{(h)}=A \cdot 2^n$，如果$f(n)=n2^n$，特解$a_n^{(p)}$令$B n^2 2^n + C n 2^n$
- 出現高次的，要依序補滿低次的
- ex. 令$f(n) = n^2$，特解需令$a_n^{(p)} = An^2+Bn+C$
- ex. 令$f(n) = n2^n$，特解需令$a_n^{(p)} = An2^n+B2^n$
- 求出一般式後，一定要記得寫下一般式的適用範圍，即最後的$n \geq 0\ or\ n \geq 2$
- 如果題目沒給initial condition，答案須帶著假設$a_n$時的常數(ex. $a_n = A2^n+n2^n$)
- ==特別注意1: 出現共軛複根( 跑出虛數$i$ )==
- 難以言傳，自己看解法，課本p5-27
- 習題5-38, 課本例19, 20
- ==特別注意2: 非齊次解法(存在特解$a_n^{(p)}$)==
- 解題程序小小複雜，須自己算幾次才會懂

## 5-3 轉換法求解遞迴關係式
- 非線性遞迴式，通常要把$a_n$令成別的東西，把式子轉換成線性，才可求解
- 習題5-58, 5-63, 5-64算是必較常見的
- 若$f(n)= 5f(n/3)+n \implies$
- 令$n=3^k \implies f(3^k)=5f(3^{k-1})+3^k$
- 令$a_k = f(n^k), a_k = 5 a_{k-1}+3^k$
- 線性法求解$a_k$，依序帶n回有k的地方得f(n)
- 有些需要創意+經驗才能解開
- 可能需要同除n!、移項、令$n=2^k$, 令$n=2^{2^k}$, 令成二進制字串, 令成$b_k = \sqrt{a_n}$
- 習題5-67, 5-73, 5-74, 5-77, 5-78
## 5-4 生成函數法求解遞迴關係式
- 很容易忘!練習!!!
- 有很多細節要小心，前面轉換成generating function容易犯錯
- 習題5-80, 5-81, 5-82
## 5-5 應用問題
- 太難了QQ
- Josephus problem
## 5-6 特殊類型遞迴關係式
- Catalan number
- $\displaystyle C_n = \frac{1} {n+1} {2n \choose n}$
- 應用:
- n個node的相異有序二元樹
- 一個sequence被push進stack又pop出來有幾種排列可能
- 2n個括號(n個左刮+n個括號)的式子
- 從(x, y)移動到(x+n, y+n)只允許沿著格子走且不可落在y=x線上
- 習題5-59, 課本例45, 48, 精選範例3
- [Bertrand's ballot theorem](https://en.wikipedia.org/wiki/Bertrand%27s_ballot_theorem)
- 選舉中，A得p票，B得q票，p>q
- 允許開票時某個時間點一樣多，但B不超過A
- 數量: $\displaystyle {p+q \choose q} - {p+q \choose q-1}$
- 機率(由上推導): $\displaystyle \frac{{p+q \choose q} - {p+q \choose q-1}}{p+q \choose q} = \displaystyle \frac{p+1-q}{p+1}$
- 本題參考課本p5-99精選範例3 (原理p5-92)
- 將題目轉化到x-y平面上，從原點(0,0)走到(p,q)不能超過 $y=x$ 那條線
- 開票全程A的票數都比B多
- 數量: $\displaystyle {p-1+q \choose q} - {p-1+q \choose q-1}$
- 機率(由上推導): $\displaystyle \frac{{p-1+q \choose q} - {p-1+q \choose q-1}}{p+q \choose q} =\displaystyle \frac{p-q}{p+q}$
- 本題參考上題平面解法，但把$y=x$ 換成 $y=x-1$
# CH6 圖論
## 6-1 圖的種類及術語
- trail
- 不含重複邊的walk
- path
- 不含重複點的walk
- circuit
- close trail, 起終點相同的trail
- cycle
- close path, 起終點相同的path
- $\mathcal K(G)$
- G的component數量
- 切點 Cut point / articulation point
- G去掉一個點v形成$G_1=(V-\{v\},E_1)使G_1$不為聯通圖，v稱為切點
- 切邊/橋 Cut edge / bridge
- 拿掉e後會使圖變成非連通圖，e稱為切邊/橋
- 雙連通圖形 Biconnected Graph
- 在圖形 G 中，不包含任何切點(Cut point)。
- 完全圖 Complete graph
- 無向圖，圖中任兩點有邊相連，記做$K_n$
- 有向完全圖: $\forall x,y \in V, (x,y), (y,x)$洽有一邊在圖中，記做$K_n^*$
- 完全雙分圖 complete bipartite graph
- bipartite的兩個vertex set中的每個點，都跟另一個點集有邊相連，記做$K_{m,n}$
- 補圖 complement graph
- 簡單無向圖，原圖G的點集相同，把原有的邊拿掉，兩個點中沒有邊的加上邊
- 記做$\overline{G}或G^c$
- 懸吊點 pendant
- degree = 1的vertex
- 規則圖 n-regular graph
- $deg(v) = n,\ \forall v \in G$
- 完全圖K~n~明顯是n-regular graph
- n個點的路徑稱為$=P_n$
- n個點的環路$=C_n$
- Wheel graph $W_n$
- $C_n$中間加個vertex與$C_n$上的點相連
- 超立方體 hypercube / n-cube $Q_n$
- 每個點以n個bit表示，兩個點相鄰的充要條件是恰有一個bit不同
- n立方體，每個vertex degree皆為n
- $2^n$個vertex，$2^n$(vertex) $\times n=n2^n$ (degree)，每個邊會算兩次，因此edge=$n2^{n-1}$
- 是bipartite的一種!!!
- Subgraph
- 點和邊是原圖edge set & vertex set的子集
- Spanning subgraph
- 和原圖有相同的vertex set (vertex一樣多)
- Induced subgraph
- vertex set是原圖的subset，但那些vertex在原圖中有的邊，在這裡也要存在
- [說明](https://www.youtube.com/watch?v=snVBGA-cMeo)
- 定義很多，請記清楚! 證明常常須從定義下手!

## 6-2 圖形表示法與同構
- adjacency matrix
- 應該很熟悉，表示兩個點中有幾條邊(直接)相連
- 如果是multigraph，可能有大於1的值
- incidence matrix
- column上方是$e_1, e_2 ...e_{|E|}$，row的旁邊是$v_1, v_2 ...v_{|V|}$
- $m_{ij}=1$, if $v_i是e_j$的端點
- $m_{ij}=0$, others
- 同構 isomprphic
- 存在$f為可逆函數:V_1 \rightarrow V_2$
- 且$\forall a,b \in V_1, (a,b) \in E_1 \iff (f(a),f(b)) \in E_2$
- G1, G2稱為同構
- 或是更簡單的: 如果能==重畫==讓G1變G2，則G1,G2同構

## 6-3 圖的基本性質
- $\displaystyle \sum_{v \in V} \deg(v)=2|E|$
- 對任意無向簡單圖/多重圖
- ==奇數點的個數必為偶數個==
- 極長路徑 maximal path
- 路徑P如果兩端點無法繼續延伸，稱之極長路徑
- 未必是圖中最長的路徑
- $\displaystyle \sum_{v \in V} id(v) = \sum_{v \in V} od(v)$，id(v)為indegree，od(v)為outdegree
- 來源: 習題6-33

- 這張課本很多證明/定理/推廣，最好去看看

## 6-4 尤拉迴路及漢米爾頓環路
- 注意: cycle無起終點之分(可自訂兩點為起點終點計算)，且沒有方向性(算數量時答案要除2)
- Euler circuit
- 經過G中每邊洽一次circuit
- Euler trail
- 經過G中每邊洽一次的trail
- 判斷是否有Euler circuit / trail
- G有Euler circuit $\iff$ G為連通圖且$\forall v \in V, deg(v)$為偶數
- $K_n$有Euler circuit $\iff$ n is odd (think why)
- $K_{n,m}$有Euler circuit $\iff$ n,m are even (think why)
- G有Euler trail $\iff$ G中洽有0或2個vertex的degree為奇數
- Hamiltonian cycle
- 經過G中每點洽一次cycle
- Hamiltonian path
- 經過G中每點洽一次path
- 判斷是否有Hamiltonian cycle / path
- 以下簡稱Hamiltonian cycle為C

- 必要條件(如果不成立，就不存在C)
- $\forall v \in V, deg(v)\geq 2$
- 若$\exists v \in V, deg(v)=2$，則與v相鄰兩邊必在C中
- 若$\exists v \in V, deg(v)=2$，且已知與v相連的某兩邊在C中，則其他與v相鄰的邊必不在C中
- 充分條件(如果成立，必存在C)
- G是loop-free undirected graph
- $|V|\geq 3, \deg(x)+\deg(y) \geq n-1, \forall x,y, \in V,x\not=y$
- 存在Hamiltonian path
- $|V|\geq 3, \deg(x)+\deg(y) \geq n, \forall x,y, \in V,x\not=y$
- 存在Hamiltonian cycle
- 充要條件
- 用$K_{m,n}$判斷前可先嘗試把node塗色成bipartite
- $K_n$必有Hamiltonian cycle，$n\geq 3$ (think why)
- $K_{m,n}$有Hamiltonian cycle$\iff m=n$
- $K_{m,n}$有Hamiltonian path$\iff |m-n|=1$
- 其他常用方法
- 把所有確定在C中的邊列出來，如果發現形成cycle了卻沒包含所有vertex，或出現超過一個cycle，則矛盾，C不存在

## 6-5 平面圖
- 本章重點: 判斷一圖G是否為planar
- 證明是planar
- G為平面圖$\iff$G不含子圖與$K_5, K_{3,3}$
- 證明非planar (==以下不成立就不是planar，但成立不一定是planar !==)
- G不為平面圖$\iff$G含子圖與$K_5, K_{3,3}$
- $v-e+r=2$， r是region數量
- $v-e+r=1+M$， M是component數量
- $\displaystyle \frac{3}{2}r \leq e \leq 3v-6$，G有三角形
- $\displaystyle e \leq 2v-4$，G不含三角形(ex. bipartite)只能用這個判斷
- 同胚 homeomorphic (看課本)

## 6-6 著色理論
- 對偶圖 Dual graph
- 把著色的圖塊畫成vertex的圖
- chromatic number
- 定義:$\chi(G)=min\{\lambda |P(G,\lambda) > 0\}$
- 解釋:用最少的顏色幫G的v上色，使得任何一邊的兩端都有不同色，記做$\chi(G)$
- $\chi(K_n)=n$ (think why)
- $\chi(P_n)=2$ (think why)
- $\chi(G) = 2 \iff$bipartite
- 平面圖的chromatic number皆 $\leq 4$
- 著色多項式
- $P(G,\lambda)$表示至多用$\lambda$種顏色對G做正當著色的方法數
- $P(G,\lambda)=P(G-e,\lambda)-P(G\cdot e,\lambda)$
- 解釋看課本，這個很好用，另外一個公式(定理6-16)就可以丟了
- 合法的$P(G,\lambda)$
- 常數向必為0 (think why)
- 係數合必為0 (think why)
- 最高次係數必為1
- 裡面有subgraph $K_n \implies \chi(G) \geq n$
- 嘗試用n把G著色，九成會成功
- 失敗的話，加一個顏色看看

# CH7 樹

## 7-1 樹的介紹
- Tree
- acyclic connected graph called tree
- 只有一個vertex的tree: degenerate tree / trivial tree
- ==tree必為bipartite==
- tree性質
- 任兩點間都有path
- tree的$|E|=|V|-1$
- 去掉任意edge就變非連通圖
- forest:
- acyclic graph
- 可以是一棵樹或多棵樹

## 7-2 有根樹
- root
- 有向樹中唯一存在v，id(v)=0，v稱作root
- m元樹 m-ary tree
- 每個內部結點最多m個兒子
- m=2就是binary tree
- full tree v.s complete tree
- full tree: 
- complete tree: 
- 公式都不用背，憑感覺都寫得出來。天平題目(例14)比較需要小心

## 7-3 生成樹
- Matrix tree theorem
- $m_{ij}=deg(v_i)$ if i=j
- $m_{ij}=0$ if $v_i, v_j$無邊相連, i$\neq$j
- $m_{ij}=-1$ if $v_i, v_j$有邊相連, i$\neq$j
- 這個矩陣任意餘因子(都相同)就是G的相異spanning tree個數
- 餘因子cofactor怎麼求要複習一下
- Branch
- G的生成樹T中的edge稱為branch
- Chord
- 不在G的生成樹T中的edge稱為chord

## 7-4 最小生成樹
- 介紹Kruskal, prim algorithm
- algo都講過，skip

## 7-5 前置碼
- 前置碼 prefix code
- binary字串的集合中，任意字串皆不為其他字串的prefix
- Huffman's tree是optimal tree的一種
## 7-6 樹的搜尋
- 前序、中序、後序
- 熟到爛掉，skip

# CH8 演算法分析
- skip, 留給演算法

# CH9 代數結構
- <font color=red>CP值很低的一張，全部章節中最難，又很少考，後面真的有時間再回頭讀</font>
## 9-1 代數系統
- 代數系統
- 封閉性 closed
- 結合性 associative
- 交換性 communicative
- 單位元素 identity
- 反元素 inverse
- 半群 semigroup
- 封閉性
- 結合性
- 單群 monoid
- (半群+單位元素)
- 封閉性
- 結合性
- 單位元素

其他練習: 精選範例1, 2, 4, 6
## 9-2 群
- 群 group
- (單群+反元素)
- 封閉性
- 結合性
- 單位元素
- 反元素
- 交換群 abelian group
- (群+交換性)
- 封閉性
- 結合性
- 交換性
- 單位元素
- 反元素
- 基數 order
- 群的大小$|G|$，計做$o(G)$
- $o(G) \not= \infty \implies 有限群$
- $o(G)= \infty \implies 無限群$

其他練習: 例20, 精選範例1,2,7

## 9-3 二個重要的有限群
- 模同餘群 group of congruence modulo n
- $(Z_n, +_n)$
- 從例子中回憶 $(Z_{12}, +_{12})$
- [5]+[3]=8
- [5]+[8]=1
- 單位元素為0
- $[3]^{-1}=[9]$
- 對稱群/排列群 symmetric group/ permutation group
- 定義好煩，直接看下面這些題目
- 例25, 27, 29, 30, 31，注意事項9-10, 9-11, 範例3
## 9-4 子群
- 若G為group，H={e}必為G的子群
- 若G為group，G本身必為G的子群
- H為G的子群 $\iff \forall a,b \in H, ab^{-1} \in H$
- 例33
- 都是證明，我先skip

## 9-5 循環群
- 循環群
- $\exists a \in G使得 G=\{a^k | k \in Z\}$
- a稱作G的generator
- 基數 order (跟上面不一樣!)
- 若$a \in G$存在最小正整數$a^n = e$，則order of a$=o(a)=n$
- a不存在n的話$o(a)=\infty$

其他練習: 精選範例1,2
## 9-6 陪集
- 左(右)陪集 left(right) coset
- 課本p9-61
- $Ha=\{ha|h \in H\}$稱H在G中的一個左陪集(right coset of H in G)
- Lagrange 定理
- G為有限群，H為G的子群，$o(G)=o(H) \cdot k$
- 好多證明skip

其他練習: 精選範例1
## 9-7 商群
- 好難看不懂skip

## 9-8 同態與同構
- 好難看不懂skip

## 9-9 環
- $(S, \oplus, \cdot)為一個代數系統滿足$
- $(S, \oplus)$為一個交換群(封閉、結合、單位、反、交換)
- $(S, \cdot)$為一個半群(封閉、結合)
- $\cdot 對 \oplus$有分配性
- $a\cdot(b\oplus c) = (a\cdot b) \oplus (a\cdot c)$且
- $(b\oplus c)\cdot a = (b\cdot a) \oplus (c\cdot a)$
- 若$(S, \cdot)$有交換性: $(S, \oplus, \cdot)$為一個交換環
## 9-10 整域
- 好難 skip

## 9-11 體
- $(R,+,\cdot)$為一個體
- 定義: $(R,+,\cdot)$為一個交換環，如果他不為0的單位元存在乘法反元素

# CH10 絡與布林代數

## 10-1 偏序集與全序集
- 偏序集 Partial ordered set (POSET or POS)
- $\iff$R滿足 [reflexive, antisymmetric, transitive](#2-2-基本關係)
- $且S \notin \varnothing ，記做(S,R)$
- 全序集 Total ordered set (TOS)
- S為偏序集，且任兩個S中的元素皆可比較，稱作全序集
- 等價於S為一個鏈，因為鏈的排列有n!種，所有全序關係有n!種
- Hasse diagram
- rule: p10-7
- 或直接看例7,8,12就會畫了
- 記得，vertex有上下關係!
- Topological sort
- 例6, 從下往上，一層層拿vertex，同一層拿取順序隨意
- 在偏序集S中，$A \subseteq S$
- 鍊 chain
- A中任兩個元素皆可比較
- 反鍊 antichain
- A中任兩個元素皆不可比較
- 不好描述卻很重要，看p10-11或例10,11,12
- 上界 upper bound
- 下界 lower bound
- 最小上界 least upper bound ，lub(a,b)
- 最大下界 greatest lower bound，glb(a,b)
- 極大元素 maximal element
- 極小元素 minimal element
- 最大元素 greatest element / maximum element
- 最小元素 least element / minimum element
- 其他練習: 精選範例都可以看

## 10-2 絡
- 絡 lattice
- 偏序集$(S, \leq)$滿足$\forall a,b \in S, lub(a,b)存在且glb(a,b)存在$
- lub(a,b) $=a \vee b$
- glb(a,b) $=a \wedge b$
- 宇上界、宇下界 (若存在，必定唯一)
- universal upper bound: $I$
- universal lower bound: $O$
- 有界絡 bounded lattice
- 絡存在$I$和$O$
- 對偶 duality
- $\leq \iff \geq$
- $\vee \iff \wedge$
- $I \iff O$
- $\overline{} \iff \overline{}$
- 其他練習:精選範例1,2

## 10-3 布林代數
- 布林代數 boolean algebra
- S是有界絡、分配絡、互補絡，稱作布林代數
- 對偶 duality
- $\subseteq \iff \supseteq$
- $\cup \iff \cap$
- $U \iff \varnothing$
- $\overline{} \iff \overline{}$
- 判斷是否$D_m$為布林代數
- $D_m = \{1\leq a \leq m | a是m的正因數\}$
- 充要條件: $m=p_1p_2..p_k其中p_1,p_2...p_k$為相異質數
- 必要條件: 元素個數有$2^n, n\in Z$
- 其他練習: 精選範例1,2,4
## 10-4 布林表示式與布林函數
- disjunctive normal form (d.n.f) / sum of product (SOP)
- conjunctive normal form (c.n.f) / product of sum (POS)
- 怎麼轉換，看例32
## 10-5 布林表示式的最小化
- 邏設的東西，不難懂但很難筆記，自己看
## 10-6 名題邏輯
- 一個敘述不是真就是假，稱作命題
- 真理、矛盾、可滿足
- 真理 (tautology/valid): 不管帶什麼值進入命題皆為true
- 矛盾 (contradiction): 不管帶什麼值進入命題皆為false
- 可滿足 (satisfiable): 不是矛盾，即為可滿足
- imply 的truth table只有在$1 \implies 0$是false，其餘皆true
- 兩個命題為等價也可以用truth table驗證
- 其他練習: 精選範例1,3,7,10
## 10-7 一階命題
- 廣義De-Morgan's law
- $\neg[\forall xP(x)] \equiv \exists x \neg P(x)$
- $\neg[\exists xP(x)] \equiv \forall x \neg P(x)$
- 題型一: 求negation
- p10-106: $\forall x[x \in A \implies \exists y (y \in B \wedge y^2 = x)]$
- ans: $\exists x[(x \in A) \wedge \forall y (y \notin B \vee y^2 \not= x)]$
- 清大計科109: 
- ans: 
- 題型二: 求翻譯
- 
- 

# CH11 玻里雅計數
## 11-1 Burnside's theorem
- 做題目就會了
- 其他練習: 例6, 精選範例1,4

## 11-2 Polya theorem
- 直接看例14, 精選範例1,2

# CH12 編碼與解碼
- <font color=yellow>聽說只有成大會考，反正我最後是沒讀了，考出來就ㄎㄎ</font>
## 12-1 編碼
- d-error detecting
- 一個code set能偵測$\leq d$個錯誤
- 最小漢明距離$\geq d+1$
- d-error correcting
- 一個code set能更正$\leq d$個錯誤
- 最小漢明距離$\geq 2d+1$
- 最小漢明距離$=min\ w(z),z \in C$ (code group)
- $w(x)=n$
- binary string中有n個1
- 王廷基講義ch5-1有提到Hamming Single Error Correcting (SEC) Code
- 只有看過交大考過一次，要放掉12張不是問題

## 12-2 解碼
放掉，發現幾乎不考12張...

# CH13 有限狀態機
## 13-1 有限狀態機
- 看一下state table怎麼畫
- Moore的狀態長在state上，Mealy的狀態隨input改變
- Moore的output會比input多一個(在S0沒有input時就有一個output了)
- 其他都是已經知道的
- 其他練習:例4，精選範例1,2,3
## 13-2 有限狀態機的簡化
- 化簡
- 找最短分別字串(minimal distinguishing string)
- 其他練習:例8,精選範例3
## 13-3 語言
- 以下為一種language範例
- L=$\{0^k10x\ | k\geq 0, x \in \{0,1\}^*\}$
- $\Sigma^0 = \{\lambda\}$
- $\Sigma^+ :不含\lambda$的任意有限長度字串集合
- $\Sigma^* = \Sigma^+ \cup\Sigma^0$
- $A^*$: A的Kleene closure
- 題目: 例15
- 遞迴定義:
- 題目: 例16,17
- 其他練習: 精選範例1~5
## 13-4 文法
- 以下為一種(regular) grammar範例
- S-->aB
- B-->bA
- B-->b
- A-->aB
- A-->a
- grammar有四種
- type 0: phrase-structure grammar
- 沒有限制，愛怎麼寫就怎麼寫
- type 1: context-sensitive grammar
- 不能有A--->B這種右邊是純變數的語法
- type 2: context-free grammar
- 不能有AB--->c這種左邊出先兩個變數的語法
- type 3: regular grammar
- 左邊一個變數A，右邊只能是{a, aB, $\lambda$} (只是舉例)
- 其他練習: 精選範例1,2,6,7
## 13-5 自動狀態機
- Finite state automata (FSA)
- 很熟悉的東西
- pumping lemma先跳過 (張俊盛slide ch4)
- 其他練習: 例39, 41, 精選範例1,2,3

## 13-6 非決定自動狀態機
- nondeterministic finite state automata (NFSA)
- NFA to DFA (張俊盛slide ch2b)，或觀察精選範例3
- 其他練習: 例43, 精選範例1,2

## 13-7 正規表示式
- 正規表示式 vs 正規集
- $0^* \iff \{0^k|k \geq 0\}$
- $(0+1)^* \iff \{0,1\}^*$
- $0+1^* \iff \{0\} \cup\{1^k|k \geq 0\}$
- Kleene's theorem
- L是正規集$\iff$存在FSM M認知L
- 以下四者能力等價
- regular grammar
- regular expression
- DFA
- NFA
- 把FSA轉成regular expression (一個個把state合併刪除，張俊盛slide ch3 p49)
- 其他練習: 例52, 精選範例2,3,4,5

## 13-8 圖靈機
- T=(I,S,f,s0), I 包含空白符號B
- five-tuple example: (s0,1,s1,0,R)
- 狀態為s0,看到1，下個state變成s1，把剛剛看到的1換成0，往右移動一步
- 詳細看p13-80