In this chapter, the following content will be discussed: entity relationship diagrams, data modeling practice, schema conversion, and normalization. This chapter extends your database design skills by explaining the process to achieve an efficient implementation of your table design. | (CSC 102) Lecture 28 Discrete Structures Graphs Previous Lecture Counting Elements of Disjoint Sets Counting the Number of Integers Relation between Permutations and Combinations Probability Axioms of Probability Expected Value Today’s Lecture Graphs Directed Graphs Simple Graphs Complete Graphs Complete Bipartite Graphs Subgraphs The Concept of Degree Graphs Imagine an organization that wants to set up teams of three to work on some projects. In order to maximize the number of people on each team who had previous experience working together successfully, the director asked the members to provide names of their past partners. This information is displayed below both in a table and in a diagram. Cont Drawings such as those shown previously are illustrations of a structure known as a graph. The dots are called vertices (plural of vertex) and the line segments joining vertices are called edges. As you can see from the drawing, it is possible for two edges to cross at a point that is not a vertex. Cont In general, a graph consists of a set of vertices and a set of edges connecting various pairs of vertices. The edges may be straight or curved and should either connect one vertex to another or a vertex to itself, as shown below. Cont In this drawing, the vertices have been labeled with v’s and the edges with e’s. When an edge connects a vertex to itself (as e5 does), it is called a loop. When two edges connect the same pair of vertices (as e2 and e3 do), they are said to be parallel. It is quite possible for a vertex to be unconnected by an edge to any other vertex in the graph (as v5 is), and in that case the vertex is said to be isolated. Cont Definition: Graphs A graph G consists of two finite sets: a nonempty set V(G) of vertices and a set E(G) of edges, where each edge is associated with a set consisting of either one or two vertices called its endpoints. The correspondence from edges to endpoints is called the edge-endpoint function. An edge with just one . | (CSC 102) Lecture 28 Discrete Structures Graphs Previous Lecture Counting Elements of Disjoint Sets Counting the Number of Integers Relation between Permutations and Combinations Probability Axioms of Probability Expected Value Today’s Lecture Graphs Directed Graphs Simple Graphs Complete Graphs Complete Bipartite Graphs Subgraphs The Concept of Degree Graphs Imagine an organization that wants to set up teams of three to work on some projects. In order to maximize the number of people on each team who had previous experience working together successfully, the director asked the members to provide names of their past partners. This information is displayed below both in a table and in a diagram. Cont Drawings such as those shown previously are illustrations of a structure known as a graph. The dots are called vertices (plural of vertex) and the line segments joining vertices are called edges. As you can see from the drawing, it is possible for two edges to cross at a point that is not
