Graph Colouring, Part Five

I said last time that I was interested in finding colourings for graphs that have lots of fully connected subgraphs, aka “cliques”. For instance, I’d like to find a four-colouring for this sixteen-node graph: Yuck. What a mess. What this graph is doing a bad job of conveying is that there are twelve fully connected…

14

Graph Colouring, Part Four

Let’s give it a try. Can we colour South America with only four colours? Let’s start by stating what all the edges are in the graph of South America: const int Brazil = 0;const int FrenchGuiana = 1;const int Suriname = 2;const int Guyana = 3; const int Venezuala = 4;const int Colombia = 5;const…

8

Graph Colouring with Simple Backtracking, Part Three

OK, we’ve got our basic data structures in place. Graph colouring is a very well-studied problem. It’s known to be NP-complete for arbitrary graphs, so (assuming that P!=NP) we’re not going to find an always-fast algorithm for colouring an arbitrary graph. However, for typical graphs that we encounter in the wild, the following simple algorithm is…

18

Graph Colouring With Simple Backtracking, Part Two

Before I begin a quick note: congratulations and best wishes to David Johnson, currently the president of my alma mater, the University of Waterloo. The Queen has appointed him to be the next Governor General of Canada come this October. For those of you unfamiliar with the Canadian political structure, Queen Elizabeth is the sovereign…

18

Graph Colouring With Simple Backtracking, Part One

As regular readers know, I’m interested in learning how to change my C# programming style to emphasize more concepts from functional programming, like use of immutable rather than mutable data structures and use of declarative control flow like LINQ queries instead of imperative control flow in the form of loops. I thought I’d solve a fairly…

23