1Albert R Meyer, March 12, 2010 Graph Connectivity Treeslec 6F.1 Mathematics for Computer ScienceMIT 6.042J/18.062JAlbert R Meyer, March 12, 2010 Connected Components Every graph consists of separate connected pieces (subgraphs) called connected components lec 6F.2 Albert R Meyer, March 12, 2010 Connected Components East Campus E25Med Center E174Infinite corridor 131012 26816 663 connected components the more connected components,the more “broken up" the graph is. lec 6F.3 Albert R Meyer, March 12, 2010 Connected Components The connected componentof vertex v ::=lec 6F.4 Albert R Meyer, March 12, 2010 Connected Components So a graph is connectediff it has only 1 connected component lec 6F.5 Albert R Meyer, March 12, 2010 Def:vertices v, w are k-edge connected if they remain connected whenever fewer than kedges are deleted. lec 6F.6 Edge Connectedness2Albert R Meyer, March 12, 2010 k-edge Connectednesslec 6F.8 1-edge connected no path deleteAlbert R Meyer, March 12, 2010 Edge Connectedness lec 6F.9 2-edge connected no path Albert R Meyer, March 12, 2010 Edge Connectedness lec 6F.10 3-edge connected no path Albert R Meyer, March 12, 2010 k-edge ConnectednessDef:A whole graph is k-edge connected iff every two vertices are k-edgeconnected.lec 6F.11 Albert R Meyer, March 12, 2010 lec 6F.12 Connectivity measures fault tolerance of a network: how many connections canfail without cutting offcommunication? Edge Connectedness Albert R Meyer, March 12, 2010 deletek-edge Connectednesslec 6F.13 1-edge connected this whole graph is3Albert R Meyer, March 12, 2010 lec 6F.16 An edge is a cut edge ifremoving it from the graphdisconnects two vertices.Cut Edges Albert R Meyer, March 12, 2010 lec 6F.18 Cut Edges BB is a cut edge Albert R Meyer, March 12, 2010 Cut Edges deleting B gives two components lec 6F.19 Albert R Meyer, March 12, 2010 Cut Edges A isnot a cut edge Alec 6F.20 Albert R Meyer, March 12, 2010 Cut Edges still connected with edge A deleted lec 6F.21 Albert R Meyer, March 12, 2010 Cut Edges So a connected graph is 2-edge connected iffit has no cut edge. lec 6F.224Albert R Meyer, March 12, 2010 CyclesA cycle is a path that begins and ends with same vertexpath: v···b···w···w···a···v wvabalso: a···v···b···w···w···a lec 6F.23 Albert R Meyer, March 12, 2010 wvaCyclesA cycle is a path that begins and ends with same vertexbalso: a ···w ···w ···b ···v ···a lec 6F.24 Albert R Meyer, March 12, 2010 Simple Cycles A simple cycle is a cycle of length > 2 that doesn’t cross itself: path: v···a···w···v lec 6F.25 vwaAlbert R Meyer, March 12, 2010 Simple Cycles A simple cycle is a cycle of length > 2 that doesn’t cross itself: path: v···a···w···v lec 6F.26 vwaalso: w···a···v···w Albert R Meyer, March 12, 2010 Simple Cycles length > 2 implies that going back & forth over an edge is not a simple cycle lec 6F.27 wvAlbert R Meyer, March 12, 2010 Cut Edges and Cycles Lemma: An edge is anot a cut edge iffit is on a simple cycle. lec 6F.305Albert R Meyer, March 12, 2010 TreesA tree is a connected graphwith no simple cycles.lec 6F.31 equivalently:Albert R Meyer, March 12, 2010 equivalentlyTreeslec 6F.32 A tree is a connected graphwith every edge a cut edge.Albert R Meyer, March 12, 2010 More Trees lec 6F.33 Albert R Meyer, March 12, 2010 Other Tree Definitions • graph with a uniquesimple path between any 2 vertices • connected graph with n vertices and n–1 edges • an edge-maximal acyclic graph lec 6F.34 Albert R Meyer, March 12, 2010 lec 6F.40 Team Problems Problems 1 & 2MIT OpenCourseWarehttp://ocw.mit.edu6.042J / 18.062J Mathematics for Computer ScienceSpring 2010For information about citing these materials or our Terms of Use, visit:
View Full Document
Unlocking...