CMSC 451 Graph Properties DFS BFS etc Slides By Carl Kingsford Department of Computer Science University of Maryland College Park Based on Chapter 3 of Algorithm Design by Kleinberg Tardos Graphs Graphs specify pairwise relationships between objects An undirected graph G V E is a pair of sets V is a set of nodes aka vertices E is a set of two elements subset of V An element of E is of the form e u v with u v V A graph is directed if E is a set of ordered pairs u v u v V Graph Terminology Simple at most one edge between every pair of vertices Complete all possible edges are present denoted Kn Degree of a vertex number of incident edges Self loop an edge u u often disallowed Path a sequence v1 v2 vk such that vi vi 1 E for i 1 k Simple path a path with no vertex repeated Closed path a path with v1 vk This path is a cycle if it is simple A graph is connected if there is a path between any pair of vertices Digraph short name for directed graph Graph Terminology II A graph G VG EG is a subgraph of H VH EH if VG VH and EG EH Connected Component a maximal connected subgraph Cut edge aka bridge an edge whose removal increases the of connected components Graph Modeling Examples Graphs model many concepts naturally 1 Social networks 2 Geographic adjacency 3 Polyhedra 4 Chemical Molecules 5 Assigning jobs to applicants 6 Food webs 7 Finite state machines 8 Markov processes 9 Project dependencies 10 World Wide Web 11 Telephone network 12 Roads Graph Modeling Examples Graphs model many concepts naturally 1 Social networks 2 Geographic adjacency 3 Polyhedra 4 Chemical Molecules 5 Assigning jobs to applicants 6 Food webs 7 Finite state machines 8 Markov processes 9 Project dependencies 10 World Wide Web 11 Telephone network 12 Roads last week today Graph Isomorphism When are two graphs the same Often we care only about the structure of the graph and not any vertex labels Definition Graph isomorphism Graphs G and H are isomorphic if there is a bijection f VG VH such that u v EG f u f v EH What s an algorithm to test whether two graphs are isomorphic Graph Isomorphism When are two graphs the same Often we care only about the structure of the graph and not any vertex labels Definition Graph isomorphism Graphs G and H are isomorphic if there is a bijection f VG VH such that u v EG f u f v EH What s an algorithm to test whether two graphs are isomorphic No one knows a really good algorithm This problem is not known to be NP complete unlike Independent Set Open Problems Already 1 Is there a polynomial time algorithm for Independent Set 2 Is there a polynomial time algorithm for Graph Isomorphism Representing Graphs Adjacency list 2 3 2 1 5 3 1 4 4 3 5 2 1 Adjacency matrix 0 1 1 1 0 0 1 0 0 0 0 1 0 1 1 0 0 1 0 0 0 1 1 0 0 3 5 Trees Trees are a special type of graph that occur often in algorithms Definition Tree A graph G is a tree if it is connected and contains no cycles Trees Theorem Characterization of Trees The following statements are equivalent 1 T is a tree 2 T contains no cycles and n 1 edges 3 T is connected and has n 1 edges 4 T is connected and every edge is a cut edge 5 Any two nodes in T are connected by exactly 1 path 6 T is acyclic and adding any new edge creates exactly one cycle Tree Terminology A tree is rooted if it has a distinguished vertex called the root level depth 0 A tree is ordered if it is a rooted tree where the children are assigned an order level depth 1 height 2 level depth 2 In a binary tree each node u ancestor of v has at most 2 children In a m ary tree each node parent of v child of u has at most m children A complete tree is a m ary tree for which each node has m children and all leaves are at the same level v descendent of u leaf and sibling of v Binary Search Trees A binary search tree is a binary tree where 1 a key k u is associated with each node u and 2 the keys in the subtree rooted at left u are all k u 3 the keys in the subtree rooted at right u are al k u Balanced binary search trees try to avoid long stringy trees so that when searching we can eliminate about half the remaining elements at each step E g AVL trees let us find any element in O log n time and we can efficiently update them Graph Traversals Breadth First Search Breadth first search explores the nodes of a graph in increasing distance away from some starting vertex s It decomposes the component into layers Li such that the shortest path from s to each of nodes in Li is of length i Breadth First Search 1 L0 is the set s 2 Given layers L0 L1 Lj then Lj 1 is the set of nodes that are not in a previous layer and that have an edge to some node in layer Lj BFS Tree Example A BFS traversal of a graph results in a breadth first search tree 2 1 s 3 2 1 3 3 BFS Tree Example A BFS traversal of a graph results in a breadth first search tree 2 1 s 3 2 1 3 3 Can we say anything about the non tree edges Property of Non BFS Tree Edges Theorem Choose x Li and y Lj such that x y is an edge in undirected graph G Then i and j differ by at most 1 In other words edges of G that do not appear in the tree connect nodes either in the same layer or adjacent layer Proof Suppose not and that i j 1 All the neighbors of x will be found by layer i 1 Therefore the layer of y is less than i 1 so j i 1 which contradicts i j 1 Depth First Search s 1 DFS keeps walking down a path until it is forced to backtrack It backtracks until it finds a new path to go down 2 Think Solving a maze It results in a search tree called the depth first search tree In general the DFS tree will be very different than the BFS tree 4 5 7 6 3 Depth First Search 2 1 s 3 5 7 4 6 Depth First Search 2 1 s 3 5 7 4 6 Can we say anything about the non tree edges A property of Non DFS Tree Edges Theorem Let x and y be nodes in the DFS tree TG such that x y is …