Graphs Part 1 The Seven Bridge Problem The city of K nigsberg was set on both sides of the Pregel River and includes two large islands Kneiphof and Lomse which were connected to each other or to the two mainland portions of the city by seven bridges The problem was to devise a walk through the city that would cross each of those bridges once and only once Euler s View of the Problem We can abstract the problem using the concept of graphs Each piece of land island is denoted by a vertex There are 4 vertices A B C D Each bridge connecting two pieces of land island is denoted by an edge There are 7 edges The number of edges incident with vertex v is called the degree of vertex v Euler s Observation Euler s solution Euler s Observation If the tour starts and ends at the same vertex the degree of must be an even number If the tour passes vertex but does not start or end at the degree of must be an even number Any tour that goes through all 7 edges will touch each of the 4 vertices at least once The degree for each of the 4 vertices is an odd number The tour cannot start and end at the same vertex There are more than 2 vertices whose degree is an odd number Euler s Observation Conclusion There is no Euler tour for the seven bridge problem of K nigsberg This is the origin of Graph Theory Undirected Graph G V E where V is the set of vertices and E is the set of undirected edges Each edge is an unordered pair of vertices In the graph below V 1 2 3 4 5 6 E 1 2 1 4 2 4 2 5 3 5 3 6 4 5 Note that 2 1 and 1 2 denote the same edge 1 4 2 5 3 6 Weighted Undirected Graph G V E w where V is the set of vertices E is the set of undirected edges and w E R is an edge weight function In the example below w 1 2 9 w 3 6 4 Edge weight can represent cost distance bandwidth etc depending on applications 1 8 4 9 5 2 2 1 5 9 3 4 6 Directed Graph G V E where V is the set of vertices and E is the set of directed edges Each edge is an ordered pair of vertices In the graph below V 1 2 3 4 5 6 E 1 2 1 4 2 5 3 5 3 6 4 2 5 4 6 6 1 4 2 5 3 6 Weighted Directed Graph G V E w where V is the set of vertices E is the set of directed edges and w E R is an edge weight function In the example below w 1 2 9 w 2 5 1 Edge weight can represent cost distance bandwidth etc depending on applications 1 8 4 9 5 2 2 1 5 9 3 4 6 3 Summary Graphs and graph theory originated from the seven We can classify graphs into directed graphs and We can classify graphs into weighted graphs and bridge problem undirected graphs unweighted graphs Graphs Part 2 Graph Representations There are two main representations of graphs Adjacency matrix and Adjacency lists You need to choose the right representation for your applications Adjacency Matrix for Unweighted Graphs Assume that V n and E m Adjacency matrix for unweighted graph G V E is an n by n matrix A aij aij 1 if i j E and aij 0 otherwise Commonly we omit the 0s in the matrix Adjacency Matrix for Undirected Graphs 1 4 2 5 3 6 0 1 0 1 0 0 1 0 0 1 1 0 0 0 0 0 1 1 1 1 0 0 1 0 0 1 1 1 0 0 0 0 1 0 0 0 A Adjacency Matrix for Directed Graphs 1 4 2 5 3 6 0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 A Adjacency Matrix for Weighted Graphs Assume that V n and E m Adjacency matrix for weighted graph G V E w is an n by n matrix A aij aij w i j if i j E and aij NIL or o w Commonly we omit the NILs in the matrix Adjacency Matrix for Weighted Graphs 1 8 4 9 5 2 2 1 5 9 3 4 6 9 8 9 5 1 9 4 5 2 8 1 2 9 4 A Adjacency Matrix for Weighted Graphs 1 8 4 9 5 2 2 1 5 9 3 4 6 3 9 8 1 9 4 5 2 3 A Adjacency Lists for Weighted Graphs Assume that V n and E m Adjacency lists for weighted graph G V E w is an array G Adj where for each u V G Adj u also by u Adj is a list that contains all vertices v such that u v E G Adj u is a pointer could be NULL Each node on the list is a struct with the fields vertex which is the label of the vertex v weight which is the value of w u v next which points to the next node on the list there is no weight field for unweighted graphs Adjacency Lists for Weighted Graphs 1 8 4 9 5 2 2 1 5 9 3 4 6 2 9 1 9 5 9 1 8 2 1 3 4 4 8 4 5 6 4 2 5 3 9 5 1 5 2 4 2 123456 Adjacency Lists for Weighted Graphs 1 8 4 9 5 2 2 1 5 9 3 4 6 3 4 8 6 4 2 9 5 1 5 9 2 5 4 2 6 3 123456 Graphs Part 3 Breadth First Search One of the simplest algorithms for graph searching Very efficient Many applications Prim s minimum spanning tree algorithm Dijkstra s shortest path algorithm Preliminaries We start from a source vertex s Discover vertices in the graph Three possible color values of a vertex white not discovered yet gray discovered but not explored black discovered and explored Initially all vertices are white The source vertex is discovered first Predecessor Parent While exploring gray node u we check the If v on u Adj is white we say v is discovered by u We also say u is the parent or predecessor of v This is adjacency list u Adj denoted by v u 5 2 1 4 3 BFS G s u color WHITE s color GRAY Breadth First Search for each vertex u d u NIL s d 0 s NIL Q while Q 11 for each vertex 15 v u 12 if v color WHITE 13 v color GRAY 14 v d u d 1 9 10 u …
View Full Document
Unlocking...