6.042J/18.062J 16. Simple Graphs, Degrees and Isomorphism

1 Albert R Meyer, March 10, 2010 lec 6W.1 Mathematics for Computer Science MIT 6.042J/18.062J Simple Graphs Degrees, Isomorphism, Paths Albert R Meyer, March 10, 2010 lec 6W.2 Types of Graphs Directed Graph Multi-Graph Simple Graph this week next week Albert R Meyer, March 10, 2010 A simple graph: Definition: A simple graph G consists of •a nonempty set, V, of vertices •a set, E, of edges (edge = set of 2 vertices) lec 6W.3 Albert R Meyer, March 10, 2010 lec 6W.5 vertices, V undirected edges, E A Simple Graph ::= { , } edge “adjacent” Albert R Meyer, March 10, 2010 deg( ) = 2 lec 6W.9 degree of a vertex is # of incident edges Vertex degree Albert R Meyer, March 10, 2010 lec 6W.10 degree of a vertex is # of incident edges Vertex degree deg( ) = 4 2 Albert R Meyer, March 10, 2010 lec 6W.11 Possible Graph? orphaned edge Is there a graph with vertex degrees 2,2,1? NO! 2 2 1 Impossible Graph Albert R Meyer, March 10, 2010 lec 6W.12 sum of degrees is twice # edges Handshaking Lemma Proof: Each edge contributes 2 to the sum on the right Albert R Meyer, March 10, 2010 lec 6W.13 Handshaking Lemma sum of degrees is twice # edges 2+2+1 = odd, so impossible Albert R Meyer, March 10, 2010 lec 6W.14 Sex in America: Men more Promiscuous? Study claims: Men average many more partners than women. Graph theory shows this is nonsense Albert R Meyer, March 10, 2010 lec 6W.15 M partners F Sex Partner Graph Albert R Meyer, March 10, 2010 lec 6W.16 Counting pairs of partners now divide by both sides by |M| avg-deg(M) avg-deg(F) 3 Albert R Meyer, March 10, 2010 lec 6W.17 Averages differ solely by ratio of females to males . No big difference Nothing to do with promiscuity Average number of partners 1.035 Albert R Meyer, March 10, 2010 lec 6W.20 The Graph Abstraction 257 67 99 145 306 122 picture of a graph Albert R Meyer, March 10, 2010 lec 6W.21 The Graph Abstraction 257 67 99 145 306 122 picture of same graph Albert R Meyer, March 10, 2010 lec 6W.22 The Graph Abstraction 257 67 99 145 306 122 picture of same graph Albert R Meyer, March 10, 2010 lec 6W.23 The Graph Abstraction 257 67 99 145 306 122 picture of same graph Albert R Meyer, March 10, 2010 lec 6W.28 All that matters are the connections: graphs with the same connections are isomorphic The Graph Abstraction 4 Albert R Meyer, March 10, 2010 lec 6W.29 Isomorphism two graphs are isomorphic when there is an edge-preserving matching of their vertices. Albert R Meyer, March 10, 2010 lec 6W.30 Are these isomorphic? Dog Pig Cat Cow Beef Tuna Corn Hay f(Dog) = Beef f(Cat) = Tuna f(Cow) = Hay f(Pig) = Corn Albert R Meyer, March 10, 2010 lec 6W.31 Edges preserved? Dog Pig Cat Cow Beef Tuna Corn Hay Albert R Meyer, March 10, 2010 lec 6W.32 Dog Pig Cat Cow Beef Tuna Corn Hay Edges preserved? YES! Albert R Meyer, March 10, 2010 lec 6W.34 Dog Pig Cat Cow Beef Tuna Corn Hay Nonedges preserved? YES! isomorphic! Albert R Meyer, March 10, 2010 lec 6W.35 Formal Def of Graph Isomorphism G1 isomorphic to G2 means edge-preserving vertex matching : bijection f:V1 􀀁 V2 with u—v in E1 iff f(u)—f(v) in E25 Albert R Meyer, March 10, 2010 lec 6W.36 degree 2 all degree 3 Nonisomorphism March 10, 2010 Proving nonisomorphism If some property preserved by isomorphism differs for two graphs, then they’re not isomorphic: •# of nodes, •# of edges, •degree distributions, …. lec 6W.37 Albert R Meyer, March 10, 2010 lec 6W.38 Finding an isomorphism? many possible mappings: large search can use properties preserved by isomorphisms as a guide, for example: •a deg 4 vertex adjacent to a deg 3 can only match with •a deg 4 vertex also adjacent to a deg 3 but even so… March 10, 2010 Are these two graphs isomorphic? ...nothing known is sure to be much faster than searching thru all bijections for an isomorphism lec 6W.39 Albert R Meyer, March 10, 2010 lec 6W.41 Paths Path: sequence of adjacent vertices ( Albert R Meyer, March 10, 2010 lec 6W.42 ( Paths Path: sequence of adjacent vertices © Source unknown. All rights reserved. This content is excluded from our Creative Commons license. For more information, see http://ocw.mit.edu/fairuse.6 Albert R Meyer, March 10, 2010 lec 6W.43 ( Paths Path: sequence of adjacent vertices Albert R Meyer, March 10, 2010 lec 6W.44 ( Paths Path: sequence of adjacent vertices Albert R Meyer, March 10, 2010 lec 6W.45 ( Paths Path: sequence of adjacent vertices Albert R Meyer, March 10, 2010 lec 6W.46 ( ) Paths Path: sequence of adjacent vertices Albert R Meyer, March 10, 2010 lec 6W.47 Connectedness two vertices are connected iff there is a path from one to the other. a graphis connected iff every two vertices are connected. Albert R Meyer, March 10, 2010 lec 6W.48 Simple Paths Simple Path: all vertices different ) (7 Albert R Meyer, March 10, 2010 lec 6W.49 Simple Paths Simple Path: (doesn’t cross itself) ) ( Albert R Meyer, March 10, 2010 lec 6W.50 Paths & Simple Paths Lemma: The shortest path between two vertices is simple! Proof: (by contradiction) suppose path from u to v crossed itself: u v c Albert R Meyer, March 10, 2010 Proof: (by contradiction) suppose path from u to v crossed itself: lec 6W.51 Paths & Simple Paths Lemma: The shortest path between two vertices is simple! u v c then path without c---c is shorter! Albert R Meyer, March 10, 2010 lec 6W.53 Team Problems Problems 1—3MIT OpenCourseWare http://ocw.mit.edu 6.042J /18.062J Mathematics for Computer Science Spring 2010 For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms.