复旦大学：《离散数学》PPT教学课件（赵一鸣）28/28

I Introduction to Set Theory ◆1. Sets and subsets Representation of set: o Listing elements Set builder notion, Recursive definition ◆∈,c,C ◆P(A) 2. Operations on Sets o Operations and their properties ◆A=?B ◆AB, and bca ◆ Properties o Theorems, examples, and exercises

 ⅠIntroduction to Set Theory  1. Sets and Subsets  Representation of set:  Listing elements, Set builder notion, Recursive definition  , ,   P(A)  2. Operations on Sets  Operations and their Properties  A=?B  AB, and B A  Properties  Theorems, examples, and exercises

+3. Relations and Properties of relations ◆ reflexive, irreflexive o symmetric, asymmetric ,antisymmetric ◆ Transitive Closures of relations ◆r(R),s(R),t(R)=? Theorems, examples, and exercises 44. Operations on relations Inverse relation, Composition o Theorems, examples, and exercises

 3. Relations and Properties of relations  reflexive ,irreflexive  symmetric , asymmetric ,antisymmetric  Transitive  Closures of Relations  r(R),s(R),t(R)=?  Theorems, examples, and exercises  4. Operations on Relations  Inverse relation, Composition  Theorems, examples, and exercises

紫◆5. Equivalence relations o Equivalence relations ◆ equivalence class .6.Partial order relations and Hasse Diagrams Extremal elements of partially ordered sets: maximal element. minimal element o greatest element, least element o upper bound, lower bound least upper bound, greatest lower bound o Theorems examples. and exercises

 5. Equivalence Relations  Equivalence Relations  equivalence class  6.Partial order relations and Hasse Diagrams  Extremal elements of partially ordered sets:  maximal element, minimal element  greatest element, least element  upper bound, lower bound  least upper bound, greatest lower bound  Theorems, examples, and exercises

◆7. Functions ◆ one to one,onto, o one-to-one correspondence 4 Composite functions and Inverse functions ◆ Cardinality,Np o Theorems, examples, and exercises

 7.Functions  one to one, onto,  one-to-one correspondence  Composite functions and Inverse functions Cardinality, 0 .  Theorems, examples, and exercises

tII Combinatorics 1. Pigeonhole principle Pigeon and pigeonholes example, exercise

II Combinatorics 1. Pigeonhole principle  Pigeon and pigeonholes  example，exercise

Permutations and combinations Permutations of sets combinations of sets circular permutation Permutations and Combinations of multisets Formulae o inclusion-exclusion principle generating functions integral solutions of the equation ◆ example, exercise

2. Permutations and Combinations  Permutations of sets, Combinations of sets  circular permutation  Permutations and Combinations of multisets  Formulae  inclusion-exclusion principle  generating functions  integral solutions of the equation  example，exercise

Applications of Inclusion -Exclusion principle theorem 3.15, theorem 3. 16,example, exercise Applications generating functions and Exponential generating functions e=1+x+x2/2!+.+x"/n!+…; x+x2/2!++xm/n!+,=ex-1 ex=1-x+x2/2!+…+(-1)"x"/n!+……; 1+x2+…+x2n(2n)+…=(ex+e)/2; x+x3/3!+…+x2am+1(2n+1)+…,=(ex-e-)2 +3. recurrence relation o Using Characteristic roots to solve recurrence relations USing Generating functions to solve recurrence relations ◆ example, exercise

 Applications of Inclusion-Exclusion principle  theorem 3.15,theorem 3.16,example,exercise  Applications generating functions and Exponential generating functions  e x=1+x+x2 /2!+…+xn /n!+…;  x+x2 /2!+…+xn /n!+…=ex -1;  e -x=1-x+x2 /2!+…+(-1)nx n /n!+…;  1+x2 /2!+…+x2n/(2n)!+…=(ex+e-x )/2;  x+x3 /3!+…+x2n+1/(2n+1)!+…=(ex -e -x )/2;  3. recurrence relation  Using Characteristic roots to solve recurrence relations  Using Generating functions to solve recurrence relations  example，exercise

YIlI Graphs 1. Graph terminology The degree of a vertex, 8(G),A(G), Theorem 5.1 5.2 k-regular, spanning subgraph, induced subgraph by v∈V the complement of a graph g, connected, connected components strongly connected, connected directed weakly connected

III Graphs 1. Graph terminology  The degree of a vertex，(G),  (G), Theorem 5.1 5.2  k-regular, spanning subgraph, induced subgraph by V'V  the complement of a graph G,  connected, connected components  strongly connected, connected directed weakly connected

2. connected. Euler and hamilton paths e Prove g is connected (1)there is a path from any vertex to any other vertex .(2 )Suppose G is disconnected +1) connected components(k>1) 2There exist u, v such that is no path between uv o Shortest-path problem

2. connected, Euler and Hamilton paths  Prove: G is connected  (1)there is a path from any vertex to any other vertex  (2)Suppose G is disconnected  1) k connected components(k>1)  2)There exist u,v such that is no path between u,v  Shortest-path problem

Prove that the complement of a disconnected graph is connected. Let g be a simple graph with n vertices. Show that ifo(G)>n/2-1, then g is connected t Show that a simple graph g with an vertices is connected if it has more than (n-1)(n-2)/2 edges. TheoremS, examples, and exercises

 Prove that the complement of a disconnected graph is connected.  Let G be a simple graph with n vertices. Show that ifδ(G) >[n/2]-1, then G is connected.  Show that a simple graph G with an vertices is connected if it has more than (n-1)(n-2)/2 edges.  Theorems, examples, and exercises