Graph Theory
goodmath | July 8, 2007Another useful concept in simple graph theory is *contraction* and its result, *minors*
of graphs. The idea is that there are several ways of simplifying a graph in order to study
its properties: cutting edges, removing vertices, and decomposing a graph are all methods we've seen before. Contraction is a different technique that works by *merging* vertices, rather than removing them.
Here's how contraction works. Suppose you have a graph G. Pick a pair of vertices v and w
which are adjacent in G. You can create a graph G' which is a contraction of G by
replacing v and w with a *single*…
goodmath | July 4, 2007One thing that we often want to do is break a graph into pieces in a way that preserves
the structural relations between the vertices in any part. Doing that is called
*decomposing* the graph. Decomposition is a useful technique because many ways
of studying the structure of a graph, and many algorithms over graphs can work by
decomposing the graph, studying the elements of the decomposition, and then combining
the results.
To be formal: a graph G can be decomposed into a set of subgraphs {G1, G2, G3, ...}, where the edges of each of the Gis are
*disjoint* subsets of the edges of G. So in a…
goodmath | July 3, 2007In addition to doing vertex and face colorings of a graph, you can also do edge colorings. In an edge coloring, no two edges which are incident on the same vertex can share the same color. In general, edge coloring doesn't get as much attention as vertex coloring or face coloring, but it can be an interesting subject. Today I'm going to show you an example of a really clever visual proof technique called *graph turning* to prove a statement about the edge colorings of complete graphs.
Just like a graph has a chromatic index for its vertex coloring, it's got a chromatic
index for its edge…
goodmath | July 2, 2007Naming Some Special Graphs
When we talk about graph theory - particularly when we get to some of the
interesting theorems - we end up referencing certain common graphs or type of graphs
by name. In my last post, I had to work in the definition of snark, and struggle around
to avoid mentioning another one, so it seems like as good a time as any to run through
some of the basics. This won't be an exciting post, but you've got to do the definitions sometime. And there's a bunch of pretty pictures, and even an interesting simple proof or two.
&uot
A *complete* graph is a graph where every…
goodmath | July 2, 2007Coloring general graphs is, as I said in my last post, quite difficult. But if you can restrict the structure of the graph, you can change the problem in a way that makes it *much* easier. The classic example of this is *planar graphs*.
A planar graph is a graph which can be drawn on a plane with no edges crossing. Every planar graph is also the structural equivalent to a map, where the vertices corresponding to two countries on a map are adjacent if and only if the countries share a border in the map. (A border here has non-zero length, so two countries that only meet in a corner don't…
goodmath | June 28, 2007Graph coloring is deceptively simple. The idea of coloring a graph is very straightforward, and it seems as if it should be relatively straightforward to find a coloring. It turns out to not be - in fact, it's extremely difficult. A simple algorithm for graph coloring is easy to describe, but potentially extremely expensive to run.
In terms of computational complexity - the measure that we computer scientists use to describe how hard it is to compute a solution to a problem - it's actually NP-hard. What that means that there is no known algorithm for optimal graph coloring which isn't…
goodmath | June 26, 2007One kind of graph problem that's extremely widely used in computer science is called graph coloring. There's two versions of it, *vertex coloring*, and *face coloring*.
Vertex coloring is the one that's more widely used. Edge coloring problems are all variations on the following: given a graph *G=(V,E)*, find a mapping of colors to vertices, such than if two vertices are adjacent, they're assigned different colors?
The variants of the vertex coloring problem are things like:
* What's the *minimum* number of colors (aka the *chromatic number* of the graph)
that can be used to color a…
goodmath | June 25, 2007
Let's talk a bit about graphs, being a tad more formal about them.
A graph G is a pair (V,E) where V is a non-empty set of *objects* called vertices, and E is a set of pairs of elements of V called edges where a pair x={a,b} means that
vertices a and b are *adjacent*. We also say that edge x is *incident on* both a and b.
The number of edges that are incident on a vertex is called the *degree* of a vertex.
Take any graph G, and take the sum of the degrees of all vertices. That number will
be 2×|E| (2 times the cardinality of the set of edges.) This should be pretty obvious: since each edge…
goodmath | June 24, 2007Set theory is, alas, going to need to take a break. I left my books on the train on friday. $200 worth of textbooks down the tubes, unless one of the conductors happened to hang on to them. At least I've got a pre-order already placed for a copy of the new addition of Ferreirós book; between that, and a new copy of Quine, I should be OK. But in the meantime, we'll look at something else. Since I mentioned graph theory on friday, and I've been promising forever to write about it, I figured this is a good time.
My favorite introduction to graph theory is stolen from one of my grad school…