離散數學

http://webapp.yuntech.edu.tw/CourPlan/963/9630009.html

======================================================
Discrete Mathematics

http://www.dyu.edu.tw/~lhuang/class/discrete/index.htm



Textbook: K. H. Rosen, "Discrete Mathematics and Its Applications", sixth edition



離散數學漫談朱緒鼎教授 國立中山大學應用數學系

http://www.math.nsysu.edu.tw/article/zhu/



離散數學


--------------------------------------------------------------------------------

比較有效率的學習態度

這不是講義啦, 只是我上課內容的摘要提示, 還是要看課本和作習題才是!
離散數學只需要國中數學為基礎幾乎用不到幾何/微積分, 是數學不好的同學一個重新出發的大好機會.
要記憶中英文的專有名詞.
腳踏實地: 不要背公式, 要勤於舉例. 每學一個名詞, 一定要會舉例及舉反例. 小考考題當中也會不斷出現舉例題.
要嚴格檢查型別.
集合

set, element (member), is a member of (屬於), is contained in (包含於), subset, proper subset, empty set, universal set, cardinality, finite, infinite
注意「屬於」 (這個元素在右邊那個集合裡面可以找得到) 和「包含於」 (這個集合內的每個元素在右邊那個集合裡面可以找得到) 的差別: 若 A = { {1,2}, {3,4} }, 則以下各集合究竟屬於抑或包含於 A? {2,1}, {{2,1}}, {2,3}, {{2,3}}
例: 試列舉出 A = { q/p-p/q | p^2+q^2 <= 5, p,q are in N } 的所有元素.
兩種表示法: 列舉或描述特性
用「描述特性」的方式定義集合時, 把條件部分的每個變數想像成 for 迴圈的一個 dummy variable. 把所有元素列出, 並只保留符合條件的元素. 若有兩個以上變數, 則想像成重疊的 for 迴圈.
power set (冪集合): 2^A = { S | S is contained in A } 例: A = { 2, 3, 5 }, 試問 {2,3} 與 A 的關係, 及 {2,3} 與 2^A 的關係.
數學中常見的集合: N 自然數, Z 整數, Q 有理數, R 實數, C 複數
如何證明兩個集合 A 與 B 相等? 分別證明 A 包含於 B 及 B 包含於 A.
intersection, union, difference, complement, symmetric difference, disjoint (mutually exclusive)
例: 若以 N 為 universal set, 並令 A = { 3, 6, 9, 12 ...} 令 B = { 5n-1 | n is in N }, 試求 (A 與 B 的 symmetric difference) 的 complement.
提示: 分析複雜的運算式, 要把握「不想從前, 不看未來」的原則.
不要背集合運算的公式. 要畫 Venn Diagram 自己下結論.
不要背 principle of inclusion and exclusion (排容原理). 畫 Venn Diagram 自己推導.
如何比較無限集合的大小? 看看是否可找到一對一的對應關係 (one-to-one correspondence).
N, Z, Q 一樣大. 和它們一樣大或更小的集合叫做 countable; 比它們大的集合叫做 uncountable.
R, C 一樣大.
R 比 N 大 (所以是 uncountable) 這個證法叫做 diagonalization.
推論: 每個集合的 power set 都比原集合大.
整數除法

divides (整除), prime (質數)
整除相關定理 (p.23) 注意 (c) 的逆命題未必成立.
如何測試一個奇數是否為質數? (偶數太容易判斷了) 用 3,5,7,... 一直試到它的根號就可以了.
每個自然數都可以做質因數分解.
common divisor (公因數), common multiple (公倍數)
gcd, lcm
Euclidean algorithm (輾轉相除法)
定理: 兩整數的 lcd 可化為這兩數的整數倍之和. (用 Euclidean algorithm 可求出適當的倍數.)
relatively prime (互質)
"x is congruent to y mod m" ("x 與 y 同餘 (以 m 為模時)") 用途之一: 計算某日是星期幾.
邏輯術語

要認得並理解這些術語; 完全不必理會這一單元中的定理與公式
statement/proposition (命題), negation
conjunction ("且"), disjunction ("或")
universal quantifer, existential quantifier
predicate (述語)
converse (逆命題)
equivalent (等價)
淺談證明

簡單的證明, 可從定義著手, 寫出前提與結論, 只需要填中間. 例如 Euclidean Algorithm 的引理.
counterexample (反例)
proof by contradiction (歸謬證法) 例如「根號 2 是無理數」, 又如「R 為不可數」
mathematical induction (數學歸納法): 像推骨牌一樣, 有 basis step 與 induction step.
使用數學歸納法證明範例:
2^n < n! for all n > 3
f(n) < (7/4)^n for all n where f(n) are the Fibonacci numbers.
cos(t) + cos(3t) ... + cos((2n-1)t) = sin(2nt)/(2 sin(t))
2^n 乘 2^n 大的地板當中任意挖掉一格, 必然可以用 L 型的 "三格磁磚" 舖滿.
數數兒

Q: 2^A 有多少個元素?
==> 有多少種方法可以產生 2^A 的一個元素?
==> 要寫出一個元素, 可以分解成那幾個步驟?
==> 畫出一棵 decision tree, 數它的 leaves 個數. (因為每一條通往樹葉的路徑, 代表一種選法.)
Ans: |2^A| = 2^|A|
Q: 從 m 個相異球當中選出 n 個, 排入 n 個不同的位置, 有多少種排法?
==> 要產生出一種排法, 可以分解成那幾個步驟?
==> 畫出一棵 decision tree, 數它的 leaves 個數.
Ans: P(m,n) = m!/(m-n)!
Q: 從 m 個相異球當中選出 n 個, 有多少種選法?
==> 要產生出一種選法, 可以分解成那幾個步驟?
==> 畫出一棵 decision tree, 數它的 leaves 個數. ==> (觀察: 有好多不同的 leaves 其實都只能算作是同一種選法)
==> 挑一片樹葉來看, 數數看還有多少樹葉其實跟它都是相同的. (如何數? 又是另外一個數數兒的問題, 可以摹仿先前的作法...) Ans: C(m,n) = m!/(n!(m-n)!)
C(m,n) 組合的數種意義:
從 m 個相異球當中選出 n 個, 有多少種選法?
m 個元素的集合 A 的子集合當中, 有幾個內含 n 個元素?
(1+x)^m 展開後, x^n 項係數是多少? (稱為 binomial coefficient)
Pascal 三角形的第 m 列第 n 個值是多少?
(「這究竟是一個排列的問題, 還是一個組合的問題?」) 把 n 個紅色的球, 與 m-n 個藍色的球排入 1 到 m 號共 m 個位置, 有多少種不同的排法?
結論: 不要按類型記公式, 因為記了太多公式也不一定知道一個題目要用那一個公式 -- 有些題目既可以當成排列, 也可以當成組合.
m!/(k1!k2!...kt!) 的意義 (m = k1+k2...+kt):
有 k1 個紅球, k2 個藍球, ... kt 個白球 共 m 個球, 排入 1 到 m 號共 m 個位置, 有多少種不同的排法?
有 1 到 m 號共 m 個球, 其中要選 k1 個出來漆成紅色, 選 k2 個出來漆成藍色, ... 選 kt 個出來漆成白色, 共有多少種不同的選法?
(r+b+...+w)^m 展開後, (r^k1)(b^k2)...(w^kt) 項係數是多少? (稱為 multinomial coefficient)
(亦稱為「重複排列」)

結論: 不要按類型記公式! 要按照 "有多少種選/排法" ==> "如何選/排出一種結果" 的方式, 畫樹出來數 leaves!
例: 七男三女坐成一列, 共有多少種坐法? 若女士們一定要坐相連的位置, 有多少種坐法? 若要求男女間隔著坐, 且女士們不願意坐最兩側的位置, 有多少種坐法?
例: n 對夫妻圍著一個大圓桌坐下, 夫妻一定要坐在一起, 有多少種坐法?
全班有 60 人, 每 5 人分成一組. 共有多少種不同的分法?
金字塔模型的五面要塗上五種不同的顏色, 可用的顏色有七種, 共有多少種不同的塗色方法?
我的解題方法供參考:
題目問 "... 有多少種排/選法?"; 我問自己 "... 如何有步驟地產生一種排/選法?" 然後用 principle of multiplication 把所有步驟的排/選法乘起來.
如果數重複了, 就挑一片樹葉 (一個結果) 起來看, 數數看還有多少其他樹葉 (其他結果) 其實跟它都是相同的.
如果題目內有變數 (或數字太大) 不知道該如何數, 就先化簡題目, 用 4, 5 等小數字做一遍.
以上方法已足以應付大部分簡單的排列組合題.

重複組合: 以下問題答案相同
有紅球無限多顆, 黃球無限多顆, ... 共 n 種顏色的球 (各無限多顆), 總共要選出 k 顆, 共有多少種選法?
x1 + x2 + x3 ... + xn = k 有多少組非負整數解?
k 個珠子排成一列, 之間要放入 n-1 個分隔板將它們分成 n 群, 分隔板有多少種放法?
例: x1+x2+x3+...+xn=k 的正整數解有多少個?
Pigeonhole principle (鴿洞原理): 如果 n 隻鴿子要分配入 m 個鴿洞內, 且 m < n, 則至少有一個鴿洞內有兩隻或兩隻以上的鴿子.
Extended pigeonhole principle: 若 n 隻鴿子要分配入 m 個鴿洞內, 則至少有一個鴿洞內有 ... 隻或更多的鴿子.
遞迴關係式

一個函數, 如果它的定義當中又出現它自己, 這樣的定義方式即稱為一個 recurrence relation (遞迴關係式).
一個 sequence (數列) 當然也是函數, 它是 domain (定義域) 在 N 的函數.
一個 recurrence relation 當然不能無窮地遞迴下去, 就好像一個遞迴的副程式必須要有停止遞迴的條件一樣, 一個 recurrence relation 必須要有 initial condition.
用遞迴關係式表達難以直接解決的問題之範例 (答案在本頁的原始碼當中):
平面上 n 條直線, 最多可以把平面分割成多少塊區域? 空間中 n 個平面, 最多可以把空間分割成多少塊區域?
一片 3 * (2n) 的地板, 要用 許多相同的 1 * 2 磁磚舖滿, 有多少種舖法?
連續擲銅板 n 次, 紀錄所得的序列 (正反反正...), 試問「正面不連續出現」的序列有多少種?
n 個石子排成一列, 從左邊開始將石子取走, 每次至少取 1 顆, 至多取 4 顆, 直到全部取完為止, 共有多少種不同的取法? ("第一次取 2 顆, 第二次取 1 顆, ... 最後取 3 顆" 算做一種取法.)
n 個人的帽子掛在牆上, 漆黑之中每人亂取一頂, 試問有多少種取法, 每個人都拿到別人的帽子? ("1 號拿到 6 號的, 2 號拿到 5 號的, ... n 號拿到 2 號的" 算做一種取法.)
0 到 10^n-1 的所有十進位數字當中, 有多少個數字內有連續三個 7? (連續更多個也可以; 連續的三個 7 出現不只一次也可以)
n 個矩陣相乘, 依計算的先後順序括上小括弧 (只影響乘法發生的順序; 矩陣排列的順序則不改變), 共有多少種不同的括法? (因矩陣乘法滿足結合律 associativity, 故各種不同的括法算出來的答案相同.)
Linear homogeneous relation of degree k with constant coefficients: a(n) = r1 a(n-1) + r2 a(n-2) ... + rk a(n-k)
上述類型的遞迴關係式, 其一般式可以由公式求得.
例一: a(n) = a(n-1) + 12 a(n-2), a(0) = -2, a(1) = 13, 求 a(n) 的通式.
解: 寫出這個遞迴關係式的 characteristic equation (特徵多項式): x^2 = x + 12, 解出兩根 4 與 -3, 令 a(n) = c1*4^n + c2*(-3)^n, 以 n=0 與 n=1 代入, 解得 c1=1, c2=-3. 記得用 n=2, n=3 代入檢查一下.
例二: a(n) = 21*a(n-1) - 147*a(n-2) + 343*a(n-3), a(0) = 5, a(1) = 11, a(2) = -35, 求 a(n) 的通式.
解: 寫出這個遞迴關係式的 characteristic equation (特徵多項式): x^3 = 21*x^2 - 147*x + 343, 解出三重根 7, 令 a(n) = c1*7^n + c2*n*7^n + c3*n^2*7^n, 以 n=0, n=1, n=2 分別代入, 解得 c1=5, c2=-4, c3=4/7. 記得用 n=3 代入檢查一下.
注意: 待定常數的個數, 遞迴關係式的次數, 最起碼的邊界條件的個數, 一定相同. 即使有重根出現也一樣.

Linear relation of degree k with constant coefficients: 分別解出 homogeneous solution 與 particular solution...
Cartesian Product 與 Partition

ordered pair, ordered tuple. (與集合不同. 兩個 ordered tuples 要稱得上相等, 必須元素個數相同, 且對應位置的元素相同.)
Cartesian product: A1 x A2 x A3 ... x An = { (a1,a2,...an) | a1 is in A1, a2 is in A2, ... an is in An }
Cartesian product 的元素個數, 等於各集合元素個數的乘積.
例: (A x B) union (C x D) 與 (A union C) x (B union D) 有什麼關係?
例: 線段與線段的 Cartesian product? 線段與圓? 圓與圓?
A partition of a set A (亦稱為 a quotient set of A): A 的某些子集合所成的集合. 這些子集合的聯集必須是 A; 兩兩交集必須是空集合. (用口語說, 就是把所有元素分成好幾國, 每個元素都不可以有雙重國籍, 也不可以沒有國籍.)
一個 partition 內的每個元素 (它本身當然是一個集合) 叫做一個 block 或 cell.
一個集合可以有很多不同的 partitions.
例: 列舉出 A = {a,b,c,d} 所有的 partitions.
例: 若 |A| = 6, 試問要把 A 分割成 3 個互斥子集合, 有多少種分法?
例: 令 A = {a,b,c} x {1,2,3} 試舉一個 A 的 partition 的例子, 要滿足:
partition 內的每個 cell 的元素個數相同.
cell 的個數又與每個 cell 的元素個數相同.
每個 cell 內所含的所有元素 (各是一個 ordered pair), 其第一個元素不可以完全相同.
Q: r 個元素的集合, 可以有多少種不同的 partitioning 方式? 提示: 先計算 S(r,n), 把 r 個不同的物品置入 n 個相同的盒子當中, 且每個盒子都要分到物品, 有多少種分法? 這些數字稱為 Stirling numbers of the second kind. 原題的答案即為 S(r,1) + S(r,2) ... + S(r,r). 答案在網頁的 source 當中.
Binary Relations 基本概念

例: 定義一個從 Z 到 Z 的 binary relation | 如下: a | b 表示 "a 這個整數整除 b 這個整數".
例: 定義一個從 M 到 H 的 binary relation F 如下: a F b 表示 "a 這個男子為 b 這個人的父親".
例: 定義一個從 AP 到 OS 的 binary relation R 如下: a R b 表示 "a 這個應用程式可以在 b 這個作業系統上執行".
例: 定義一個從 S 到 S 的 binary relation RA 如下: a RA b 表示 "a 這顆星球繞著 b 這顆星球轉".
例: 定義一個從 A 到 P 的 binary relation E 如下: a E b 表示 "a 這種動物喜歡吃 b 這種植物".
其他例子: <, <=, ..., "a 認識 b", "副程式 a 呼叫副程式 b", "a 是 b 的父親或母親", ...
上述各例中, 左邊的集合叫做這個 relation 的 domain (定義域); 右邊的集合叫做它的 range (值域).
表示一個 binary relation R 的方法:
(集合表示法) 列舉出所有滿足 a R b 的 (a,b)
(矩陣表示法) 把所有的 a 在左邊排成一行, 所有的 b 在上面排成一列, 在矩陣的每個位置上填入 1 或 0 (視 a R b 是否成立而決定填 1 或填 0).
(有向圖表示法, 常用於 domain = range 時) 把所有的元素一一畫出來 (成為一個個 vertex). 若 a R b 就從 a 畫一道箭頭 (稱為一個 edge) 指向 b.
幾個常見名詞/符號: 以下假設 R 為一個從 A 到 B binary relation, 並以 A = {1,3,5}, B = {0,2,4,6}, "<" = { (1,2), (1,4), (1,6), (3,4), (3,6), (5,6) } 為例.
名詞/符號
set
digraph
範例

x R y
(x,y) in R
有一條 edge 從 x 指向 y
3 < 5

R(x), R-relative set of x
{ y in B | (x,y) in R }
所有「被 x 指到」的 y.
"<"(3) = {4,6}

R(A1), R-relative set of A1
{ y in B | (x,y) in R for some x in A1 }
所有「被 A1 內任何一個元素指到」的 y.
"<"({1,3}) = {2,4,6}

in-degree of y
| { x in A | (x,y) in R } |
指向 y 的箭頭數.
in-degree(4) = 2

out-degree of x
| { y in B | (x,y) in R } |
從 x 指出來的箭頭數.
out-degree(5) = 1

restriction of R to A1
R intersect (A1 x A1)
把 A1 以外的 vertices 及其上 edges 都拿掉.
(通常只用於 A = B 的場合)

complement of R
(A x B) \ R
把原有的 edge 去掉, 沒有的 edge 生出來.
{(1,0),(3,0),...(5,4)}

inverse of R
{ (y,x) | (x,y) in R }
把所有的 edge 方向反過來.
{(2,1),(4,1),...(6,5)}


作業: 將上表加上一行 matrix 表示法的解釋.
Q: 令 A = B = { 1, 2, 3, 4, 5, 6 }, R 為 A 上的 "<" 這個 binary relation, x = 3, z = 4, A1 = {2,5}, 試以 set, matrix, digraph, 等三種表示法將上述各名詞表示出來.
Q: 從 Z 到 Z 的 binary relation "<", 它的 complement 是? 它的 inverse 是?
Q: 若 R 為一個從 A 到 B 的 binary relation, 且 x in A, 試問 R(x) 與 out-degree(x) 有何關係?
提醒: 當書本 (或考題) 說 "令 A x B 的一個子集合 R 表示 ... 這樣的一個 relation" 時, 請以集合表示法理解.
Q: 若 |A| = m, |B| = n, 則從 A 到 B 可以定義出多少個不同的 binary relations?
我們對什麼樣的 relations 有興趣? 若一個 binary relation R on A 內的所有元素都滿足 ... 特性, 則稱 R 為一個 ... relation.
特性
set
digraph

reflexive
(a,a) in R
每個 vertex 都指向自己.

irreflexive
(a,a) not in R
沒有一個 vertex 指向自己.

symmetric
(a,b) in R ==> (b,a) in R
有 edge 的地方一定都是雙向的.

asymmetric
(a,b) in R ==> (b,a) not in R
有 edge 的地方一定都是單向的 (而且沒有 vertex 指向自己).

antisymmetric
(a,b) in R and (b,a) in R ==> a=b
不同的兩個 vertices 之間最多只有一條 edge.

transitive
(a,b) in R and (b,c) in R ==> (a,c) in R
若 a 指向 b 且 b 指向 c, 則 a 指向 c


Q: 令 A 表 Gimp (一套類似 PhotoShop 的軟體, 喜歡畫圖的讀者一定要試試看!) 程式原始碼當中, 所有副程式所成的集合. 定義 C 為一個從 A 到 A 的 binary relation 如下: x C y 表示 x 的程式碼當中呼叫到 y. 試描述 A 的一個子集合 A1, 可以讓 restriction of C to A 為 reflexive.
partial order: reflexive, transitive, antisymmetric 的 binary relation. 例: a 整除 b; A 這個集合包含於 B 這個集合; ...
equivalence relation: reflexive, transitive, symmetric 的 binary relation. 例: a is congruent to b mod 7; a 與 b 這兩顆星球繞著同一顆星球轉; ...
equivalence relation (「同一國的關係」) 與 partition (「把所有元素分成那幾國」) 其實是同一觀念的不同表示法, 從一個可以產生出另外一個.
equivalence class of x 記為 [x], 其實就是先前定義的 R(x), 也就是「和 x 同一國的所有元素所成集合」.
Q: 以下各集合各滿足上述那些特性? R1 = {(a,a) | a is in A}, R2 = {(a,b) | a != b}, R3 = {(a,b) | a, b are in A}, R4 = {}
衍生出來的 relations

complement of R: (A x A) \ R
inverse of R: R-1 = { (b,a) | (a,b) is in R }
reflexisive closure of R: R union { (a,a) | a in A }
symmetric closure of R: R union R-1
transitive closure of R: ...
所謂 "R 的 ... closure" 就是在 R 當中加入最少的元素對, 讓新的 relation 滿足 ... 特性.
Q: 若一個集合原本就已經是 reflexive, 則它的 reflexive closure 為? 若原本就已經是 symmetric, 則它的 symmetric closure 為?
Q: 「a 是 b 的手足」 的 reflexive closure 是? 「a 是 b 的丈夫」 的 symmetric closure 是? 「a 是 b 的父母」 的 transitive closure 是? 「a 知道 b 的電話號碼」 的 transitive closure 是? (答案在原始檔中)
composition of R and S: 若 R 為從 A 到 B 的 relation, S 為從 B 到 C 的 relation, 則定義 R 與 S 的 composition 為 { (a,c) | 存在 b 使得 (a,b) in R 且 (b,c) in S } 並記為 S o R
例:
「a 這學期修 b 這門課」與「b 這門課在星期 c 這天有課」的 composition 為「a 這學期在星期 c 這天有課」.
「a 這個出版社曾經出版過 b 這本書」與「b 這本書可以算是 c 這類的書」的 composition 為「a 這個出版社曾經出版過 c 這類的書」.
「a 是 b 的兒子或女兒」與「b 是 c 的父親或母親」的 composition 為「a 是 c 的兄弟姊妹」
「a 是 b 的父親或母親」與「b 是 c 的兒子或女兒」的 composition 為「a 是 c 的夫妻或自己」
從最後兩個例子可以看出: S o R 與 R o S 不一定相等. 事實上即使 S o R 存在, R o S 甚至未必存在.
符號: (S o R)(x) = S(R(a)) 與 a 有關係的所有 c 所成集合.
若 binary relation R 以矩陣方式表示為 MR, S 以矩陣方式表示為 MS, 則 S o R 如何以矩陣表示? 把一般矩陣乘法的定義當中的數字乘法改成 and, 把數字加法改成 or, 所得結果記為 MR Q MS 稱為 MR 與 MS 的 boolean product, 這個結果正好就是 S o R 的矩陣表示法. 想法: 只要存在有任何一個 b (多了也沒關係) 使得 a R b 且 b R c, 則稱 a (S o R) c.
Q: 給你兩個 relations R 與 S 用 digraphs 表示, 如何求出 S o R 的 digraph 表示法? 提示在本頁 source 某處.
transitive closure of R: 若 R 以矩陣表示為 MR, 則 R 的 transitive closure 以矩陣表示為 MR Q MR2 Q MR3 ... (事實上若 A 內的元素個數為 n, 則上面的無窮 boolean product 只要算前面 n 項就夠了.)
Warshall's algorithm for computing Transitive Closure:
17. for k=1,2,3...n

18. 列出可以到達 k 的 i 有那些 (第 k 列所有 1 出現的地方)

19. 列出從 k 可以到達的 i 有那些 (第 k 行所有 1 出現的地方)

20. 將所有的 (i,j) 填 1.

21. end

22.

到第 k 步為止, 所求得的結果並不是 M^k 也不是 M union M^2 union ... M^k 而是「若只准以 1,2,...k 為中繼站, 有那些地方可以相通?」

函數

何謂函數? 凡是滿足以下特性的 relation 都叫做函數: f 是一個從 A 到 B 的 binary relation, 且 A 的每個元素 a 都滿足 f(a) 恰有一個元素. (注意: 這裡的 f(a) 是 relation 的符號, 也就是 f-relative set of a). 亦即: 若一個 relation 的 domain 當中的每個元素的 out degree 都恰為 1, 則這個 relation 即是一個函數.
約定俗成的偷懶表示法: 若 f 為一個函數, 我們可以將 f(a) = {b} 簡單地寫成 f(a) = b 就好.
函數亦稱為 mapping (映射) 或 transformation (轉換). f(a)=b 當中的 a 稱為 argument (引數), b 稱為 image of a under f (a 在 f 作用下所得到的映象).
從 A 到 B 的 binary relation f, 若它恰好是一個 function, 我們經常用這樣的寫法來表示: f : A --> B
one-to-one function: 「不同的 a 必然映射到不同的 b」 這類函數. 又叫做 injective function 或 injection (嵌射, 一山不容二虎). 亦即, 每個 b 的 in-degree 至多是 1.
onto function: 「每個 b 都是某個 a 的映象」 這類函數. 又叫做 surjective function 或 surjection (蓋射, 每座山上都有老虎). 亦即, 每個 b 的 in-degree 至少是 1.
one-to-one correspondence between A and B: 既是 injective 又是 surjective 的函數. 又叫做 bijective function 或 bijection. 亦即, 每個 b 的 in-degree 恰為 1.
一般的函數 f, 它的 inverse relation f-1 不一定滿足函數的定義; 但若 f 為 bijective, 則 f-1 (它的 inverse relation) 不僅是一個 relation, 還會是一個 bijective function. f-1 稱為 f 的 inverse fucntion (反函數); 我們說 f 是一個 invertible function (因為可以對它求反函數).
因為每個函數也都是一個 relation, 所以像 inverse 與 composition 這樣的觀念都被 "繼承" 下來了. 但要注意 f 的 inverse relation 一定存在; 但 f 的 inverse function 不一定存在.
Order Relations

一個從 A 到 A 的 binary relation R, 若滿足 reflexivity, transitivity, antisymmetry, 則稱為一個 partial order. (A, R) 稱為一個 partially ordered set, 或簡稱為 poset.
若 R 為一個 partial order, 則 R-1 也是一個 partial order, 稱為 R 的 dual. 例如 "小於等於" 的 dual 是 "大於等於"; "包含於" 的 dual 是 "包含", "a 是 b 的因數" 的 dual 是 "a 是 b 的倍數",...
一個 poset (A, R) 當中的兩個元素 a 與 b, 如果 aRb 或 bRa 成立, 則稱 a 與 b 為 comparable. 若 (A, R) 當中的每一對元素都是 comparable, 則稱 R 為一個 linear order, 稱 A 為一個 linearly ordered set, 又稱為 chain.
Q: 請對上述每一名詞舉例.
定理: poset 的 digraph 表示法中, 只會有 loop, 不會有更長的 cycle 出現.
Hasse diagram: 簡化的 poset 表示法.
把所有的 loop 省略不畫 (反正我們知道 poset 一定是 reflexive)
把所有 "由 transitivity 可以推導出來的關係" 省略不畫. (反正我們知道 poset 一定是 transitive)
將 diagram 擺設成所有的箭頭都往上指, (由上述定理知道這一定可以辦得到) 並把所有的箭頭省略不畫,
請練習把 poset 的 digraph 表示法與 Hasse diagram 互換.
假設 (A,R) 與 (B,S) 為兩個 posets. 一個從 A 到 B 的函數 f, 如果它是 one-to-one correspondence (bijection) 而且又滿足: a R b <==> f(a) S f(b), 則稱 f 為一個從 (A,R) 到 (B,S) 的 isomorphism (同構).
兩個 posets 之間, 如果可以找到 isomorphism, 則稱這它們為 isomomorphic posets.
例: 令 A = 2{a,b,c}, R 為 A 上面的 "包含於" 關係; B = {1,2,3,5,6,10,15,30}, S 為 B 上面的 "整除" 關係. 則 (A,R) 與 (B,S) 同構. (事實上它們之間有好幾個 isomorphisms.)
isomorphism 的直覺解釋: 換湯不換葯; 換零件的標籤不換相對關係, 換零件的廠牌不換整體結構 (所以叫做同構).
自己與自己之間的 isomorphism 叫做 automorphism.
為何研究 isomorphism? 希望只要研究少數的 posets, 就可以把所有的定理搬到其他同構的 posets 上直接使用, 不必再證明一次.
Undirected Graph

一個 undirected graph G = (V,E) 包含兩部分: vertices 及 edges.
一個 edge 的表示法: 在無向圖中, 用 {u,v} 表示; 在有向圖中 用 (u,v) 表示.
一個 vertex v 的 degree: 接在 v 上面的 edges 端點個數.
兩頭都落在同一個 vertex 上面的 edge, 叫做一個 loop. (這樣的 edge 對這個 vertex 的 degree 貢獻了 2 次.) 如果沒有特殊說明, 通常我們都假設所討論的 graph 當中沒有 loop.
degree 為 0 的 vertex 叫做一個 isolated vertex.
一個 edges 兩頭的 vertices 稱為 adjacent vertices.
一連串接在一起, 不重複經過同一 vertex 的 edges, 稱為一個 simple path.
起點和終點相同的 simple path, 稱為一個 simple cycle.
一個 graph G 當中, 如果任兩個 vertices 之間都可以找到 simple path, 則稱 G 為 connected; 否則稱 G 為 disconnected. 一個 graph 的每一小塊自成 connected 的部分, 稱為一個 connected component.
特殊的 graphs:
discrete graph: 沒有 edges, 每個 vertex 都是一個獨立的 connected component.
linear graph: ...
complete graph Kn: 任兩個 vertices 之間都有 edge (共 n(n-1)/2 個 edges).
bipartite graph: 一個 graph, 如果可以找到一種拆法, 把它所有的 vertices 分成兩國, 讓所有的 edges 都橫跨兩國, 而同一國內的 vertices 彼此之間都沒有 edges, 則稱此 graph 為 bipartite graph. 例: 表達「那幾個男生愛那幾個女生」的 graph.
complete bipartite graph Km,n: 是一種特殊的 bipartite graph, 兩國各有 m, n 個 vertices, 且每一對分屬不同兩國的 vertices 之間, 都有 edge 相連. (共 mn 個 edges)
從 G = (V,E) 的 V 與 E 當中隨便取出來的子集合 V' 與 E' (當然 E' 內所有 edges 的端點必須落在 V' 之內) 所構成的圖 G' = (V',E') 稱為 G 的一個 subgraph.
若 G = (V,E), 且有一個集合 F 讓 (V,E union F) 成為 complete graph, 讓 (V, E intersect F) 成為 discrete graph, 則稱 (V,F) 為 complement of G.
若 G1 = (V1, E1), G2 = (V2, E2), 且 f 為一個從 V1 到 V2 的 one-to-one correspondence, 並且保留對應 vertices 之間的相鄰關係, 則稱 f 為一個從 G1 到 G2 的 isomorphism. 兩個 graphs 之間如果可以找到 isomorphism, 則稱它們為 isomorphic graphs.
自己到自己的 isomorphism 叫做 automorphism.
Planar Graphs

可以被 embed (嵌) 到平面上, 而所有 edges 互不交叉的圖, 叫做 planar graph.
Kuratowski' Theorem: 一個圖 G 為 non-planar graph <==> G 至少有一個 subgraph 與 K5 或 K3,3 homeomorphic.
Euler's Formula: 凡是一個 planar graph, 它的 vertices, edges, regions 的個數之間必滿足下列等式: v-e+r=2
一個 planar graph 若它沒有 loop 且至少含一個 edge, 則必滿足 3r <= 2e 且 e <= 3v-6. 所以 r 屬於 O(v) 且 e 屬於 O(v).
若 G 為一個 planar graph, 則可由 G 定義出它的一個 dual graph (對偶圖) G^d 如下: 在 G 的每個 region r (含 infinite region) 內畫一個 G^d 的 vertex 叫它 r^d; 找出每對相鄰的 regions r1 與 r2 , 及它們之間的分界 edge e, 然後把 r1 與 r2 的 dual vertices r1^d 與 r2^d 用一條 G^d 的 edge 連起來, 命名為 e^d.
Dual graph 的例子: 地圖上的國家邊界, 它的 dual graph 代表國與國的相鄰關係.