TAILIEUCHUNG - Lecture Algorithms and data structures (CSC112) - Chapter 28
In this chapter, you learned about 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. | Review Binary Search Trees Operations on Binary Search Tree Inserting a Node Searching a Node Deleting a Node Expression Tree Decision Tree Graphs Graph Directed Graph Undirected Graph Sub-Graph Spanning Sub-Graph Degree of a Vertex Weighted Graph Elementary and Simple Path Link List Representation Introduction A graph G consist of 1. Set of vertices V (called nodes), V = {v1, v2, v3, v4} and 2. Set of edges E={e1, e2, e3} A graph can be represented as G = (V, E), where V is a finite and non empty set of vertices and E is a set of pairs of vertices called edges Each edge ‘e’ in E is identified with a unique pair (a, b) of nodes in V, denoted by e = {a, b} 3 Consider the following graph, G Then the vertex V and edge E can be represented as: V = {v1, v2, v3, v4, v5, v6} and E = {e1, e2, e3, e4, e5, e6} E = {(v1, v2) (v2, v3) (v1, v3) (v3, v4),(v3, v5) (v5, v6)} There are six edges and vertex in the graph 4 Directed Graph A graph can be a Directed Graph Undirected/Simple Graph A directed graph G is defined as an ordered pair (V, E) where, V is a set of vertices and the ordered pairs in E are called edges on V A directed graph can be represented geometrically as a set of marked points (called vertices) V with a set of arrows (called edges) E between pairs of points (or vertex or nodes) so that there is at most one arrow from one vertex to another vertex 5 For example, following figure shows a directed graph, where G ={a, b, c, d }, E={(a, b), (a, d), (d, b), (d, d), (c, c)} An edge (a, b), is said to be the incident with the vertices it joints, ., a, b We can also say that the edge (a, b) is incident from a to b The vertex a is called the initial vertex and the vertex b is called the terminal vertex of the edge (a, b) 6 If an edge that is incident from and into the same vertex, say (d, d) or (c, c) in figure, is called a loop Two vertices are said to be adjacent if they are joined by an edge Consider edge (a, b), the vertex a is said to be adjacent to .
đang nạp các trang xem trước
