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 AB, 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