In the Project Euler problem
Tom and Jerry, it defines Tom graphs. A cat named Tom and a mouse named Jerry play a game on a graph G. Each vertex of G is a mouse hole. Jerry hides in one of the holes. Then, Tom tries to catch Jerry by picking a hole. Then, Jerry moves to an adjacent hole. Then, Tom picks another hole. They keep doing this, where Jerry moves to an adjacent hole and Tom picks a hole. A Tom graph is a graph that Tom can always catch Jerry by following a sequence of holes.
Example: This is a Tom graph.
1---2---3
Tom can do the sequence 2, 2 to guarantee catching Jerry.
1. Prove that all Tom graphs are cycle-free.
2. Find the smallest cycle-free graph that is not a Tom graph.
These graph are hard to analyze, so I thought I'd start with the easy case of line graphs:
The 1---2---3---4 is a Tom graph. A sequence for Tom is 2,3,3,2
Jerry's possible holes:
{1,2,3,4} Tom 2
{2,3,4} Tom 3
{1,3} Tom 3
{2} Tom 2
Caught
1---2---3---4---5 is also a Tom graph.
A sequence for Tom is 2,3,4,4,3,2
Any straight line graph is a Tom graph.
1---2---3-...--(n-1)---n
If Tom starts at 2 and works his way up to (n-1) he can narrow Jerry down to either even or odd. Hitting (n-1) and working his way back down will guarantee getting Jerry in hole 2 at the very least.
So the sequence goes 2,3,...,(n-1),(n-1),...,3,2.
The key here is Tom can force Jerry into a dead end.
If there's a cycle, Jerry can stay within it and may never be caught.
Say the cycle is size n (ignore any other branches).
1---2---3--...-n---1
If Tom tries any hole he no longer limits Jerry's possible holes because he could fill in from either direction. If Tom goes 2 for a first move, this no longer eliminates 1 from Jerry's possibilities for the second move because he could get there from n.
|
|
Posted by Jer
on 2021-02-20 13:11:06 |
A family of Tom graphs, Solution for part 1.
