Chapter 10 Simple Graphs Graphs in which edges are not directed are called simple graphs. They come up in all sorts of applications, including scheduling, optimization, communications, and the design and analysis of algorithms. Two Stanford students even used graph theory to become multibillionaires! But we’ll start with an application designed to get your attention: we are going to make a professional inquiry into sexual behavior. Namely, we’ll look at some data about who, on average, has more opposite-gender partners, men or women. Sexual demographics have been the subject of many studies. In one of the largest, researchers from the University of Chicago interviewed a random sample of 2500 people over several years to try to get an answer to this question. Their study, published in 1994, and entitled The Social Organization of Sexuality found that on average men have 74% more opposite-gender partners than women. Other studies have found that the disparity is even larger. In particular, ABC News claimed that the average man has 20 partners over his lifetime, and the aver-age woman has 6, for a percentage disparity of 233%. The ABC News study, aired on Primetime Live in 2004, purported to be one of the most scientific ever done, with only a 2.5% margin of error. It was called ”American Sex Survey: A peek between the sheets,” —which raises some question about the seriousness of their reporting. Yet again, in August, 2007, the N.Y. Times reported on a study by the National Center for Health Statistics of the U.S. government showing that men had seven partners while women had four. Anyway, whose numbers do you think are more accurate, the University of Chicago, ABC News, or the National Center? —don’t answer; this is a setup question like “When did you stop beating your wife?” Using a little graph theory, we’ll explain why none of these findings can be anywhere near the truth. 167168 CHAPTER 10. SIMPLE GRAPHS 10.1 Degrees & Isomorphism 10.1.1 Definition of Simple Graph Informally, a graph is a bunch of dots with lines connecting some of them. Here is an example: ABCDEFGHIFor many mathematical purposes, we don’t really care how the points and lines are laid out —only which points are connected by lines. The definition of simple graphs aims to capture just this connection data. Definition 10.1.1. A simple graph, G, consists of a nonempty set, V , called the ver-tices of G, and a collection, E, of two-element subsets of V . The members of E are called the edges of G. The vertices correspond to the dots in the picture, and the edges correspond to the lines. For example, the connection data given in the diagram above can also be given by listing the vertices and edges according to the official definition of simple graph: V = {A, B, C, D, E, F, G, H, I}E = {{A, B} , {A, C} , {B, D} , {C, D} , {C, E} , {E, F } , {E, G} , {H, I}} . It will be helpful to use the notation A—B for the edge {A, B}. Note that A—B and B—A are different descriptions of the same edge, since sets are unordered. So the definition of simple graphs is the same as for directed graphs, except that instead of a directed edge v w which starts at vertex v and ends at vertex → w, a simple graph only has an undirected edge, v—w, that connects v and w. Definition 10.1.2. Two vertices in a simple graph are said to be adjacent if they are joined by an edge, and an edge is said to be incident to the vertices it joins. The number of edges incident to a vertex is called the degree of the vertex; equivalently, the degree of a vertex is equals the number of vertices adjacent to it. For example, in the simple graph above, A is adjacent to B and B is adjacent to D, and the edge A—C is incident to vertices A and C. Vertex H has degree 1, D has degree 2, and E has degree 3.169 10.1. DEGREES & ISOMORPHISM Graph Synonyms A synonym for “vertices” is “nodes,” and we’ll use these words interchangeably. Simple graphs are sometimes called networks, edges are sometimes called arcs. We mention this as a “heads up” in case you look at other graph theory literature; we won’t use these words. Some technical consequences of Definition 10.1.1 are worth noting right from the start: 1. Simple graphs do not have self-loops ({a, a} is not an undirected edge be-cause an undirected edge is defined to be a set of two vertices.) 2. There is at most one edge between two vertices of a simple graph. 3. Simple graphs have at least one vertex, though they might not have any edges. There’s no harm in relaxing these conditions, and some authors do, but we don’t need self-loops, multiple edges between the same two vertices, or graphs with no vertices, and it’s simpler not to have them around. For the rest of this Chapter we’ll only be considering simple graphs, so we’ll just call them “graphs” from now on. 10.1.2 Sex in America Let’s model the question of heterosexual partners in graph theoretic terms. To do this, we’ll let G be the graph whose vertices, V , are all the people in America. Then we split V into two separate subsets: M , which contains all the males, and F , which contains all the females.1 We’ll put an edge between a male and a female iff they have been sexual partners. This graph is pictured in Figure 10.1 with males on the left and females on the right. M WFigure 10.1: The sex partners graph 1For simplicity, we’ll ignore the possibility of someone being both, or neither, a man and a woman.� � 170 CHAPTER 10. SIMPLE GRAPHS Actually, this is a pretty hard graph to figure out, let alone draw. The graph is enormous: the US population is about 300 million, so V ≈ 300M. Of these, approximately 50.8% are female and 49.2% are male, so |M|||≈ 147.6M , and |F | ≈152.4M. And we don’t even have trustworthy estimates of how many edges there are, let alone exactly which couples are adjacent. But it turns out that we don’t need to know any of this —we just need to figure out the relationship between the average number of partners per male and partners per female. To do this, we note that every edge is incident to exactly one M vertex (remember, we’re only considering male-female relationships); so the sum of the degrees of the M vertices equals the number of edges. For the same reason, the sum of the degrees of the F vertices equals the number of edges. So
View Full Document
Unlocking...