Math 2.0

definition

Hamiltonian cycle

Definition

Let GG be a graph. A Hamiltonian cycle of GG is a cycle in GG that contains every vertex of GG.

Remarks

A Hamiltonian path is a path that contains every vertex of GG. The names come from William Rowan Hamilton. His icosian game asks for a Hamiltonian cycle on the edges of a dodecahedron. To decide whether a graph has a Hamiltonian cycle is an NP-complete problem.

Explanations

L1 human

A Hamiltonian cycle is a round trip that visits every vertex exactly once. It is about visiting all vertices, while an Eulerian circuit is about using all edges.

What this node needs for W1
  • an inventory row: the row of the inventory that the node accounts for (0 of 1)

The writing levels say how complete the text of a node is. They do not measure its truth.

What this needs

To read this node, read these 6 nodes in this order. The foundations come first, and the list ends with this node.

Graph, definition, no evidence levelGraphdefinitionWalk, definition, no evidence levelWalkdefinitionTrail, definition, no evidence levelTraildefinitionCircuit, definition, no evidence levelCircuitdefinitionCycle, definition, no evidence levelCycledefinitionHamiltonian cycle, definition, no evidence levelHamiltonian cycledefinition
Each node uses the nodes above it. The colour of the bar on a box shows the evidence level, and the box also gives it as text. The list below has the same nodes.
  • no evidence level
  1. Graph definition
  2. Walk definition
  3. Trail definition
  4. Circuit definition
  5. Cycle definition
  6. Hamiltonian cycle definition

What depends on this

3 nodes use this node, directly or through other nodes.

Sources

  1. Web https://en.wikipedia.org/wiki/Hamiltonian_path, Definitions

What links here

Used by