《期中测验时间11月4日集合关系函数基数组合数学PPT课件》由会员分享，可在线阅读，更多相关《期中测验时间11月4日集合关系函数基数组合数学PPT课件（30页珍藏版）》请在金锄头文库上搜索。
1、v期中测验时间：期中测验时间： v11月月4日日v课件课件 集合，关系，函数，基数集合，关系，函数，基数,组合数学组合数学vIntroduction to Set Theory v1. Sets and Subsets vRepresentation of set: vListing elements, Set builder notion, Recursive definition v , , vP(A)v2. Operations on Sets vOperations and their PropertiesvA=?BvA B, and B AvOr PropertiesvTheorem
2、s, examples, and exercisesv3. Relations and Properties of relationsvreflexive ,irreflexivevsymmetric , asymmetric ,antisymmetricvTransitivevClosures of Relationsvr(R),s(R),t(R)=?vTheorems, examples, and exercisesv4. Operations on RelationsvInverse relation, CompositionvTheorems, examples, and exerci
3、sesv5. Equivalence Relation and Partial order relations vEquivalence Relationvequivalence classvPartial order relations and Hasse DiagramsvExtremal elements of partially ordered sets:vmaximal element, minimal element vgreatest element, least element vupper bound, lower boundvleast upper bound, great
4、est lower boundvTheorems, examples, and exercises v6.Everywhere Functionsvone to one, onto, one-to-one correspondencevComposite functions and Inverse functionsvCardinality, 0. vTheorems, examples, and exercisesvII Combinatoricsv1. Pigeonhole principle vPigeon and pigeonholesvexample，exercisev2. Perm
5、utations and CombinationsvPermutations of sets, Combinations of setsvcircular permutationvPermutations and Combinations of multisets vFormulaevinclusion-exclusion principle vgenerating functions vintegral solutions of the equation vApplications of Inclusion-Exclusion principlevexample,exercisevAppli
6、cations generating functions and Exponential generating functionsvex=1+x+x2/2!+xn/n!+;vx+x2/2!+xn/n!+=ex-1;ve-x=1-x+x2/2!+(-1)nxn/n!+;v1+x2/2!+x2n/(2n)!+=(ex+e-x)/2;vx+x3/3!+x2n+1/(2n+1)!+=(ex-e-x)/2;vexamples, and exercisesv3. recurrence relation vUsing Characteristic roots to solve recurrence rela
7、tions vUsing Generating functions to solve recurrence relationsvexamples, and exercisesChapter 5 Graphs vthe puzzle of the seven bridge in the Knigsberg,von the Pregel vKirchhoffvCayler CnH2n+1vThe four colour problem四色问题四色问题vHamiltonian circuitsv1920s,Knig: finite and infinite graphsvOS,Compiler,AI
8、, Network 5.1 Introduction to Graphs v5.1.1 Graph terminology vRelation: digraph vDefinition 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 cal
9、led 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.vG=(V,E),V=a,b,c,d,e,f,g, vE=(a,b),(a,c),(b,c),(c,a),(c,c),(c,e),(d,a),(d,c),(f,e), (f,f),Edge (a,b)a: initial vertex，b:terminal vertexedges (a,b) incident w
10、ith the vertices a and b。(c,c),(f,f) loopg: isolated vertex。 vDefinition 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
11、 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; vDefinition 3: Let V is not empty set. A
12、n 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 ca
13、lled 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 v2loop ; isolated vertex edge v2,v5 multiple edge。vDefinition 4： These edges are called multiple edges if they incident with the same two vertices. The g
14、raph 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 o
15、f distinct vertices.vundirected graph: graphvfinite graphvfinite digraphvDefinition 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).
16、 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)(=minv Vd(v) and the maximum degree by (G)(=maxv Vd(v)vb=a,a,a,vTheorem 5.2: An undirected graph has an even number of vertices of odd degree.vDefinition 6：In a directed graph the out-
17、degree 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 ver
18、tex v is denoted by d(v). vTheorem 5.3: Let G(V,E) be an directed graph. ThenaD, bB,cA,dE; (a,b)(D,B), (a,c)(D,A),，isomorphism vDefinition 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 edg
19、e of G if only if (f(a),f(b) is an edge of G. We denote by G G. 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 G G.vPetersen3-regula
20、r The graph is called k-regular if every vertex of G has degree k.vDefinition 8: Graphs that have a number assigned to each edge or each vertex are called weighted graphsvweighted digraphs vDefinition 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 b
21、e a spanning subgraph.vDefinition 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).vinduced subgraph by v1,v2,v4,v5vNext: Paths and Circuits, Connectivity,8.1 P306(Sixth) OR P291(Fifth) vExercise P135 27,28; P310 9,10(Sixth);vOR P123 27,28; P295 9,10(Fifth)
