Graph theory algorithms

Graph theory and the Graph ADT and graph theory and complex networks and graph theory data science
Dr.SethPatton Profile Pic
Dr.SethPatton,United Kingdom,Teacher
Published Date:22-07-2017
Your Website URL(Optional)
Comment
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 © 2006-2013 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 sub-graphs – 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 Sub-graphs A sub-graph 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 Vertex-induced sub-graphs A vertex-induced sub-graph 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.7