Graph theory.

Everyone thinks they know what a graph is, but most people don't know what a graph is. Do you know what a graph is? You will definitely know what one is after I tell you. A graph is not the thing you had to draw in high-school algebra. A graph is also not a giraffe, contrary to popular belief. A graph is something like this:

The Petersen graph: one of the most famous graphs. (Image from Wikipedia.)

A graph is a bunch of dots connected by lines or curves. The dots are called vertices, and the lines and curves are called edges. This is all there is to a graph. In particular, a graph is generally not concerned with distances or orientations. The above graph, the Petersen graph, is exactly the same graph as this one:

Also the Petersen graph. (Image from Wikipedia.)

But it looks different! It doesn't matter, though; it's still the same graph. The only thing that matters for a graph is which vertices are connected by edges. It turns out that, in the pair of graphs in this paragraph, you can label each vertex with a number in such a way that the same numbers have edges between them in both versions of the graph. That's how you know they're the same graph. In fact, this was one of my first homework problems in my graph theory class.

I think graph theory is really fun. The problems I get in the class are challenging and interesting—the best possible combination. The professor gives us information in lecture, but then on the homework we have to use what we learned to discover new things, in a way that isn't always immediately clear.

The class has spent a lot of time on Hamiltonian cycles. A cycle is a path through the edges of a graph that doesn't repeat any vertices and ends where it began. A Hamiltonian cycle is a cycle that reaches each vertex once. Not every graph has a Hamiltonian cycle, and an interesting and important part of graph theory studies the question of which graphs have Hamiltonian cycles and which ones don't.

Another really cool thing I've learned about in class is graph coloring. To properly color the vertices of a graph, you assign each one a color in such a way that there is no edge between two same-color vertices—that is, the endpoints of an edge are different colors from each other. Any graph can be properly colored (just put a different color on each vertex), but sometimes we want to know the least number of colors that are needed to properly color a graph. This number is called the chromatic number of the graph.

Graphs are also used in the "stable marriage problem": given a set of people, each having a preference ranking of some of the other people, is there a way to pair off the people so that no two people both prefer the other over their partner? This problem is represented as a graph: each person is a vertex, and each pair of vertices has an edge if it is a possible partnership. Then each vertex has a ranking of the vertices that it's adjacent to. In the traditional scenario, where there are men and women that are to be married off, the answer is yes, there is a stable marriage. In this case, the algorithm for finding a stable marriage is incredibly amusing: it is best conceptualized in terms of one gender making proposals to the other, who accepts or rejects each proposal.

That's about it for giraffe theory. I'm sorry I haven't been updating my blog very often; I'll have to shape up soon, because my next entry will be about my geometry class. HA HA HA.