Graph Theory:
In my last post on game theory, I said that you could find an optimal probabilistic grand strategy for any two-player, simultaneous move, zero-sum game. It's done through something called linear programming. But linear programming is useful for a...
Read on »
Posted on May 7, 2008 2:28 PM • 21 Comments •
As promised, today I'm going to talk about how to compute the strongly connected components of a directed graph. I'm going to go through one method, called Kosaraju's algorithm, which is the easiest to understand. It's possible to do...
Read on »
Posted on October 30, 2007 9:09 PM • 18 Comments •
Colored Petri Nets The big step in Petri nets - the one that really takes them from a theoretical toy to a serious tool used by protocol developers - is the extension to colored Petri nets (CPNs). Calling them "colored"...
Read on »
Posted on October 10, 2007 9:03 AM • 8 Comments •
There's one variant of Petri nets, called counted Petri nets, which I'm fond of for personal reasons. As Petri net variants go, it's a sort of sloppy but simple one, but as I said, I'm fond of it. As...
Read on »
Posted on October 4, 2007 9:12 PM • 9 Comments •
Among many of the fascinating things that we computer scientists do with graphs is use them as a visual representation of computing devices. There are many subtle problems that can come up in all sorts of contexts where being...
Read on »
Posted on October 1, 2007 8:11 PM • 12 Comments •
Yet another example of how graphs can be used as models to solve real problems comes from the world of project management. I tend to cringe at anything that involves management; as a former IBMer, I've dealt with my...
Read on »
Posted on September 24, 2007 12:28 PM • 5 Comments •
There's a kind of graph which is very commonly used by people like me for analysis applications, called a lattice. A lattice is a graph with special properties that make it extremely useful for representing information in an analysis...
Read on »
Posted on September 18, 2007 9:09 PM • 12 Comments •
Last time, I showed a way of using a graph to model a particular kind of puzzle via a search graph. Games and puzzles provide a lot of examples of how we can use graphs to model problems. Another...
Read on »
Posted on September 16, 2007 11:58 AM • 10 Comments •
As I've mentioned before, the real use of graphs is as models. Many real problems can be described using graphs as models - that is, to translate the problem into a graph, solve some problem on the graph, and...
Read on »
Posted on September 10, 2007 9:00 AM • 8 Comments •
Suppose you've got a huge graph - millions of nodes. And you know that it's not connected - so the graph actually consists of some number of pieces (called the connected components of the graph). And there are constantly...
Read on »
Posted on September 6, 2007 11:40 AM • 12 Comments •
The next interesting variant on graphs is directed graphs, or digraphs for short. A digraph is a graph where each edge distinguished between its source and its target - so an edge is from one node, and to another...
Read on »
Posted on August 24, 2007 7:14 PM • 6 Comments •
One of the reasons that I like about graph theory so much is because of how it ties into computer science. Graphs are fundamental to many problems in computer science, and a lot of the work in graph theory has...
Read on »
Posted on August 15, 2007 2:37 PM • 23 Comments •
One amusing thing in graph theory is graph traversal. Many of the interesting algorithms on graph are ultimately based on the idea of iterating through the nodes of the graph in some order that is related to the structure...
Read on »
Posted on August 13, 2007 10:05 PM • 7 Comments •
Another really fun and fundamental weighted graph problem is the shortest path problem. The question in: given a connected weighted graph G, what is the shortest path between two vertices v and w in G?...
Read on »
Posted on August 10, 2007 4:33 PM • 5 Comments •
I got started on this series about graph theory by writing a post debunking something foolish that George Gilder said about network theory. Today I'm going to talk about one of the classic problems in graph theory, which happens...
Read on »
Posted on August 7, 2007 6:50 PM • 13 Comments •
Moving on from simple graphs, one of the things you can do to make things more interesting is to associate numeric values with the edges, called the weights of those edges. This variation of a graph is called a...
Read on »
Posted on August 1, 2007 11:07 AM • 8 Comments •
Often, we use graphs as a structured representation of some kind of information. Many interesting problems involving the things we're representing can then by described in terms of operations over graphs. Today, I'm going to talk about some of...
Read on »
Posted on July 23, 2007 7:48 PM • 27 Comments •
One application of graph theory that's particularly interesting to me is called Ramsey theory. It's particularly interesting as someone who debunks a lot of creationist nonsense, because Ramsey theory is in direct opposition to some of the basic ideas...
Read on »
Posted on July 16, 2007 8:47 PM • 26 Comments •
Today, I'm going to talk a bit about two closely related problems in graph theory: the maximal clique detection problem, and the maximal common subgraph problem. The two problems are interesting both on their own as easy-to-understand but hard-to-compute...
Read on »
Posted on July 15, 2007 6:52 PM • 15 Comments •
One of the things that I find fascinating about graph theory is that it's so simple, and yet, it's got so much depth. Even when we're dealing with the simplest form of a graph - undirected graphs with no 1-cycles,...
Read on »
Posted on July 10, 2007 9:53 PM • 10 Comments •
Another 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...
Read on »
Posted on July 8, 2007 6:48 PM • 15 Comments •
One 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...
Read on »
Posted on July 4, 2007 2:10 PM • 4 Comments •
In 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...
Read on »
Posted on July 3, 2007 3:49 PM • 1 Comments •
Naming 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...
Read on »
Posted on July 2, 2007 9:49 PM • 14 Comments •
Coloring 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...
Read on »
Posted on July 2, 2007 9:04 AM • 21 Comments •
Graph 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....
Read on »
Posted on June 28, 2007 7:59 PM • 10 Comments •
One 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...
Read on »
Posted on June 26, 2007 3:48 PM • 20 Comments •
Let's talk a bit about graphs, being a tad more formal about them....
Read on »
Posted on June 25, 2007 7:31 PM • 30 Comments •
Set 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...
Read on »
Posted on June 24, 2007 7:40 PM • 13 Comments •
