LiveJournal will be undergoing maintenance on May 25, and might display errors until complete. Please see http://lj-maintenance.livejournal.com/ for details and updates.

Bram Cohen () wrote,
Trikke

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.
• Post a new comment

Error

Anonymous comments are disabled in this journal

default userpic