再談離散數(shù)學

1、2/21/2022 4:24 PM Discrete Math. , DeRen Chen1再談離散數(shù)學再談離散數(shù)學Reviewing in Reviewing in Discrete Mathematics Discrete Mathematics 2/21/2022 4:24 PM Discrete Math. , DeRen Chen2 Discrete Math. 離散數(shù)學離散數(shù)學 研究離散對象及其相互間關(guān)系的一門數(shù)學學科。研究離散對象及其相互間關(guān)系的一門數(shù)學學科。 研究離散結(jié)構(gòu)的數(shù)學分支。（辭海）研究離散結(jié)構(gòu)的數(shù)學分支。（辭海）離散數(shù)學的內(nèi)容離散數(shù)學的內(nèi)容：基礎：基礎概念概念 原理原

2、理方法方法 應用應用實踐實踐2/21/2022 4:24 PM Discrete Math. , DeRen Chen3基礎部分基礎部分: 邏輯邏輯(Logic) 集合集合(Sets) 算法算法(Algorithms) 數(shù)論數(shù)論(Number Theory)原理部分原理部分: 數(shù)學推理數(shù)學推理(Reasoning) 計數(shù)原理計數(shù)原理(Counting) 關(guān)系關(guān)系(Relations)應用部分應用部分: 圖圖(Graphs) 樹樹(Trees) 代數(shù)系統(tǒng)：布爾代數(shù)代數(shù)系統(tǒng)：布爾代數(shù)(Boolean Algebra)，群（群（Group）2/21/2022 4:24 PM Discrete Mat

3、h. , DeRen Chen4邏輯（邏輯（LOGIC）：命題邏輯命題邏輯 Proposition Logic命題演算命題演算 Propositional Equivalences謂詞和量詞謂詞和量詞 Predicates and Quantifiers2/21/2022 4:24 PM Discrete Math. , DeRen Chen5 （1）命題的概念：）命題的概念：定義、邏輯值、定義、邏輯值、 符號化表示符號化表示（2）從簡單命題到復合命題：）從簡單命題到復合命題： 邏輯聯(lián)接詞：運算方法、運算優(yōu)先級邏輯聯(lián)接詞：運算方法、運算優(yōu)先級（3）從命題常量到命題變量，）從命題常量到命題變量，

4、 從復合命題到命題公式：從復合命題到命題公式： 命題公式的真值描述：命題公式的真值描述：真值表真值表（4）命題公式的分類：）命題公式的分類： 永真公式、永假公式、可滿足公式永真公式、永假公式、可滿足公式 （5）命題公式的等價演算：）命題公式的等價演算：基本等價定理；兩種方法基本等價定理；兩種方法（6）命題公式的標準化描述：）命題公式的標準化描述：表達、判定、分類與應用表達、判定、分類與應用（7）從命題到命題函數(shù)：）從命題到命題函數(shù)：N元謂詞、個體、個體變量、個體域元謂詞、個體、個體變量、個體域（8）從命題公式到謂詞公式：）從命題公式到謂詞公式：存在量詞、全稱量詞；變量的分類存在量詞、全稱量詞；

5、變量的分類（9）謂詞公式的演算：）謂詞公式的演算：基本等價定理基本等價定理2/21/2022 4:24 PM Discrete Math. , DeRen Chen62/21/2022 4:24 PM Discrete Math. , DeRen Chen7p q Tp q Fp (p q) p Absorption Laws/吸收律p (p q) pp q p qp q (p q) ( q p)2/21/2022 4:24 PM Discrete Math. , DeRen Chen8判斷命題公式邏輯等價的方法：判斷命題公式邏輯等價的方法： 1、真值表、真值表 2、命題公式的演算、命題公式的

6、演算 基本等值定理（基本等價定理）；基本等值定理（基本等價定理）； 公式的代入不變性；公式的代入不變性； 等值關(guān)系的傳遞性。等值關(guān)系的傳遞性。2/21/2022 4:24 PM Discrete Math. , DeRen Chen9命題公式邏輯等價關(guān)系的應用：命題公式邏輯等價關(guān)系的應用： 1、判定是否邏輯等價；、判定是否邏輯等價； 2、判斷是否為永真公式或永假公式；、判斷是否為永真公式或永假公式； 3、命題公式的化簡、命題公式的化簡 2/21/2022 4:24 PM Discrete Math. , DeRen Chen10定理定理2 （基本量詞等值定律）（基本量詞等值定律）量詞分配律量詞

7、分配律 Vx（A(x)B(x)）VxA(x)VxB(x) x(A(x)B(x)） xA(x) xB(x)另兩種情況的思考：另兩種情況的思考：V與與， 與與量詞否定律量詞否定律2/21/2022 4:24 PM Discrete Math. , DeRen Chen11量詞擴張量詞擴張/收縮律收縮律Vx(PB(x)PVxB(x)Vx(PB(x)PVxB(x) x(PB(x)P xB(x) x(PB(x)P x B(x)這里這里A、B是任意包括個體變量是任意包括個體變量x的謂詞公式，的謂詞公式，P是不包括是不包括個體變量個體變量x的任意謂詞公式。的任意謂詞公式。2/21/2022 4:24 PM

8、Discrete Math. , DeRen Chen12 集合集合1.集合的表示集合的表示2.集合間的關(guān)系：相等、包含集合間的關(guān)系：相等、包含3.集合間的運算集合間的運算4.一些特殊的集合：空集、全集、冪集、一些特殊的集合：空集、全集、冪集、X集集5.集合的分類：集合的基集合的分類：集合的基6.函數(shù)的概念函數(shù)的概念7.函數(shù)的分類函數(shù)的分類8.函數(shù)的運算函數(shù)的運算9.一些特殊的應用函數(shù)：語言一些特殊的應用函數(shù)：語言2/21/2022 4:24 PM Discrete Math. , DeRen Chen132/21/2022 4:24 PM Discrete Math. , DeRen Che

9、n142/21/2022 4:24 PM Discrete Math. , DeRen Chen15證明兩個集合相等的方法：證明兩個集合相等的方法：1、定義方法：謂詞公式、定義方法：謂詞公式2、相等定理：互相包含、相等定理：互相包含3、集合相等運算：基本相等定理、集合相等運算：基本相等定理4、Venn 圖（文氏圖）：圖解圖（文氏圖）：圖解5、位運算、位運算2/21/2022 4:24 PM Discrete Math. , DeRen Chen16一對一，單函數(shù)，單射一對一，單函數(shù)，單射映上的，滿函數(shù)，滿射映上的，滿函數(shù)，滿射一一對應，雙射一一對應，雙射逆函數(shù)逆函數(shù)函數(shù)的復合運算，積運算函數(shù)的

10、復合運算，積運算2/21/2022 4:24 PM Discrete Math. , DeRen Chen17幾個常用的函數(shù)：幾個常用的函數(shù)：Eigenfunctionfloor functionceiling function關(guān)于集合的進一步討論（基于函數(shù)）：關(guān)于集合的進一步討論（基于函數(shù)）： Sequences string Language Countable of elements in sets2/21/2022 4:24 PM Discrete Math. , DeRen Chen18 算法（算法（Algorithm）是通過一個有限的指是通過一個有限的指令序列集合對特定問題進行求解

11、的一種計算執(zhí)令序列集合對特定問題進行求解的一種計算執(zhí)行描述。行描述。 An algorithm is a finite set of precise instructions for performing a computation or for solving a problem.2/21/2022 4:24 PM Discrete Math. , DeRen Chen19一個算法通常應具有下列特征：一個算法通常應具有下列特征：（1）輸入：一個算法具有零個或多個取自指定集合的輸入）輸入：一個算法具有零個或多個取自指定集合的輸入值；值；（2）輸出：對算法的每一次輸入，算法具有一個或多個與）輸出

12、：對算法的每一次輸入，算法具有一個或多個與輸入值接聯(lián)系的輸出值；輸入值接聯(lián)系的輸出值；（3）確定性：算法的每一個指令步驟都是明確的；）確定性：算法的每一個指令步驟都是明確的；（4）有限性：對算法的每一次輸入，算法都必須在有限步）有限性：對算法的每一次輸入，算法都必須在有限步驟（即有限時間）內(nèi)結(jié)束；驟（即有限時間）內(nèi)結(jié)束；（5）正確性：對每一次輸入，算法應產(chǎn)生出正確的輸出值；）正確性：對每一次輸入，算法應產(chǎn)生出正確的輸出值；（6）通用性：算法的執(zhí)行過程可應用于所有同類求解問題，）通用性：算法的執(zhí)行過程可應用于所有同類求解問題，而不是僅適用于特殊的輸入。而不是僅適用于特殊的輸入。2/21/2022

13、 4:24 PM Discrete Math. , DeRen Chen20Let f and g be functions from the set of R or I to the set of R. Call that f(x) is O(g(x) if there are constants C and k such that |f(x)| k. Read as “f(x) is big-oh of g(x)” O:Landau symbol關(guān)于關(guān)于C和和k 的說明：的說明： 1、 不唯一不唯一 2、是有序?qū)ψ鳛樵氐囊粋€無限集、是有序?qū)ψ鳛樵氐囊粋€無限集 3、盡可能小、盡可能小2/

14、21/2022 4:24 PM Discrete Math. , DeRen Chen21Theorem 1 If f(x)=an xn +an-1 xn-1+a 1 x1+a0 where ai R, i=0,1,nThen f(x) is O(xn)Theorem 2 If f1(x) is O(g1(x), f2(x) is O(g2(x),Then (f1 + f2 )(x) is O(max(g1(x), g2(x) )2/21/2022 4:24 PM Discrete Math. , DeRen Chen22Corollary 1 If f1(x) is O(g(x), f2(x

15、) is O(g(x),Then (f1 + f2 )(x) is O(g(x) )Theorem 3 If f1(x) is O(g1(x), f2(x) is O(g2(x),Then (f1 f2 )(x) is O(g1(x)g2(x) )2/21/2022 4:24 PM Discrete Math. , DeRen Chen23常用的算法復雜性分類：常用的算法復雜性分類： O(1): constant complexity O(log n): logarithmic complexity O(n): linear complexity O(n log n): n log n com

16、plexity linear O(nb) : polynomial complexity polynomial O(bn) : exponential complexity(b1) exponential O(n!): factorial complexity2/21/2022 4:24 PM Discrete Math. , DeRen Chen24Let f and g be functions from the set of R or I to the set of R. Call that f(x) is (g(x) if there are constants C and k suc

17、h that |f(x)| = C|g(x)|Wherever x k. Read as “f(x) is big-omega of g(x)” 2/21/2022 4:24 PM Discrete Math. , DeRen Chen25Let f and g be functions from the set of R or I to the set of R. Call that f(x) is (g(x) if f(x) is O(g(x) and f(x) is (g(x)Read as “f(x) is big-theta of g(x)” “f(x) is of order g(

18、x)”2/21/2022 4:24 PM Discrete Math. , DeRen Chen26數(shù)論數(shù)論 （Number Theory）1、算術(shù)基本定理、算術(shù)基本定理2、同余關(guān)系、同余關(guān)系3、密碼學基礎、密碼學基礎定義定義 設設m是一個正整數(shù)，對任意兩個整數(shù)是一個正整數(shù)，對任意兩個整數(shù)a、b，若，若a-b能被能被m整除，則稱整除，則稱a與與b是是（模（模m）同余的）同余的，或，或（模（模m）合）合同的同的/congruent by modulo m ，記為，記為 a b ( mod m) 在在m確定的情況下，簡記為確定的情況下，簡記為 a b 。2/21/2022 4:24 PM Disc

19、rete Math. , DeRen Chen271、整數(shù)的因子、公因子、整數(shù)的因子、公因子、GCD -EUCLID算法、算法、 GCD的線性組合的線性組合2、質(zhì)數(shù)、質(zhì)因子、兩兩互質(zhì)、質(zhì)數(shù)、質(zhì)因子、兩兩互質(zhì) -整數(shù)分解整數(shù)分解3、同余關(guān)系、線性同余、中國同余定理、同余關(guān)系、線性同余、中國同余定理4、費爾瑪小定理、費爾瑪小定理、RSA算法算法2/21/2022 4:24 PM Discrete Math. , DeRen Chen28原理部分原理部分: 數(shù)學推理數(shù)學推理(Reasoning) 3.1 推理與證明方法推理與證明方法 3.2 數(shù)學歸納方法數(shù)學歸納方法 3.3 遞推方法遞推方法 計數(shù)原

20、理計數(shù)原理(Counting) 關(guān)系關(guān)系(Relations)2/21/2022 4:24 PM Discrete Math. , DeRen Chen29蘊涵演算蘊涵演算/logical implying operation 對于任意的公式對于任意的公式P和和Q，如果，如果P Q 為為T，則稱，則稱P蘊涵蘊涵Q， 記為記為P Q 或或P/Q蘊涵演算的推廣表示：蘊涵演算的推廣表示： P1、 P2 、 、Pn Q 前提組前提組/hypotheses 結(jié)論結(jié)論/conclusion2/21/2022 4:24 PM Discrete Math. , DeRen Chen30Rule of Infe

21、rence NameP P QAddition/析取附加式析取附加式P Q P Simplification/合取化簡式合取化簡式P、Q P Q Conjunction/并發(fā)式并發(fā)式P、 P Q QModus ponens/分離式分離式 Q、 P Q PModus tollens/拒取式拒取式 p、P Q QDisjunctive syllogism/析取三段式析取三段式P Q、 Q R P R Hypothetical syllogism/假言三段式假言三段式2/21/2022 4:24 PM Discrete Math. , DeRen Chen31定理證明方法：定理證明方法：1、直接證明

22、、直接證明/direct proof: p Q 2、間接證明、間接證明/indirect proof : p Q Q P3、空證明、空證明/vacuous proof: p Q 其中其中 P為為 F4、平凡證明、平凡證明/trivial proof： p Q 其中其中 Q 為為T2/21/2022 4:24 PM Discrete Math. , DeRen Chen32定理證明方法：定理證明方法：5、反證明、反證明/proof of contradiction： P P S S6、分例證明、分例證明/proof of cases： P1 P2 Pn Q （P1 Q） （P2 Q） （Pn Q

23、）7、存在證明、存在證明/existence proof： x P(x) constructive, nonconstructive8、歸納證明、歸納證明/induction proof ： x P(x) 2/21/2022 4:24 PM Discrete Math. , DeRen Chen33（1）0N；（2）對每一個）對每一個nN，唯一定義了一個自然數(shù)，唯一定義了一個自然數(shù)n，n 稱為稱為n的后鄰；的后鄰；（3）不同的自然數(shù)，其后鄰也不同；）不同的自然數(shù)，其后鄰也不同；（4）沒有一個自然數(shù)的后鄰是）沒有一個自然數(shù)的后鄰是0；（5）如果有一個子集）如果有一個子集M N滿足：滿足： 0M；

24、 nM時必時必n M, 則則M = N自然數(shù)全體自然數(shù)全體N通過皮亞諾公理的五條公理組成。通過皮亞諾公理的五條公理組成。 這些公理缺一不可，其中性質(zhì)（這些公理缺一不可，其中性質(zhì)（5）稱為歸納公理，并指）稱為歸納公理，并指出了自然數(shù)是滿足公理（出了自然數(shù)是滿足公理（1）（4）的最小集合。）的最小集合。 2/21/2022 4:24 PM Discrete Math. , DeRen Chen34數(shù)學歸納法的一般公式表示：數(shù)學歸納法的一般公式表示：P(k) m(m k P(m) P(m+1) n P(n) 1、歸納基礎：、歸納基礎： P(k) 2、歸納步驟：、歸納步驟： m (m k P(m) P

25、(m+1)第二數(shù)學歸納法：第二數(shù)學歸納法：P(n0) k ( k n0 P(n0) P(n0+1) P(k) P(k+1) n P(n) 1、歸納基礎：、歸納基礎： P(n0) 2、歸納步驟：、歸納步驟： k ( k n0 P(n0) P(n0+1) P(k) P(k+1) 2/21/2022 4:24 PM Discrete Math. , DeRen Chen35有限數(shù)學歸納法：對于有限數(shù)學歸納法：對于 n0 n nk 的的 P(n)有限數(shù)學歸納法的前推公式表示：有限數(shù)學歸納法的前推公式表示：P(n0) n(n0 n nk-1 P(n) P(n+1) n (n0 n nk P(n) 1、歸

26、納基礎：、歸納基礎： P(n0) 2、歸納步驟：、歸納步驟： n(n0 n nk-1 P(n) P(n+1) 有限數(shù)學歸納法：對于有限數(shù)學歸納法：對于 n0 n nk 的的 P(n)有限數(shù)學歸納法的后推公式表示：有限數(shù)學歸納法的后推公式表示：P(nk ) n(n0 +1 n nk P(n) P(n-1) n (n0 n nk P(n) 1、歸納基礎：、歸納基礎： P(nk ) 2、歸納步驟：、歸納步驟： n(n0 +1 n nk P(n) P(n-1)2/21/2022 4:24 PM Discrete Math. , DeRen Chen36定義定義1如果一個對象部分地由自己所組成，如果一個

27、對象部分地由自己所組成，或 者 按 它 自 己 定 義 ， 則 稱 為 是或 者 按 它 自 己 定 義 ， 則 稱 為 是 遞 歸遞 歸 的的（Recursion）。）。f的定義域：非負整數(shù)集的定義域：非負整數(shù)集 1、遞歸基礎：、遞歸基礎： f(0) 2、遞歸步驟：、遞歸步驟： f(n)=g(f(k), k=0菲波那契數(shù)菲波那契數(shù)/FibonacciF(0) = 0，F(xiàn)(1) = 1F(n) = F (n1) + F (n2)n12/21/2022 4:24 PM Discrete Math. , DeRen Chen374、計數(shù)原理、計數(shù)原理/Counting 4.1 基本計數(shù)原理基本計數(shù)

28、原理:加法原理和乘法原理加法原理和乘法原理 The Basic of Counting 4.2 包含與排斥原理包含與排斥原理:有限集的基的運算有限集的基的運算 The Inclusion-Exclusion Principle 4.3 鴿洞原理鴿洞原理:有限集的基的比較有限集的基的比較 The Pigeonhole Principle4.4 排列與組合排列與組合:排列、組合、二項式排列、組合、二項式 Permutations and Combinations4.5 排列與組合的生成：排列與組合的生成：排列生成、組合生成排列生成、組合生成 Generating Permutations and

29、Combinations2/21/2022 4:24 PM Discrete Math. , DeRen Chen38求和規(guī)則求和規(guī)則/The Sum RuleIf a first task can be done in n ways and a second task in m ways, and if there these tasks cannot be done at the same time, then there are n+m ways to be either task.|A1 A2| = |A1| + |A2| 其中其中A1 A2 = 求和規(guī)則的推廣求和規(guī)則的推廣|A1 A

30、2 An | = |A1| + |A2| + + |An| 其中其中A i A j = i j, i,j =1,2,n2/21/2022 4:24 PM Discrete Math. , DeRen Chen39求積規(guī)則求積規(guī)則/The Product RuleSuppose that a procedure can be broken down into two tasks. If there are n ways to do the first task and m ways to do the second task after the first task has been done,

31、 then there are nm ways to do the procedure. |A1 A2 | = |A1| |A2|求積規(guī)則的推廣求積規(guī)則的推廣|A1 A2 An | = |A1| |A2| |An| 2/21/2022 4:24 PM Discrete Math. , DeRen Chen40對任意有限集對任意有限集A1、A2，成立成立 |A1 A2| = |A1| + |A2| - |A1 A2| 推廣：推廣：|A1 A2 An | =2/21/2022 4:24 PM Discrete Math. , DeRen Chen41The Pigeonhole Principle

32、If k+1 or more objects are placed into k boxes, then there is at least one box containing two or more of the objects.The Generalized Pigeonhole PrincipleIf N objects are placed into k boxes, then there is at least one box containing at least N/k objects.2/21/2022 4:24 PM Discrete Math. , DeRen Chen4

33、24.4 排列與組合排列與組合/Permutations and Combinations(1) 排列：排列：r-排列、全排列、排列、全排列、 r-可重排列、可重排列、r-限重排列、限重排列、r-循環(huán)排列循環(huán)排列(2) 組合：組合：r-組合、組合、 r-可重組合可重組合(3) 二項式定理與二項式系數(shù)：二項式定理與二項式系數(shù)：4.5 排列與組合的生成排列與組合的生成 Generating Permutations and Combinations2/21/2022 4:24 PM Discrete Math. , DeRen Chen43定義定義1：n個元素的集合個元素的集合A中任意選擇中任意選

34、擇r個（個（r n）進行排列稱為進行排列稱為A的一個的一個r-排列排列/r-Permutation定理定理1： n個元素的集合個元素的集合A的的r-排列數(shù)為排列數(shù)為 n(n-1)(n-2)(n-r+1) =P(n,r)特別地，當特別地，當r = n 時，記時，記P(n,r)=n! 稱為稱為A的一個的一個全排列全排列2/21/2022 4:24 PM Discrete Math. , DeRen Chen44排列的函數(shù)表示：排列的函數(shù)表示： |A| = n，B=1,2,r，F(xiàn):BA（1）F是一個單射是一個單射 A的一個的一個r-排列排列（2）B到到A的所有的所有單射總數(shù)單射總數(shù) P(n,r)排列

35、的球盒模型表示：排列的球盒模型表示： |A| = n n個盒子個盒子 B=1,2,r r個不同的球個不同的球F:BA且是單射且是單射 每個盒子最多放一個球每個盒子最多放一個球 A的一個的一個r-排列排列B到到A的所有的所有單射總數(shù)單射總數(shù) 球放入盒子的放法總數(shù)球放入盒子的放法總數(shù) P(n,r)2/21/2022 4:24 PM Discrete Math. , DeRen Chen45定義定義2：n個元素的集合個元素的集合A中任意選擇中任意選擇r個（個（r n）稱為）稱為A的一個的一個r-組合組合/r-Combination定理定理2： n個元素的集合個元素的集合A的的r-組合數(shù)為組合數(shù)為 n

36、(n-1)(n-2)(n-r+1)/r! 記為記為C(n,r)組合的球盒模型表示：組合的球盒模型表示： B=0，1 兩個盒子兩個盒子 A n個不同的球個不同的球F:BA且使得且使得A中的中的r個元素的象為個元素的象為1 指定一個盒子恰好放指定一個盒子恰好放r個球個球 A的一個的一個r-組合組合滿足條件的滿足條件的F總數(shù)總數(shù) = C(n,r) = 滿足條件的球的放法總數(shù)滿足條件的球的放法總數(shù)2/21/2022 4:24 PM Discrete Math. , DeRen Chen46定理定理6（Binomial Theorem/二項式定理）：二項式定理）： 對任意正整數(shù)對任意正整數(shù)n和變量和變量

37、x、y （x+y）n= nj=0 C（n，j）xn-j yj2/21/2022 4:24 PM Discrete Math. , DeRen Chen47定義定義3 n個不同元素的集合個不同元素的集合A，每個元素可重復，每個元素可重復選取，則選取，則A中任意選擇中任意選擇r個（個（r n）進行排列稱為）進行排列稱為A的一個的一個r-可重排列可重排列/r-Permutation with repetition。定理定理7 n個不同元素的集合個不同元素的集合A，每個元素可重復，每個元素可重復選取，則選取，則A的的r-可重排列總數(shù)為可重排列總數(shù)為nr。 2/21/2022 4:24 PM Discr

38、ete Math. , DeRen Chen48定義定義6 n個不同元素的集合個不同元素的集合A，每個元素可重復，每個元素可重復選取，則選取，則A中任意選擇中任意選擇r個（個（r n）的方式稱為）的方式稱為A的的一個一個r-可重組合可重組合/r-Combination with repetition。定理定理10 n個不同元素的集合個不同元素的集合A，每個元素可重，每個元素可重復選取，則復選取，則A的的r-可重組合總數(shù)為可重組合總數(shù)為 C（n-1+r，r） 2/21/2022 4:24 PM Discrete Math. , DeRen Chen49Relations 關(guān)系關(guān)系（1）二元關(guān)系的

39、概念：集合、關(guān)系、函數(shù)）二元關(guān)系的概念：集合、關(guān)系、函數(shù) 多元關(guān)系多元關(guān)系（2）二元關(guān)系的表示）二元關(guān)系的表示:集合、圖形、矩陣集合、圖形、矩陣（3）二元關(guān)系的性質(zhì)：分類）二元關(guān)系的性質(zhì)：分類（4）二元關(guān)系的運算：集合運算、函數(shù)運算、閉包運算）二元關(guān)系的運算：集合運算、函數(shù)運算、閉包運算2/21/2022 4:24 PM Discrete Math. , DeRen Chen50（5）等價關(guān)系的概念、等價關(guān)系與劃分等價關(guān)系的概念、等價關(guān)系與劃分（6）半序關(guān)系與半序集、全序關(guān)系與全序集半序關(guān)系與半序集、全序關(guān)系與全序集 半序集中的極小半序集中的極小/大元素、最小大元素、最小/大元素、大元素、 上

40、上/下界、上下界、上/下確界下確界 良序關(guān)系與良序集、拓撲排序良序關(guān)系與良序集、拓撲排序2/21/2022 4:24 PM Discrete Math. , DeRen Chen51 7、圖、圖/Graph7.1 圖的概念圖的概念/Introduction of Graph7.2 圖的術(shù)語圖的術(shù)語/Graph Terminology7.3 圖的表示與同構(gòu)圖的表示與同構(gòu)/ Representing Graph and Graph Isomorphism 表示表示:集合、表、矩陣集合、表、矩陣 圖的轉(zhuǎn)換、圖的包含、圖的轉(zhuǎn)換、圖的包含、 圖的運算、圖的同構(gòu)圖的運算、圖的同構(gòu)7.4 連通性連通性/Co

41、nnectivity2/21/2022 4:24 PM Discrete Math. , DeRen Chen52一些特殊的簡單無向圖：一些特殊的簡單無向圖： （1）Complete Graphs/完全圖完全圖Kn （2）Cycles/環(huán)圖環(huán)圖Cn （3）Wheels/輪圖輪圖Wn （4）n-Cubes/n-立方圖立方圖Qn （5）Bipartite Graphs/二分圖二分圖Kn,m2/21/2022 4:24 PM Discrete Math. , DeRen Chen53一些特殊的其他圖：一些特殊的其他圖： （1）有向完全圖）有向完全圖 （2）零圖）零圖 （3）平凡圖）平凡圖 （4）正則圖：若圖（，）中每正則圖：若圖（，）中每個頂點的次均為個頂點的次均為n n，稱此圖是，稱此圖是n-n-正則的正則的/n-/n-regularregular。2/21/2022 4:24 PM Discrete Math. , DeRen Chen547.5 歐拉道路與哈密爾頓道路歐拉道路與哈密爾頓道路/ Euler and Hamilton Paths7.6 最短道路問題最短道路問題/Shortest Path Problem7.7 平面圖平面圖/Planar Graphs 平面圖的概念：無向、簡單、有限、非交叉邊平面圖的概念：無向、簡單、有限、非交叉邊/區(qū)域區(qū)域 平