1Chapter 3GraphsSlides by Kevin Wayne.Copyright © 2005 Pearson-Addison Wesley.All rights reserved.3.1 Basic Definitions and Applications3Undirected GraphsUndirected graph. G = (V, E)! V = nodes.! E = edges between pairs of nodes.! Captures pairwise relationship between objects.! Graph size parameters: n = |V|, m = |E|.V = { 1, 2, 3, 4, 5, 6, 7, 8 }E = { 1-2, 1-3, 2-3, 2-4, 2-5, 3-5, 3-7, 3-8, 4-5, 5-6 }n = 8m = 114Some Graph ApplicationstransportationGraphstreet intersectionsNodes Edgeshighwayscommunication computers fiber optic cablesWorld Wide Web web pages hyperlinkssocial people relationshipsfood web species predator-preysoftware systems functions function callsscheduling tasks precedence constraintscircuits gates wires5World Wide WebWeb graph.! Node: web page.! Edge: hyperlink from one page to another.cnn.comcnnsi.comnovell.comnetscape.comtimewarner.comhbo.comsorpranos.com69-11 Terrorist NetworkSocial network graph.! Node: people.! Edge: relationship between two people.Reference: Valdis Krebs, http://www.firstmonday.org/issues/issue7_4/krebs7Ecological Food WebFood web graph.! Node = species.! Edge = from prey to predator.Reference: http://www.twingroves.district96.k12.il.us/Wetlands/Salamander/SalGraphics/salfoodweb.giff8Graph Representation: Adjacency MatrixAdjacency matrix. n-by-n matrix with Auv = 1 if (u, v) is an edge.! Two representations of each edge.! Space proportional to n2.! Checking if (u, v) is an edge takes !(1) time.! Identifying all edges takes !(n2) time. 1 2 3 4 5 6 7 81 0 1 1 0 0 0 0 02 1 0 1 1 1 0 0 03 1 1 0 0 1 0 1 14 0 1 0 1 1 0 0 05 0 1 1 1 0 1 0 06 0 0 0 0 1 0 0 07 0 0 1 0 0 0 0 18 0 0 1 0 0 0 1 09Graph Representation: Adjacency ListAdjacency list. Node indexed array of lists.! Two representations of each edge.! Space proportional to m + n.! Checking if (u, v) is an edge takes O(deg(u)) time.! Identifying all edges takes !(m + n) time.1 2 3234 2 5567 3 881 3 4 51 2 5872 3 4 65degree = number of neighbors of u3 710Paths and ConnectivityDef. A path in an undirected graph G = (V, E) is a sequence P of nodesv1, v2, …, vk-1, vk with the property that each consecutive pair vi, vi+1 isjoined by an edge in E.Def. A path is simple if all nodes are distinct.Def. An undirected graph is connected if for every pair of nodes u andv, there is a path between u and v.11CyclesDef. A cycle is a path v1, v2, …, vk-1, vk in which v1 = vk, k > 2, and thefirst k-1 nodes are all distinct.cycle C = 1-2-4-5-3-112TreesDef. An undirected graph is a tree if it is connected and does notcontain a cycle.Theorem. Let G be an undirected graph on n nodes. Any two of thefollowing statements imply the third.! G is connected.! G does not contain a cycle.! G has n-1 edges.13Rooted TreesRooted tree. Given a tree T, choose a root node r and orient eachedge away from r.Importance. Models hierarchical structure.a treethe same tree, rooted at 1vparent of vchild of vroot r14Phylogeny TreesPhylogeny trees. Describe evolutionary history of species.15GUI Containment HierarchyReference: http://java.sun.com/docs/books/tutorial/uiswi ng/overview/anatomy.htmlGUI containment hierarchy. Describe organization of GUI widgets.3.2 Graph Traversal17Connectivitys-t connectivity problem. Given two node s and t, is there a pathbetween s and t?s-t shortest path problem. Given two node s and t, what is the lengthof the shortest path between s and t?Applications.! Friendster.! Maze traversal.! Kevin Bacon number.! Fewest number of hops in a communication network.18Breadth First SearchBFS intuition. Explore outward from s in all possible directions, addingnodes one "layer" at a time.BFS algorithm.! L0 = { s }.! L1 = all neighbors of L0.! L2 = all nodes that do not belong to L0 or L1, and that have an edgeto a node in L1.! Li+1 = all nodes that do not belong to an earlier layer, and that havean edge to a node in Li.Theorem. For each i, Li consists of all nodes at distance exactly ifrom s. There is a path from s to t iff t appears in some layer.sL1L2L n-119Breadth First SearchProperty. Let T be a BFS tree of G = (V, E), and let (x, y) be an edgeof G. Then the level of x and y differ by at most 1.L0L1L2L320Breadth First Search: AnalysisTheorem. The above implementation of BFS runs in O(m + n) time ifthe graph is given by its adjacency representation.Pf.! Easy to prove O(n2) running time:– at most n lists L[i]– each node occurs on at most one list; for loop runs " n times– when we consider node u, there are " n incident edges (u, v),and we spend O(1) processing each edge! Actually runs in O(m + n) time:– when we consider node u, there are deg(u) incident edges (u, v)– total time processing edges is #u$V deg(u) = 2m !each edge (u, v) is counted exactly twicein sum: once in deg(u) and once in deg(v)21Connected ComponentConnected component. Find all nodes reachable from s.Connected component containing node 1 = { 1, 2, 3, 4, 5, 6, 7, 8 }.22Flood FillFlood fill. Given lime green pixel in an image, change color of entireblob of neighboring lime pixels to blue.! Node: pixel.! Edge: two neighboring lime pixels.! Blob: connected component of lime pixels.recolor lime green blob to blue23Flood FillFlood fill. Given lime green pixel in an image, change color of entireblob of neighboring lime pixels to blue.! Node: pixel.! Edge: two neighboring lime pixels.! Blob: connected component of lime pixels.recolor lime green blob to blue24Connected ComponentConnected component. Find all nodes reachable from s.Theorem. Upon termination, R is the connected component containing s.! BFS = explore in order of distance from s.! DFS = explore in a different way.su vRit's safe to add v3.4 Testing Bipartiteness26Bipartite GraphsDef. An undirected graph G = (V, E) is bipartite if the nodes can becolored red or blue such that every edge has one red and one blue end.Applications.! Stable marriage: men = red, women = blue.! Scheduling: machines = red, jobs = blue.a bipartite graph27Testing BipartitenessTesting bipartiteness. Given a graph G, is it bipartite?! Many graph problems become:– easier if the underlying graph is bipartite (matching)– tractable if the underlying graph is bipartite (independent set)! Before attempting to design an algorithm, we need to understandstructure of bipartite graphs.v1v2v3v6v5v4v7v2v4v5v7v1v3v6a bipartite graph G another drawing of G28An Obstruction to BipartitenessLemma. If a graph G is bipartite, it cannot contain an odd length cycle.Pf. Not