Hamiltonian Graphs
Hamiltonian graphs are often used to solve problems similar to Traveler's problems, which asks: A traveler wishes to visit a number of cities. Can a tour be found which visits
each city only once?
This type of problem focuses on finding a cycle which includes every vertex of a graph. As we saw from the section "Development", "A Voyage around the World" is one such problem.
One other problem that we talking about in "The Beginning" was a Knight's Tour problem, both of these are solved using Hamiltonian Graphs. For example, with the Knight's Tour problem,
each square can be a vertex, and then the edges between them are the paths of the knight.
Another famous problem that can be solved with Hamiltonian graphs is The Traveling Salesman Problem.This problem asks us to find a path to visit a number of cities, return
home (to the starting point), with every city being visited once and minimizing the total distance covered.
One other problem type that is found in Hamiltonian Graphs are tournaments. Tournaments are digraphs that are complete. These can be used to record winners where each player play each of
the others (a round-robin tournament). This website will be useful for generating an adjacency matrix, which you will need to explore the following applet.
http://users.cecs.anu.edu.au/~bdm/data/digraphs.html
If you would like to know more about how this applet works and what it tells you you can read this paper Combinatorial Games
on Graphs , starting on page 57. Another paper to read about what Kings are is this paper Every Vertex A King .
