27 Oct 2004 Bram   » (Master)


I had some interesting ideas for a human-powered vehicle in which the rider stood upright and propelled forward by side to side motion using the same general principle as pumping on a skateboard or streetboard. Then I read about Trikke and realized that it's been invented already, so I could simply buy one. After an hour of practice I can do laps with a Trikke 8 without having to push at all. It's great fun.

On the subject of interesting vehicles, I'd be remiss not to mention the handcycle.

Graph Isomorphism

After much cogitation, I think I've figured out some examples of graph isomorphism problems which are almost tricky.

Take a graph for which for every pair of nodes (X, Y) the entire graph can be mapped onto itself in an isomorphism such that X maps onto Y. There are many example of these, such as hypercubes. Then, 'split' each node to make a new graph, such that for each node X in the old graph, there are two nodes in the new graph Y and Y', with Y connected to Y'. For each pair of nodes X and Z connected in the original graph and corresponding to Y, Y', W, and W' in the new graph, either connect Y to W and Y' to W' or 'cross' it by connecting Y to W' and Y' to W.

The potentially tricky problem is to determine whether a graph created with one set of crossings is isomorphic to one with a different set of crossings.

One way to differentiate nodes in graphs of this form is to, for each node, make a list of how many other nodes have a minimum distance of one hop away, then two, then three, etc. If there was a loop in the original graph then the numbers will be affected by whether that loop contains an odd or even number of crossings. Proper selection of the graph and crossings make make every short loop have an even number of crossings, thus foiling this approach.


Latest blog entries     Older blog entries

New Advogato Features

New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.

Keep up with the latest Advogato features by reading the Advogato status blog.

If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!