Editing 230: Hamiltonian

Jump to: navigation, search

Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.

The edit can be undone. Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
Latest revision Your text
Line 8: Line 8:
  
 
==Explanation==
 
==Explanation==
βˆ’
[[Cueball]], presumably in class, decides that the subject of {{w|Mathematical_optimization|optimizing}} {{w|Routing|routing algorithms}} is not important in the larger context of life and love. However, he later realizes while in bed with [[Megan]] that there is a flaw in the proof presented, and suddenly wants to focus on the mathematics again, in a humorous reversal of his position about what is meaningful.
+
[[Cueball]], presumably in class, decides that the subject of Hamiltonian circuits in graphs is not important in the larger context of life and love. Later, however, he realizes there is a flaw in the proof presented, while in bed with [[Megan]], and suddenly wants to focus on the mathematics, in a humorous reversal of his position about what is meaningful.
  
βˆ’
In graph theory, a {{w|Hamiltonian_path|Hamiltonian path}} is a path that connects all the vertices (nodes) and passes through each one exactly once. (Think connect the dots with rules!) A Hamiltonian cycle is a Hamiltonian path such that the final vertex is adjacent to the initial one (intuitively, it "begins and ends with the same vertex," but recall that paths are required to only pass through each vertex once). The presenter is using graph theory to optimize a routing algorithm by solving a {{w|Hamiltonian_path_problem|Hamiltonian path problem}}. Cueball's realization is that the proof he had followed in part actually requires a Hamiltonian cycle, not just a path, so the presenter's proof of the existence of a Hamiltonian path is insufficient to solve the problem.
+
In graph theory, a {{w|Hamiltonian_path|Hamiltonian}} is a traceable path that connects all the vertices (nodes) by passing through each one exactly once (Think connect the dots with rules!). If this is not possible, then it can be said that no Hamiltonian exists for the given set of vertices. A Hamiltonian cycle is a Hamiltonian where the path begins and ends at the same node. The professor is using the graph theory to optimize some algorithm by solving a {{w|Hamiltonian_path_problem|Hamiltonian path problem}}. He meant to say "Hamiltonian Cycle", but instead said only "Hamiltonian Path".
  
βˆ’
The title text plays on a dual interpretation of bidirectional: just as any graph cycle can be traversed in two directions, a change in perspective can be traversed in two directions (from mathematics to love, and then from love to mathematics).
+
The title text explains that the Hamiltonian Cycle can be solved in two different directions around the cycle.
  
 
==Transcript==
 
==Transcript==

Please note that all contributions to explain xkcd may be edited, altered, or removed by other contributors. If you do not want your writing to be edited mercilessly, then do not submit it here.
You are also promising us that you wrote this yourself, or copied it from a public domain or similar free resource (see explain xkcd:Copyrights for details). Do not submit copyrighted work without permission!

To protect the wiki against automated edit spam, we kindly ask you to solve the following CAPTCHA:

Cancel | Editing help (opens in new window)

Templates used on this page:

Retrieved from "https://www.explainxkcd.com/wiki/index.php/230:_Hamiltonian"