You want to conduct a tour of this museum:

A-B-C
| | |
D-E-F
| | |
G-H-I
| | |
J-K-L

You want to walk through all the hallways once. What would be the least amount of walking you would need to do (each hallway is a kilometer long) to cover all the hallways at least once? (You can start and stop anywhere.)

A network is traversable if it has two or fewer even nodes.

This network has six so some hallways will have to be walked more than once.  Odd nodes may be turned into even nodes by connecting them in pairs.  The two pairs most easily (and shortly) connectable are GD and FI. 

Doing this adds two kilometers of walking to the 17 kilometers of existing hallway for a total tour length of 19 kilometers.  B and K remain as the odd nodes so the tour begins at one and ends at the other.

A possible tour (though the problem doesn't ask for one) is BCFILKJGDABEDGHEFIHK

-Jer

Posted by Jer on 2004-06-04 09:23:09