advertisement

期中测验时间： 11月4日 课件 集合，关系，函数，基数,组合数学 Ⅰ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 Or Properties 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 Relation and Partial order relations Equivalence Relation equivalence class 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 6.Everywhere Functions one to one, onto, one-to-one correspondence Composite functions and Inverse functions Cardinality, 0. Theorems, examples, and exercises II Combinatorics 1. Pigeonhole principle Pigeon and pigeonholes 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 Applications of Inclusion-Exclusion principle example,exercise Applications generating functions and Exponential generating functions ex=1+x+x2/2!+…+xn/n!+…; x+x2/2!+…+xn/n!+…=ex-1; e-x=1-x+x2/2!+…+(-1)nxn/n!+…; 1+x2/2!+…+x2n/(2n)!+…=(ex+e-x)/2; x+x3/3!+…+x2n+1/(2n+1)!+…=(ex-e-x)/2; examples, and exercises 3. recurrence relation Using Characteristic roots to solve recurrence relations Using Generating functions to solve recurrence relations examples, and exercises Chapter 5 Graphs the puzzle of the seven bridge in the Königsberg, on the Pregel Kirchhoff Cayler CnH2n+1 The four colour problem四色问题 Hamiltonian circuits 1920s,König: finite and infinite graphs OS,Compiler,AI, Network 5.1 Introduction to Graphs 5.1.1 Graph terminology Relation: digraph Definition 1 : Let V is not empty set. A directed graph, or digraph, is an ordered pair of sets (V,E) such that E is a subset of the set of ordered pairs of V. We denote by G(V,E) the digraph. The elements of V are called vertices or simply "points", and V is called the set of vertices. Similarly, elements of E are called "edge", and E is called the set of edges. Edge (a,b) a: initial vertex， b:terminal vertex edges (a,b) incident with the vertices a and b。 (c,c),(f,f) loop g: isolated vertex。 G=(V,E),V={a,b,c,d,e,f,g}, E={(a,b),(a,c),(b,c),(c,a),(c,c),(c,e),(d,a),( d,c),(f,e), (f,f)}, Definition 2 ： Let (a,b) be edge in G. The vertices a and b are called endvertices of edges; a and b are called adjacent in G; the vertex a is called initial vertex of edge (a,b), and the vertex b is called terminal vertex of this edge. The edge (a,b) is called incident with the vertices a and b. The edge (a,a) is called loop。The vertex is called isolated vertex if a vertex is not adjacent to any vertex. g is an isolated vertex, (c,c) ,(f,f) are loop. a and b are adjacent; c and d are adjacent; Definition 3: Let V is not empty set. An undirected graph is an ordered pair of sets (V,E) such that E is a sub-multiset of the multiset of unordered pairs of V. We denote by G(V,E) the graph. The elements of V are called vertices or simply "points", and V is called the set of vertices. Similarly, elements of E are called "edge", and E is called the set of edges. V={v1,v2,v3,v4,v5,v6}，E={{v1,v2},{v1,v5,}，{v2,v2}, {v2,v3},{v2,v4},{v2,v5},{v2,v5},{v3,v4},{v4,v5}}， edges {v1,v2} incidents with the vertices v1 and v2 loop ; isolated vertex edge {v2,v5} multiple edge。 4 ： These edges are called multiple edges if they incident with the same two vertices. The graph is called multigraph. The graph is called a simple graph, if any two vertices in the graph, may connect at most one edge (i.e., one edge or no edge) and the graph has no loop. The complete graph on n vertices, denoted by Kn, is the simple graph that contains exactly one edge between each pair of distinct vertices. Definition undirected graph: graph finite graph finite digraph Definition 5：The degree of a vertex v in an undirected graph is the number of edges incident with it, except that a loop at a vertex contributes twice to the degree of that vertex. The degree of the vertex v is denoted by d(v). A vertex is pendent if only if it has degree one. The minimum degree of the vertices of a graph G is denoted by (G)(=minvV{d(v)}) and the maximum degree by (G)(=maxvV{d(v)} b=a,{a,a}, Theorem 5.1(the handshaking theorem): Let G(V,E) be an undirected graph with e edge. n Then: d (vi ) 2e i 1 Theorem 5.2: An undirected graph has an even number of vertices of odd degree. Definition 6：In a directed graph the outdegree of a vertex v by d+(v) is the number of edges with v as their initial vertex. The in-degree of a vertex v by d-(v), is the number of edges with v as their terminal vertex. Note that a loop at a vertex contributes 1 to both the out-degree and the in-degree of this vertex. The degree of the vertex v is denoted by d(v). Theorem 5.3: Let G(V,E) be an directed graph. Then d ( v ) d (v) | E | vV vV aD, bB,cA,dE; (a,b)(D,B), (a,c)(D,A),…， isomorphism Definition 7：The directed graphs G(V,E) and G'(V',E') be isomorphic if there is a one to one and onto everywhere function f from V to V' with the property that (a, b) is an edge of G if only if (f(a),f(b)) is an edge of G'. We denote by GG'. The undirected graph G(V,E) and G'(V',E') be isomorphic if there is a one to one and onto everywhere function f from V to V' with the property that {a, b} is an edge of G if only if {f(a),f(b)} is a edge of G'. We denote by GG'. Petersen 3-regular The graph is called k-regular if every vertex of G has degree k. Definition 8: Graphs that have a number assigned to each edge or each vertex are called weighted graphs weighted digraphs Definition 9: The graph G'(V',E') is called a subgraph of G(V,E) If V'V and E'E. If V'=V, then G'(V',E') is said to be a spanning subgraph. Definition 10: If G'(V',E') contains all edges of G that join two vertices in V' then G' is called the induced subgraph by V'V and is denoted by G(V'). induced subgraph by {v1,v2,v4,v5} Next: Paths and Circuits, Connectivity,8.1 P306(Sixth) OR P291(Fifth) Exercise P135 27,28; P310 9,10(Sixth); OR P123 27,28; P295 9,10(Fifth)