TAILIEUCHUNG - Lecture Discrete structures: Chapter 32 - Amer Rasheed

In this chapter, the following content will be discussed: This chapter augments your database application development skills with stored procedures and triggers. Stored procedures provide reuse of common code, while triggers provide rule processing for common tasks. | (CSC 102) Lecture 32 Discrete Structures Trees Previous Lecture Matrices and Graphs Matrices and Directed Graphs Matrices and undirected Graphs Matrices and Connected Components Trees Characterizing Trees Rooted Trees Today’s Lecture Rooted Trees Binary Trees Spanning Trees and Shortest Paths Minimum Spanning Trees Kruskal’s Algorithm Prim’s Algorithm Finding Minimum Spanning Trees Rooted Trees Rooted Trees These terms are illustrated in the following Figure of Rooted Tree Rooted Trees Example Binary Trees Representation of Algebraic Expressions a/b a/(c+d) ((a − b)·c) + (d/e) Spanning Trees and Shortest Paths An East Coast airline company wants to expand service to the Midwest and has received permission from the Federal Aviation Authority to fly any of the routes shown in Figure Spanning Trees and Shortest Paths The fact is that the graph of any system of routes that satisfies the company’s wishes is a tree, because if the graph were to contain a circuit, then one of the routes in the circuit could be removed without disconnecting the graph, and that would give a smaller total number of routes. But any tree with eight vertices has seven edges. Therefore, any system of routes that connects all eight vertices and yet minimizes the total number of routes consists of seven routes. Spanning Trees and Shortest Paths Definition A spanning tree for a graph G is a subgraph of G that contains every vertex of G and is a tree. Theorem 1. Every connected graph has a spanning tree. 2. Any two spanning trees for a graph have the same number of edges. Spanning Trees Example Find all spanning trees for the graph G pictured below. Solution The graph G has one circuit v2v1v4v2, and removal of any edge of the circuit gives a tree. Thus, as shown below, there are three spanning trees for G. Minimum Spanning Trees Now suppose the airline company wants to serve all the cities shown, but with a route system that minimizes the total mileage. More generally, a graph whose edges are .

• Cơ sở dữ liệu
• Discrete structures
• Lecture Discrete structures
• Cấu trúc rời rạc
• Discrete data
• Discrete mathematics
• Computer scientists
• Equivalence relations