# 離散數學
###### tags: `MyNTUST`
{%hackmd @CA-Lee/MyNTUST_banner %}
[TOC]
Logic and Proofs
===
Propositional Logic
---
### 專有名詞
- **Propositions 陳述句**
- 有明確的真假值 (True/False)
- proposition variable
- 變數，常用 p, q, r, s
- eg.
- 月亮是綠色起司做的 (False)
- 1+0=1 (True)
- 反例
- 坐下 (not proposition)
- x + 1 = 2 (不確定 x 是多少)
- **Compound Proposition**
- 邏輯連接符號 + proposition
- negation 否定 ($\neg$)
- NOT 的概念
- $\neg T = F$
- conjunction 且 ($\land$)
| p | q | $p \land q$ |
| --- | --- | -------- |
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
- disjunction 或 ($\lor$)
| p | q | $p \lor q$ |
| --- | --- | ---------- |
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
- exclusive or 互斥或 ($\oplus$)
| p | q | $p \oplus q$ |
| --- | --- | ---------- |
| T | T | F |
| T | F | T |
| F | T | T |
| F | F | F |
- implication 蘊涵 ($\rightarrow$)
| p | q | $p \rightarrow q$ |
| --- | --- | ---------- |
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
- If p, then q (若 p 則 q)
- p, q 之間並不需要有關連(相依性)，implication 只是表示兩者真假值之間的關聯
- 如果 p = F，則不管 q = T 或 q = F，$p \to q$ 都成立(因為 **若 p 則 q** 仍然成立)
- 其他表示法
- if p, q
- q if p
- p is sufficient for q (p 是 q 的充分條件)
- q is necessary for p (q 是 p 的必要條件)
- inverse (換質，否命題)
- $\neg p \to \neg q$
- 前提和結論改為否定陳述
- converse (換位，逆命題)
- $q \to p$
- 前提和結論對調
- contrapositive (換質換位，否逆命題)
- $\neg q \to \neg p$
- 前提和結論改為否定陳述且對調
- eg. It raining is a sufficient condition for my not going to town.
- converse: If I do not go to town, then it is raining.
- inverse: If it is not raining, then I will go to town.
- contrapositive: If I go to town, then it is not raining.
- biconditional 雙條件 ($\leftrightarrow$)
| p | q | $p \leftrightarrow q$ |
| --- | --- | ---------- |
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | T |
- p if and only if q (若且唯若 p 則 q ／ q 若且唯若 p)
- 其他表示法
- p is necessary and sufficient for q (p 是 q 的充分必要條件)
- if p then q , and conversely
- p iff q
- truth table 真值表
- 列出各種真值組合
- row
- 有 n 個 propostion variables 時，會有 2^n^ 個 row
- column
- 包含每個變數、中間的過程及最後的結果
- eg. $p \lor q \Rightarrow \neg r$
| p | q | r | $\neg r$ | $p \lor q$ | $p \lor q \Rightarrow \neg r$ |
| --- | --- | --- | -------- | ---------- | ----------------------------- |
| T | T | T | F | T | F |
| T | T | F | T | T | T |
| T | F | T | F | T | F |
| T | F | F | T | T | T |
| F | T | T | F | T | F |
| F | T | F | T | T | T |
| F | F | T | F | F | T |
| F | F | F | T | F | T |
- equivalent propostions 等價敘述句
- 所有情形下結果都一樣，可用真值表驗證
- eg. show **implication** is equivalent to the **contrapositive**
- non equivalence 不等價
- tautology 恆成立
- eg. $p \lor \neg p$
- contradiction 恆不成立
- eg. $p \land \neg p$
- contingency 不一定成立
- eg. $p$
### 優先順序
| 符號 | 順位 |
| ------------- | ---- |
| () | 1 |
| $\neg$ | 2 |
| $\land$ | 3 |
| $\lor$ | 4 |
| $\Rightarrow$ | 5 |
| $\iff$ | 6 |
Application of Propositional Logic
---
### 英文轉換成邏輯敘述句
**#1**
If ++I go to Harry’s++ or ++to the country++ , ++I will not go shopping++.
### Consistent System Specifications
consistent (相容): 一組 propositions 可以同時成立 (類似於方程式**有解**的概念)
### Logic Puzzles
島上有兩種人，騎士和惡棍。騎士只會說真話，惡棍只會說謊話。今天遇到島上 A B 兩人：
A: B 是騎士。
B: 我們不一樣。
**解：**
設 p 為 A 的敘述句，q 為 B 的敘述句，解出 p, q 就知道 A B 是哪種人。
| p | q | 合理 |
| --- | --- | ---- |
| T | T | F |
| T | F | F |
| F | T | F |
| F | F | T |
> If A is a knight, then p is true. Since knights tell the truth, q must also be
true. Then (p ∧ q)∨ ( p ∧ q) would have to be true, but it is not. So, A is
not a knight and therefore p must be true.
If A is a knave, then B must not be a knight since knaves always lie. So, then
both p and q hold since both are knaves.
Propositional Equivalence
---
### 名詞介紹
- tautology
- 恆為 T 的 proposition
- contradiction
- 恆為 F
- contingency
- 不一定為 T 或 F
- 連續 $\lor$
- $\bigvee_{j=1}^{n} p_j$
- 連續 $\land$
- $\bigwedge_{j=1}^n p_j$
### 重要邏輯等價公式
- **De Morgan’s Laws 迪摩根律**
- $\neg(p \land q) \equiv \neg p \lor \neg q$
- $\neg(p \lor q) \equiv \neg p \land \neg q$
- Identity Laws 恆等律
- $p \land T \equiv p$
- $p \lor F\equiv p$
- Domination Laws 支配律
- $p \land F \equiv F$
- $p \lor T \equiv T$
- Idempotent laws 冪等律
- $p \land p \equiv p$
- $p \lor p \equiv p$
- Double Negation Law 雙非律
- $\neg(\neg p) \equiv p$
- Negation Laws 否定律
- $p \land \neg p \equiv F$
- Commutative Laws 交換律
- $p \land q \equiv q \land p$
- $p \lor q \equiv q \lor p$
- Associative Laws 結合律
- $(p \land q) \land r \equiv p \land (q \land r)$
- $(p \lor q) \lor r \equiv p \lor (q \lor r)$
- Distributive Laws 分配律
- $p \land (q \lor r) \equiv (p \land q) \lor (p \land r)$
- $p \lor (q \land r) \equiv (p \lor q) \land (p \lor r)$
- Absorption Laws 吸收律
- $p \lor (p \land q) \equiv p$
- $p \land (p \lor q) \equiv p$
- $p \to q \equiv \neg p \lor q$
### Satisfiability
- 如果可以找到一組真值設定可以讓一個 compound proposition 為真，則該 proposition 為 **satisfiable**，否則為 **unsatisfiable**
Predicate Logic
---
- a.k.a. Propositional function
- P(x) 表示帶入 x 之後會變成一個 proposition (會有一個真假值)
- 帶入的變數可以是多個 (e.g. R(x,y,z))
- 可以和其他的 proposition 組合 (e.g. $P(-1) \land P(3)$)
- domain 定義域
- often denoted by $U$
- variable
- propositional function has variables (such as $x$ in $P(x)$) which can be replaced by element in its domain ($U$)
Quantifier
---
Quantifier有時僅使用判斷而非迴圈逐個檢查，因為domain中元素數可能無限多
- universal quantifier 全稱量詞 ($\forall$)
- $\forall x \space P(x)$ (for all x, P(x))
- 對 domain 中所有 x 都使 P(x) 為 T
- existential quantifier 存在量詞 ($\exists$)
- $\exists x \space P(x)$ (for some x, P(x))
- domain 中有至少一個 x 使 P(x) 為 T
- uniqueness quantifier 唯一量詞／唯一存在量詞
- $\exists ! x \space P(x)$ (There is one and only one x such that P(x))
- 存在唯一一個 x 使 P(x) 為 T
- 比較少用到
- quantifier 比所有邏輯符號都還優先
- $\forall x \space P(x) \lor Q(x)$ is mean $(\forall x \space P(x) ) \lor Q(x)$
Translating English -> Logic
---
**Learn from example**
> ++Every++ student in this class has taken a course in Java.
- sol I
- domain $U$ : all students in this class
- propositional function $J(x)$ : x has taken a course in Java
- ans: $\forall x J(x)$
- sol II
- domain $U$ : all people
- propositional functions
- $J(x)$ : x has taken a course in Java
- $S(x)$ : x is a student in this class
- ans: $\forall x (S(x) \Rightarrow J(x))$
- $\forall x (S(x) \land J(x))$ 是錯的，因為語意不同，題目的意思是**所有班上的學生都修過 Java 課**而不是**是班上的學生且修過 Java 課**
> ++Some++ student in this class has taken a course in Java.
- sol I
- domain $U$ is all student in this class
- $\exists x J(x)$ (J(x) is same as former example)
- sol II
- domain $U$ is all people
- $\exists x(S(x) \land J(x))$ (S(x) and J(x) is same as former example)
- why $\exists x (S(x) \Rightarrow J(x))$ was wrong?
- $F \Rightarrow T$ and $F \Rightarrow F$ are also true
- 如果有不是班上的學生但有學 Java 課，仍然會使此 predicate 成立
Equivalence in Predicate Logic
---
- 基本上還是可以沿用的！
- 含有 predicate 及 quantifier 的敘述如果在所有情形都有一樣的真值則他們就是 **logically equvalent**
Quantifiers as Conjunctions and disjunctions
---
- $\forall x P(x) \equiv \bigwedge_{x} P(x)$
- $\exists x P(x) \equiv \bigvee_{x} P(x)$
Negating Quantified Expressions
---
- e.g. $\forall x \space J(x)$
- 班上的每個學生都修過 Java
- domain 是班上的每個學生
- $\neg \forall x \space J(x)$
- 班上的每個學生都修過 Java 課不成立
- $\Rightarrow$ 班上至少有一個學生沒修過 Java 課
- 也就是說，$\forall$ 的否定就是要**找反例**
- $\neg \forall x J(x) \equiv \exists x \neg J(x)$
- e.g. $\exists x \space J(x)$
- $\neg \exists x \space J(x)$
- 每個學生都沒修過 Java 課
- $\forall x \neg J(x)$
- De Morgan's Laws again
- $\neg \forall x P(x) \equiv \exists x \neg P(x)$
- $\neg \exists x P(x) \equiv \forall x \neg P(x)$
- ==++***很重要***++== (螢光筆+底線+粗體+斜體)
```
缺1.6~1.8
```
Sets, Functions, Sequences, Sums, and Matrices
===
Sets
---
Set Operations
---
Functions
---
Sequences and Summations
---
### Sequences
- 中文: 序列
- 定義: a function from a subset of the set of integers to a set $S$
- geomertric progression
- 中文: 等比數列
- arithmetic progression
- 中文: 等差數列
- String
- 中文: 字串
- 定義: a finite sequence of characters
### Recurrence Relations
- 中文: 遞迴關係
- 定義: 使用前面 $a_{1}$ 至 $a_{n-1}$ 項的值表達 $a_{n}$
- 可以與迭代(Iterative)互換(參見下方 Iterative Solution)
- 迭代：使用 $n$ 與常數表達 $a_{n}$
- Fibonacci Sequence
- $f_n=f_{n-1}+f_{n-2}$
### solving recurrence relation
- closed formula
- 可以直接求得 f(n) 的公式
- Iterative Solution
- 從 $a_1$ 開始，依序列出 $a_n$ 的算式，從中找出規律
- 求 $a_n$，將 $a_{n-1}$ 替換成 $a_{n-2}$，持續替換直到式子內只有用到 $a_1$ (首項)
### Summations
$S_n = \sum^{n}_{j=m} a_j = a_m+a_{m+1}+a_{m+2}+ \cdots + a_n$
- 中文: 求和／加總
- 級數(Series): 序列的和
- Geometric Series
- 中文: 幾何級數／等比級數
- $S_n = \frac{ar^{n+1}-a}{r-1} , r \neq 1$
- $S_n = \sum^{n}_{j=0} a_j = (n+1)a , r=1$
Cardinality of Sets
---
- $|A|=|B|$ 只有在 A 和 B 之間每一個元素都存在一對一對應關係時成立
- $|A| \le |B|$ 只有在 A 的每一個元素都可以一對一對應到 B（B 到 A 不用）時成立
- 不可以一對多，也不可以多對一
- countable infinity
- 可數無限
- $\aleph_0$
- 讀作 aleph null
- $|S|=|Z^+|$
- S 可以一對一對應到正整數集合內，可以想成可以為 S 的每一個元素編號
- https://www.youtube.com/watch?v=Uj3_KqkI9Zo
- 整數、正整數、負整數、奇數、偶數、質數、有理數都是可數無限
- uncountable infinity
- 不可數無限
- $|S|=|R|$
- 實數不可數
- 用對角線證法證明
Matrix
---
- 矩陣相乘
- $$
\begin{bmatrix}
a&b\\
c&d\\
\end{bmatrix}
\times
\begin{bmatrix}
p&q\\
r&s\\
\end{bmatrix}
=
\begin{bmatrix}
ap + br & aq + bs\\
cp + dr & cq + ds\\
\end{bmatrix}
$$
Zero-one matrix
---
- element $\in \{0,1\}$
- join
- $A \lor B = A_{ij} \lor B_{ij}$
- meet
- $A \land B = A_{ij} \land B_{ij}$
- product
- $A \odot B$
- replace $\times$ by $\land$ , $+$ by $\lor$
- power
- $A^{[n]} = A \odot A \odot A \odot \ldots \odot A$
Induction and Recursion
===
Counting
===
**計數**
The Basic of Counting
---
- the product rule 乘法原理
- 若一程序(procedure)可以分解為一序列共$k$個任務(task)，其中第$m$個任務有$n_m$種方式進行，則此程序有$n_1n_2...n_k$種方式進行
- prosudocode:
```
k := 0
for i1 := 1 to n1
for i2 := 1 to n2
.
.
.
for im := 1 to nm
k := k + 1
final: k = n1 * n2 * ... * nm
```
- the sum rule 加法原理
- 若一任務(task)可以有$n_1$或$n_2$或...$n_k$種**不重複**方式進行，則此任務有$n_1+n_2+...+n_k$種方式進行
- prosudocode:
```
k := 0
for i1 := 1 to n1
k := k + 1
for i2 := 1 to n2
k := k + 1
.
.
.
for im := 1 to nm
k := k + 1
final: k = n1 + n2 + ... + nm
```
- the subtraction rule (principle of inclusion and exclusion) 排容原理
- 若一任務可以有$n_1$、$n_2$、...、$n_k$共$k$種方式進行，則此任務有$n_1+n_2+...+n_k$減去**當中重複項**種方式進行
- $|A_1 \cup A_2 \cup ... \cup A_k|=|A_1|+|A_2|+...+|A_k|-|A_1 \cap A_2 \cap ... \cap A_k|$
- the division rule 除法原理
- 若使用一個支援目標任務的$n$種解決方法的輔助程序，且每種解決任務方式皆對應輔助程序的$d$種方法，則此任務有$n/d$種方法
- $|B|=|A|/d$
- tree diagram 樹形圖
- aka 列出所有可能性硬幹
The Pigeonhole Principle
---
- 鴿籠原理
- 若$k$為一正整數，且有$k+1$個物件需放進$k$個箱子中，則至少有一個箱子中有兩個或更多物件。
- 從$k+1$個元素的集合映射至$k$個元素的集合的函式$f$必然不是一對一函數
- Generalized Pigeonhole 廣義鴿籠原理
- 若有$k+1$個物件需放進$k$個箱子中，則至少有一個箱子中至少有$\lceil N/k \rceil$個物件。
- 應用
- 每個具有$n^2+1$個相異實數的序列包含一個長度為$n+1$的嚴格遞增或嚴格遞減子序列
- Ramsey theory 拉姆齊定理
- 一個集合到達一定大小必能滿足特定性質
- Ramsey number 拉姆齊數 $R(m,n)$: 滿足有$m$個元素能形成具一特性的子集、有$n$個元素能形成具另一特性的子集之條件的最小母集合元素數。`(應該是這樣吧?盡力把課本跟維基轉成白話了)`
Permutations and Combinations
---
- Permutation 排列: $P(n, r)=n(n-1)(n-2)...(n-r+1)=\dfrac{n!}{(n-r)!}$
- Combination 組合: $C(n, r)=\dfrac{n!}{r!(n-r)!}=C(n, n-r)$
- 也能以 **binomial coefficient 二項式係數** $\dbinom nr$表示
- combinatorial proof 組合證明: 組合學的標準證明方式
- double counting proofs 算兩次: 左右兩邊用不同方式表示/取得同一個值，則左右值相等
- Bijective proofs 對射法: 若左右兩個集合對射，則兩集合大小相等
Binomial Coefficients and Identities
---
- Binomial theorem 二項式定理: $(x+y)^n=\displaystyle\sum_{j=0}^n\dbinom njx^{n-j}y^i=\dbinom n0x^n+\dbinom n1x^{n-1}y+...+\dbinom n{n-1}xy^{n-1}+\dbinom nny^n$
- $\displaystyle\sum_{k=0}^n\dbinom nk=2^n$
- $\displaystyle\sum_{k=0}^n(-1)^k\dbinom nk=0$
- $\displaystyle\sum_{k=0}^n2^k\dbinom nk=3^n$
- Pascal's identity 帕斯卡恆等式: $\dbinom{n+1}k=\dbinom n{k-1}+\dbinom nk$
- 可以畫出一個 Pascal's triangle 帕斯卡三角形(圖片自己去搜尋引擎看)
- Vandermonde's identity 凡德芒(范德蒙)恆等式: $\dbinom{m+n}r=\displaystyle\sum_{k=0}^r\dbinom m{r-k}\dbinom nk$
- $\dbinom{2n}n=\displaystyle\sum_{k=0}^r\dbinom nk^2$
- $\dbinom{n+1}{r+1}=\displaystyle\sum_{j=r}^n\dbinom jr$
Generalized Permutations and Combinations
---
- Permutations with Repetition 重複排列
- n個物件取r排列且允許重複取用的結果為$n^r$
- 例子: 用英文字母(26個)形成一個長度r的字串(字母可重複出現)
- Combinations with Repetition 重複組合
- n個物件取r組合且允許重複取用的結果為$C(n+r-1, r)=C(n+r-1, n-1)$
- 例子: 一個若干容量的菜籃裝數種水果
- **綜合整理速查表**
| 類型 | 公式 |
| -------- | ---------------------------- |
| 不重複排列 | $\dfrac{n!}{(n-r)!}$ |
| 不重複組合 | $\dfrac{n!}{r!(n-r)!}$ |
| 可重複排列 | $n^r$ |
| 可重複組合 | $\dfrac{(n+r-1)!}{r!(n-1)!}$ |
- Permutations with indistinguishable objects 無區別物件排列
- $\dfrac{n!}{n_1!n_2!...n_k!}$
- 例子: 從單字SUCCESS(有重複字母出現)中可以形成多少種不同字串
### Distributing Objects into Boxes
- 物件分裝 aka 計數問題四種類型的具象化
- Objects: 哪個物件有差(distinguishable) 或 哪個物件沒差(indistinguishable)
- Boxes: 哪個箱子有差(distinguishable) 或 哪個箱子沒差(indistinguishable)
> 以下公式均假設n個object與k個box
- **Distinguishable** *objects* and **Distinguishable** *boxes*
- $\dfrac{n!}{n_1!n_2!n_3!...n_k!}$
- 例子: 撲克牌發若干張牌給數個玩家（撲克牌每張不一樣，每個玩家是不同人）
- **Indistinguishable** *objects* and **Distinguishable** *boxes*
- $C(n+r-1,n)$
- 例子: 堆沒做標記的乒乓球分裝進數個標有號碼的箱子
- **Distinguishable** *objects* and **Indistinguishable** *boxes*
- $\displaystyle\sum_{j=1}^k\dfrac1{j!}\sum_{i=0}^{j-1}(-1)^i\dbinom{j}{i}(j-i)^n$
- 例子: 個不同員工分配進數個相同模樣的辦公室
- **Indistinguishable** *objects* and **Indistinguishable** *boxes*
- $p_k(n)$, the number of ways to write $n$ as the sum of at most $k$ positive integers in increasing order
- 沒有公式 :D
- 例子: 干本書放進沒標示的數個箱子（課本454頁例題11有解題策略）
Graphs
===
**圖**
Graphs and Graph Models
---
### Intro
- 定義：$G(V,E)$
- V: vertices 頂點 (nodes)的非空集合
- E: edges 的集合
- edge 邊: 具有一或二個被稱為endpoints(端點)的關聯頂點
- 術語
- simple graph 簡單圖: 每個邊都連接兩個不同頂點，沒有邊會連接同樣一組的頂點
- Multigraph 多重圖: 可以有邊連接同樣一組的頂點
- loop 迴圈: 連到自己的邊
- pseudograph: 除了multigraph外還能有loop
- directed graph(digraph) 有向圖: E 還會儲存具有起終點的有向資訊(表示邊起終點)
- undirected graph(無向圖)就是一般的圖
### 應用模型
- 網路
- 社群網路
- 軟體設計
- 生物學基因學
- ...不贅述
Graph Terminlogy and Special Types of Graphs
---
### Terminlogy
- adjacent/neighbors 相鄰: 無向圖中的一組相連節點
- neighborhood: 一個節點所有neighbor的集合
- degree (of a vertex in an undirected graph): 一個節點除了loop外的neighbor數量
- The Handshaking theorem(握手定理): $2m=\displaystyle\sum_{v\in V}deg(v)$，m為edge數量
- 對於multiple edges與loops也有效
- 無向圖奇數degree的頂點數量為偶數
- 當(u, v)是有向邊，則他們互相相鄰。u稱為(u,v)的terminal(終端)或end vertex(端頂點)
- $deg^-(v)$: v的in-degree; $deg^+(v)$: v的out-degree
- $\displaystyle\sum_{v\in V}deg^-(v)=\sum_{v\in V}deg^+(v)=|E|$
### Special Simple Graphs
- Complete Graph 完全圖($K_n$): 每一對相異頂點之間都有邊
- Cycle 循環($C_n$): 會形成一個環狀連接(1接2, 2接3,..., n接1)
- Wheel($W_n$): 像cycle，但多了一個跟所有頂點連接的頂點
- n-Cube n維方圖($Q_n$): 線、面(方形)、立體(六面體)、超立方體...
### Bipartite Graph 二部圖
- 定義: 其頂點集合可以分為兩個不相交集合$V_1、V_2$，讓每個edge都變成$V_1、V_2$元素的連結，且沒有連接同集合內頂點的邊
- 二部圖 若且唯若 為每個頂點塗上兩種不同顏色之一後沒有相鄰節點同色
- Complete Bipartite Graph 完全二部圖($K_{m, n}$): 兩個子集合中的頂點都與另一集合的所有頂點連接
### Bipartite Graph and Matching(配對)
- Job Assignment
- Marriages on an Island
- Hall's Mattiage Theorem 霍爾婚配定理:
- The bipartite graph $G=(V, E)$ with bipartition $(V_1, V_2)$ has a complete matching from $V_1$ to $V_2$ if and only if $|N(A)|\le|A|$ for all subsets $A$ os $V_1$
### Applications of Special Types of Graphs
- Local Area Networks
- star topology 星狀拓樸: 二部圖 $K_{1,n}$
- ring topology 環狀拓樸: $C_n$
- 混合拓樸: $W_n$-based
- Interconnection Networks for Parallel Computation
- n-dimensional hypercube n維超立方
- mesh network 網狀網路
### New Graphs form Old
- subgraph 子圖: 有 $G=(V, E)$ 與 $H=(W, F)$ 兩圖，當中$W\subseteq V$ 且 $F\subseteq E$，則H是G的子圖
- 若$H\neq G$，H是G的proper subgraph
- induced subgraph 導出子圖: $G=(V, E)$ 是一圖。可藉由頂點集合V的子集合W導出子圖(W,F)，當中若且唯若兩個端點都在集合W則F包含E中的邊。
- union 聯集: 有$G_1=(V_1, E_1)$與$G_2=(V_2, E_2)$兩圖的聯集形成$(V_1\cup V_2, E_1\cup E_2)$一圖，表記為$G_1\cup G_2$
Representing Graphs and Graph Isomorphism
---
- adjacency list 相鄰表: 表示圖的另一種方式，依照有向或無向可分為以下兩種方式
- 左欄依次列出頂點，右欄填入該頂點所有的相鄰頂點
- 左欄依次列出起始頂點，右欄填入該頂點所有的終端頂點
- adjacency matrix 相鄰矩陣: 從圖產生，當{$v_i$, $v_j$}是$G$的一條邊時值為1，否則值為0
> sparse 稀疏: 包含相對少量邊的
> sparse matrix: 稀疏圖的相鄰矩陣
> dense 稠密: 包含相對大量邊的
- incidence matrix 關聯矩陣: 當邊$e_j$與$v_j$關聯時值為1，否則為0
### Isomorphism of Graphs
- isomorphism 同構[名]: 對於$G_1=(V_1, E_1)$和$G_2=(V_2, E_2)$，若存在$V_1$對$V_2$的一對一唯一對應函數$f$，且對於$V_1$中任意兩相鄰頂點$a$、$b$在$V_2$具有$f(a)$與$f(b)$相鄰。
- 反義: [形]nonisomorphic
- 檢查方式: 看圖、看相鄰矩陣、看路徑
Connectivity
---
- path 路徑: 從某個頂點開始，沿著邊前進，直到某個頂點結束的序列
- length 長度: 長度n的路徑一共包含n個頂點
- circuit 迴路: 起終點是同個頂點（在有向圖也可稱為cycle）
- simple 簡單: 沒有經過任意邊超過一次
- pass through vertices, traverse edges: 在路徑前進的兩種說法
- connected 連通的: 在任意頂點間都能形成路徑
- 反義: disconnected
- 在連通的無向圖中任兩節點必有一條簡單路徑
- cut vertices 割點, articulation points 接合點: 若從圖中移除就會形成複數子圖的頂點
- cut edge, bridge: 若從圖中移除就會形成複數子圖的邊
- nonseparable graph: 沒有割點的圖
- vertex connectivity 連通度: 要使一圖分割所需移除的最少頂點數量
- strongly connected: (有向圖)同時具有從任意相異頂點$a$至$b$的路徑及$b$至$a$的路徑
- weakly connected: (有向圖)轉成無向圖後才能有任意頂點間的路徑
- connting paths:
- 將圖寫成相鄰矩陣$A$，從$v_i$到$v_j$長度$r$的路徑會等於$A^r$中的$(i,j)$項
Euler and Hamilton Paths
---
- Euler circuit 歐拉迴路: a simple circuit containing every edge
- if and only if each of vertices of graph has even degree
```
while H has edges
subcircuit := a circuit in H beginning at a vertex in H that also is an endpoint of an edge of circuit
H := H with edges of subcircuit and all isolated vertices removed
circuit := circuit with subcircuit inserted at the appropriate vertex
return circuit
```
- Euler path 歐拉路徑: a simpe path containing every edge
- (Epath but not Ecircuit) if and only if graph has exactly two vertices of odd degree
- Hamilton path 哈密頓路徑: a simple path passes through every vertex exactly once
- Hamilton circuit 哈密頓迴路: a simple circuit passes throutgh every vertex exactly once
- Dirac's theorem: the degree of every vertex in the graph is at least n/2, then the graph has a Hcircuit
- Ore's theorem: deg(u) + deg(v) >= n for every pair of nonadjacent vertices u and v in the graph, then the graph has a Hcircuit
Trees
===
Introduction to Trees
---
### Rooted Trees
### Trees as Model
### Properties of Trees
Tree Traversal
---
### Traversal Algorithms
### Infix, Prefix, and Postfix Notation
Spanning Trees
---
### Depth-First Search
### Breadth-First Search
### Depth-First Search in Directed Graphs
Minimum Spanning Trees
---
### Algorithms for MSTs
Contributors
===
- [calee](https://calee.tw)
- @youwei
- @Silverfish4epic
Sign in with Wallet
Connect another wallet