This chapter shows you how to apply your query formulation skills to building applications with views. This chapter also emphasizes views as the foundation for building database applications. Before discussing the link between views and database applications, essential background is provided. | (CSC 102) Lecture 31 Discrete Structures Graphs and Trees Previous Lecture Euler Circuits Finding an Euler Circuit Euler Trails Finding an Euler Trail Hamiltonian Circuits A Traveling Salesman Problem Today’s Lecture Matrices and Graphs Matrices and Directed Graphs Matrices and undirected Graphs Matrices and Connected Components Trees Characterizing Trees Rooted Trees Matrices and Graphs How can graphs be represented inside a computer? It happens that all the information needed to specify a graph can be conveyed by a structure called a matrix, and matrices are easy to represent inside computers. Matrices and Graphs The entry ai j in the ith row and j th column of A is called the ijth entry of A. An m × n matrix is said to have size m × n. If A and B are matrices, then A = B if, and only if, A and B have the same size and the corresponding entries of A and B are all equal; that is, ai j = bi j for all i = 1, 2, . . . ,m and j = 1, 2 . . . , n. A matrix for which the numbers of rows and columns are equal is called a square matrix. If A is a square matrix of size n × n, then the main diagonal of A consists of all the entries a11, a22, . . . , ann Matrices and Graphs Matrices and Directed Graphs Example The two directed graphs shown below differ only in the ordering of their vertices. Find their adjacency matrices. The Adjacency Matrix of a Graph Since both graphs have three vertices, both adjacency matrices are 3 × 3 matrices. For (a), all entries in the first row are 0 since there are no arrows from v1 to any other vertex. For (b), the first two entries in the first row are 1 and the third entry is 0 since from v1 there are single arrows to v1 and to v2 and no arrows to v3. Continuing the analysis in this way, you obtain the following two adjacency matrices. Obtaining a Directed Graph from a Matrix Obtaining a Directed Graph from a Matrix Matrices and Undirected Graphs Matrices and Undirected Graphs Solution Matrix is symmetric. Matrices and Connected Components . | (CSC 102) Lecture 31 Discrete Structures Graphs and Trees Previous Lecture Euler Circuits Finding an Euler Circuit Euler Trails Finding an Euler Trail Hamiltonian Circuits A Traveling Salesman Problem Today’s Lecture Matrices and Graphs Matrices and Directed Graphs Matrices and undirected Graphs Matrices and Connected Components Trees Characterizing Trees Rooted Trees Matrices and Graphs How can graphs be represented inside a computer? It happens that all the information needed to specify a graph can be conveyed by a structure called a matrix, and matrices are easy to represent inside computers. Matrices and Graphs The entry ai j in the ith row and j th column of A is called the ijth entry of A. An m × n matrix is said to have size m × n. If A and B are matrices, then A = B if, and only if, A and B have the same size and the corresponding entries of A and B are all equal; that is, ai j = bi j for all i = 1, 2, . . . ,m and j = 1, 2 . . . , n. A matrix for which the numbers of rows and
