Our first topic today is "Sex in America"-- what they never told you in 8th grade health class. In 1994 the University of Chicago conducted a massive survey. Their results indicated that on average men have 74 percent more opposite-gender partners than women. That's a startling statistic under any intepretation. We'll come back in a moment and look at this through the lens of graph theory. Informally, a graph is just a bunch of dots joined by lines. Here's an example. This is great, because you probably were pretty up on dots and lines by age 6 and that's about all we're going to talk about for the next couple weeks. (Of course, we'll find SOME way to make it all seem screwed up and confusing...) For starters, we need to a more precise definition of a graph if we're going to do proofs. So, formally, a graph is a pair of sets, which are often named V and E. V is a nonempty set whose elements are called vertices. And E is a set of edges, which are 2-element subsets of vertices. Let's see how this definition relates to the picture. This graph has 6 vertices. Let's call them A thru F. So then V, the set of vertices, is just A through F. Now the edges are 2-element subsets of vertices. In this case, we have {a, c}, {e, c}, ... So, formally, the graph is this pair of sets-- nothing more, nothing less-- and this diagram is just an illustration of the graph. So if we make the edges more curvy or move some vertices around, this would still depict the same graph. Any questions about what a graph is? Now, formally, edges are 2-element subsets, but to avoid death by squiggly braces, let's denote an edge between a and c like this (a--c) or this (c--a) I'm gonna warn you now-- there's a lot of terminology associated with graphs. At least most of the terms relate to pretty intuitive ideas. Unfortunately, no one agrees on the precise meanings of a lot of those terms. For example, I've insisted that the set of vertices in a graph be nonempty. Some authors allow graphs with no vertices. It's a not a *big* difference and it doesn't *make* much difference, so don't be alarmed by this kind of inconsistency. If you're not sure exactly what we mean by some term, just ask. Anyway, here's a first definition: The degree of a vertex is the number of incident edges. For example Deg(c) = 3 and Deg(a) = 1. ------------------------------------------------------------------------------- Let's return to the University of Chicago study and think about it terms of graphs. Let's create a vertex for each person in America. Let's put some the of vertices-- call them M vertices-- over here. And let's put the rest of the vertices-- call them W vertices over her. So the vertex set for this graph is M U W. Now, without getting into a lot of specifics, from time to time an M vertex and a W vertex get together, one thing leads to another, an edge appears between and M vertex and a W vertex. We'll say that those are "partners". (Some day you'll have a little kid and you'll sit him down and say, "Well, Jonny, there are two kinds of vertices...") ------------------------------------------------------------------------------- Every edge in this graph connects an M vertex to a W vertex; we're only considering opposite-gender partners. Each edge increases the degree of an M vertex by 1 and increases the degree of a W vertex by 1. Therefore, no matter how many edges there are: sum M = sum W Let's divide both sides by the product of the sizes of these two sets. [...] So the survey data collected in the Chicago study is provably way off! On average men have 3.5% more partners, but that's toally a function of population statistics. No behavior change by either gender can affect that statistic. ------------------------------------------------------------------------------- Graphs are probably the most useful mathematical object in computer science. And the reason is that they can model so many different phenomena. ------------------------------------------------------------------------------- Are these two graphs the same? Well, strictly speaking, no. V1, the set of vertices in the first graph is {a, b, c, d}, but V2, the set of vertices in the second graph is {1, 2, 3, 4}. Those are different sets. And a graph IS just a pair of sets. So these are two different graphs. But... they're pretty much the same. I mean, they have the same structure. In a sense, they're not meaningfully different. There's a mathematical name for this sort of structural sameness-- isomorphism. ------------------------------------------------------------------------------- All right, we've got most of the basic definitions out of the way. Let's try to say something about the overall structure of graphs. ------------------------------------------------------------------------------- Now, intuitively, a graph with a lot of vertices and only a few edges can't possibly be connected; you just can't hook everything up! But as you add more edges, you can connect up more stuff and the number of connected components may drop. We can formalize this observation into a theorem. But I'll tell ya... some points about the proof of this theorem are going to be much more important than the theorem itself. ------------------------------------------------------------------------------- Anyone heard of the "six degrees of separation" claim? This says that if you take any two people in the world, say one of you and somebody in the Australian outback, then you know someone who knows someone who knows someone who knows someone who knows the guy in Australia, where there are at most six "knows someone"'s in the chain. We can think about this in graph terms. Suppose we construct a social graph, where the vertices are all the people in the world, and there's an edge between any two people that know each other. For example, here's a little piece of the social graph... ------------------------------------------------------------------------------- Trees are so common that even some special types of trees are worth mention. A ROOTED TREE is a tree with one vertex designated as the "root". This orients the whole graph. If you take a vertex x, then the vertices one step further from the root are called children of x. For example, y is a child of x. And x is called the parent of y. You'll even see often see a special case of this special special case-- a rooted tree is binary if there are at most 2 children per vertex. You'll see one of those critters next week. ------------------------------------------------------------------------------- Coloring final exam scheduling problem Delta = k => Chi <= k+1 Bipartite graphs Mention: bipartite iff no odd cycle Planar graphs definition Euler's formula regular polyhedra Hall's theorem -------------------------------------------------------------------------------