James Bond — Graph Theory
If you have every wondered if you could watch every James Bond movie without watching the same actor play James Bond in a row or how many different possibilities there were, you’ve unsuspectedly ventured into graph theory. Graph theory is basically the study of connected things. These can be bridges, social networks, or in this post’s case, James Bond films.
This is an example of what a graph is. There are nodes/vertices [the James Bond films] and edges [the connection between films that don’t have the same actor playing Bond]. This can be abstracted to many situations especially traveling salespeople. The graph above has six Bond films each one being connected to others that don’t have the same actor portraying Bond. Goldeneye and Die Another Day are connected to the other four non-Pierce Brosnan films, but not with each other.
When this is extended to all 23 films the graph becomes much busier.
The best way, I found to display this was in a circular graph with all the neighboring nodes being connected. To reiterate, this graph is drawn so only Bond films with different actors playing Bond are connected. Right away, you can clearly see that there is a way to watch all 23 films with the prescribed condition, since you can trace a circle through all 23 films on the graph.
The path created by watching every film without repeating has a named; it’s called a Hamiltonian path. And there are many, many different ways to achieve this in this graph. Unfortunately, there isn’t a succinct algorithm to find all of them short of programing an exhaustive search. Since I didn’t know the best way to approach this, I created a stochastic approach [Python code] to finding some of the possible Hamiltonian paths. A stochastic process uses randomness injected into an algorithm. The first Bond film in the path was selected at random, and so were subsequent films (nodes) that weren’t already visited.
This is just one of the possible Hamiltonian paths to fulfill the requirements of this post. The path goes [Tomorrow Never Dies, Live and Let Die, From Russia with Love, The Spy Who Loved Me, Goldfinger, Die Another Day, Moonraker, Dr. No, The Man with the Golden Gun, Casino Royale, GoldenEye, Skyfall, You Only Live Twice, License to Kill, Quantum of Solace, The Living Daylights, On Her Majesty’s Secret Service, For Your Eyes Only, The World Is Not Enough, Octopussy, Diamonds Are Forever, A View to a Kill, Thunderball]
Unfortunately, the only way to find the total number of paths for this problem is an exhaustive search. I’m going to table that as a problem for later. I looped the stochastic Hamiltonian path program nearly 1 million times and found 757,733 different Hamiltonian path permutations. Practically, if I did figure out how many different unique paths there are, it will be another really high number.
What I do find interesting that until the algorithm is run enough times to start repeating paths, it will find a complete path [23 is a complete path — 23 total Bond films] about 75% of the time. Which means you have a pretty good chance to watch the movies in real life if you just pick randomly. I’d actually say you’d have a better than 75% chance because you can look ahead and use some reason so you don’t leave two of the same era films for last. For example, you could see you have three films left: 2 Sean Connery and 1 Roger Moore. You wouldn’t want to watch the Roger Moore film first, you’d logically choose the Sean Connery film. The best strategy I think would be to hold off on the George Lazenby film till the end in case you need bailed out. Conversely, you could do worse than random if you were biased in your choice of films. For example, if you prefer more recent films and alternated watching Pierce Brosnan and Daniel Craig films first, now you have fewer choices sooner.