Question? Leave a message!




Graph theory and the Graph ADT

Graph theory and the Graph ADT
ECE 250 Algorithms and Data Structures Graph theory and the Graph ADT Douglas Wilhelm Harder, M.Math. LEL Department of Electrical and Computer Engineering University of Waterloo Waterloo, Ontario, Canada ece.uwaterloo.ca dwharderalumni.uwaterloo.ca © 20062013 by Douglas Wilhelm Harder. Some rights reserved.Graph theory 2 Outline A graph is an abstract data type for storing adjacency relations – We start with definitions: • Vertices, edges, degree and subgraphs – We will describe paths in graphs • Simple paths and cycles – Definition of connectedness – Weighted graphs – We will then reinterpret these in terms of directed graphs – Directed acyclic graphsGraph theory 3 Outline We will define an Undirected Graph ADT as a collection of vertices V = v , v , ..., v 1 2 n – The number of vertices is denoted by V = n – Associated with this is a collection E of unordered pairs v , v termed i j edges which connect the vertices There are a number of data structures that can be used to implement abstract undirected graphs – Adjacency matrices – Adjacency listsGraph theory 4 Graphs Consider this collection of vertices V = v , v , ..., v 1 2 9 where V = nGraph theory 5 Undirected graphs Associated with these vertices are E = 5 edges E = v , v , v , v , v , v , v , v , v , v 1 2 3 5 4 8 4 9 6 9 – The pair v , v indicates that both vertex v is adjacent to vertex v and j k j k vertex v is adjacent to vertex v k jGraph theory 6 Undirected graphs We will assume in this course that a vertex is never adjacent to itself – For example, v , v will not define an edge 1 1 The maximum number of edges in an undirected graph is VV1  V 2 EV O  2 2 Graph theory 7 An undirected graph Example: given the V = 7 vertices V = A, B, C, D, E, F, G and the E = 9 edges E = A, B, A, D, A, E, B, C, B, D, B, E, C, E, C, F, D, EGraph theory 8 Degree The degree of a vertex is defined as the number of adjacent vertices degree(A) = degree(D) = degree(C) = 3 degree(B) = degree(E) = 4 degree(F) = 1 degree(G) = 0 Those vertices adjacent to a given vertex are its neighborsGraph theory 9 Subgraphs A subgraph of a graph a subset of the vertices and a subset of the edges that connected the subset of vertices in the original graphGraph theory 10 Vertexinduced subgraphs A vertexinduced subgraph is a subset of a the vertices where the edges are all edges in the original graph that originallyGraph theory 11 Paths A path in an undirected graph is an ordered sequence of vertices (v , v , v , ..., v ) 0 1 2 k where v , v is an edge for j = 1, ..., k j – 1 j – Termed a path from v to v 0 k – The length of this path is k Graph theory 12 Paths A path of length 4: (A, B, E, C, F)Graph theory 13 Paths A path of length 5: (A, B, E, C, B, D)Graph theory 14 Paths A trivial path of length 0: (A)Graph theory 15 Simple paths A simple path has no repetitions other than perhaps the first and last vertices A simple cycle is a simple path of at least two vertices with the first and last vertices equal – Note: these definitions are not universal http://xkcd.com/140/Graph theory 16 Connectedness Two vertices v , v are said to be connected if there exists a path i j from v to v i j A graph is connected if there exists a path between any two vertices An unconnected graph A connected graphGraph theory 17 Weighted graphs A weight may be associated with each edge in a graph – This could represent distance, energy consumption, cost, etc. – Such a graph is called a weighted graph Pictorially, we will represent weights by numbers next to the edgesGraph theory 18 Weighted graphs The length of a path within a weighted graph is the sum of all of the edges which make up the path – The length of the path (A, D, G) in the following graph is 5.1 + 3.7 = 8.8Graph theory 19 Weighted graphs Different paths may have different weights – Another path is (A, C, F, G) with length 1.2 + 1.4 + 4.5 = 7.1Graph theory 20 Weighted graphs Problem: find the shortest path between two vertices – Here, the shortest path from A to H is (A, C, F, D, E, G) with length 5.7Graph theory 21 Trees A graph is a tree if it is connected and there is a unique path between any two vertices – Three trees on the same eight vertices Consequences: – The number of edges is E = V – 1 – The graph is acyclic, that is, it does not contain any cycles – Adding one more edge must create a cycle – Removing any one edge creates two disjoint nonempty subgraphsGraph theory 22 Trees Any tree can be converted into a rooted tree by: – Choosing any vertex to be the root – Defining its neighboring vertices as its children and then recursively defining: – All neighboring vertices other than that one designated its parent are now defined to be that vertices children Given this tree, here are three rooted trees associated with itGraph theory 23 Forests A forest is any graph that has no cycles Consequences: – The number of edges is E V – The number of trees is V – E – Removing any one edge adds one more tree to the forest Here is a forest with 22 vertices and 18 edges – There are four treesGraph theory 24 Directed graphs In a directed graph, the edges on a graph are be associated with a direction – Edges are ordered pairs (v , v ) denoting a connection from v to v j k j k – The edge (v , v ) is different from the edge (v , v ) j k k j Streets are directed graphs: – In most cases, you can go two ways unless it is a oneway streetGraph theory 25 Directed graphs Given our graph of nine vertices V = v , v , …v 1 2 9 – These six pairs (v , v ) are directed edges j k E = (v , v ), (v , v ), (v , v ), (v , v ), (v , v ), (v , v ) 1 2 3 5 5 3 6 9 8 4 9 4Graph theory 26 Directed graphs The maximum number of directed edges in a directed graph is VV1  V 2 E 2 2 V V1 O V    2 2 Graph theory 27 In and out degrees The degree of a vertex must be modified to consider both cases: – The outdegree of a vertex is the number of vertices which are adjacent to the given vertex – The indegree of a vertex is the number of vertices which this vertex is adjacent to In this graph: indegree(v ) = 0 outdegree(v ) = 2 1 1 indegree(v ) = 2 outdegree(v ) = 3 5 5Graph theory 28 Sources and sinks Some definitions: – Vertices with an indegree of zero are described as sources – Vertices with an outdegree of zero are described as sinks In this graph: – Sources: v , v , v 7 1 6 – Sinks: v , v 2 9Graph theory 29 Paths A path in a directed graph is an ordered sequence of vertices (v , v , v , ..., v ) 0 1 2 k where (v , v ) is an edge for j = 1, ..., k j – 1 j A path of length 5 in this graph is (v , v , v , v , v , v ) 1 4 5 3 5 2 A simple cycle of length 3 is (v , v , v , v ) 8 4 5 8Graph theory 30 Connectedness Two vertices v , v are said to be connected if there exists a path j k from v to v j k – A graph is strongly connected if there exists a directed path between any two vertices – A graph is weakly connected there exists a path between any two vertices that ignores the direction In this graph: – The subgraph v , v , v , v is strongly 3 4 5 8 connected – The subgraph v , v , v , v , v , v is 1 2 3 4 5 8 weakly connectedGraph theory 31 Weighted directed graphs In a weighted directed graphs, each edge is associated with a value Unlike weighted undirected graphs, if both (v , v ) and (v , v ) are j k j k edges, it is not required that they have the same weight 6.4 7.5 6.8 7.3 6.7 5.9 4.1 3.2 4.7 4.5 5.4Graph theory 32 Directed acyclic graphs A directed acyclic graph is a directed graph which has no cycles – These are commonly referred to as DAGs – They are graphical representations of partial orders on a finite number of elements These two are DAGs: This directed graph is not acyclic:Graph theory 33 Directed acyclic graphs Applications of directed acyclic graphs include: – The parse tree constructed by a compiler – A reference graph that can be garbage collected using simple reference counting – Dependency graphs such as those used in instruction scheduling and makefiles – Dependency graphs between classes formed by inheritance relationships in objectoriented programming languages – Information categorization systems, such as folders in a computer – Directed acyclic word graph data structure to memoryefficiently store a set of strings (words) Reference: http://en.wikipedia.org/wiki/DirectedacyclicgraphGraph theory 34 Representations How do we store the adjacency relations – Binaryrelation list – Adjacency matrix – Adjacency listGraph theory 35 Binaryrelation list The most inefficient is a relation list: – A container storing the edges (1, 2), (1, 4), (3, 5), (4, 2), (4, 5), (5, 2), (5, 3), (5, 8), (6, 9), (7, 9), (8, 4) – Requires Q(E) memory – Determining if v is adjacent to v is O(E) j k – Finding all neighbors of v is Q(E) jGraph theory 36 Adjacency matrix Requiring more memory but also faster, an adjacency matrix – The matrix entry (j, k) is set to true if there is an edge (v , v ) j k 1 2 3 4 5 6 7 8 9 1 T T 2 3 T 4 T T 5 T T T 6 T 7 T 8 T 9 2 – Requires Q(V ) memory – Determining if v is adjacent to v is O(1) j k – Finding all neighbors of v is Q(V) jGraph theory 37 Adjacency list Most efficient for algorithms is an adjacency list – Each vertex is associated with a list of its neighbors 1 • → 2 → 4 2 • 3 • → 5 4 • → 2 → 5 5 • → 2 → 3 → 8 6 • → 9 7 • → 9 8 • → 4 9 • – Requires Q(V + E) memory – On average:  E • Determining if v is adjacent to v is O j k  V   E • Finding all neighbors of v is Q j  V Graph theory 38 The Graph ADT The Graph ADT describes a container storing an adjacency relation – Queries include: • The number of vertices • The number of edges • List the vertices adjacent to a given vertex • Are two vertices adjacent • Are two vertices connected – Modifications include: • Inserting or removing an edge • Inserting or removing a vertex (and all edges containing that vertex) The runtime of these operations will depend on the representationGraph theory 39 Summary In this topic, we have covered: – Basic graph definitions • Vertex, edge, degree, adjacency – Paths, simple paths, and cycles – Connectedness – Weighted graphs – Directed graphs – Directed acyclic graphs We will continue by looking at a number of problems related to graphsGraph theory 40 References Wikipedia, http://en.wikipedia.org/wiki/Adjacencymatrix http://en.wikipedia.org/wiki/Adjacencylist rd 1 Donald E. Knuth, The Art of Computer Programming, Volume 1: Fundamental Algorithms, 3 Ed., Addison Wesley, 1997, §2.2.1, p.238. 2 Cormen, Leiserson, and Rivest, Introduction to Algorithms, McGraw Hill, 1990, §11.1, p.200. rd 3 Weiss, Data Structures and Algorithm Analysis in C++, 3 Ed., Addison Wesley, §3.6, p.94. 4 David H. Laidlaw, Course Notes, http://cs.brown.edu/courses/cs016/lectures/1320Graphs.pdf These slides are provided for the ECE 250 Algorithms and Data Structures course. The material in it reflects Douglas W.Harder’s best judgment in light of the information available to him at the time of preparation. Any reliance on these course slides by any party for any other purpose are the responsibility of such parties. Douglas W. Harder accepts no responsibility for damages, if any, suffered by any party as a result of decisions made or actions based on these course slides for any other purpose than that for which it was intended.
Website URL
Comment
sharer
Presentations
Free
Document Information
Category:
Presentations
User Name:
Dr.SethPatton
User Type:
Teacher
Country:
United Kingdom
Uploaded Date:
22-07-2017