Hamiltonpad
Een Hamiltonpad is een pad langs knooppunten in een graaf waarbij elk knooppunt precies één keer op het pad ligt. Een gesloten Hamiltonpad noemt men een Hamiltoncykel of Hamiltoncircuit. De naam Hamiltonpad komt van de Ierse wiskundige Sir William Rowan Hamilton (1805-1865).
Een graaf die een Hamiltoncircuit bevat noemt men een Hamiltoniaanse graaf of Hamilton-graaf. Elke cykel-graaf is Hamiltoniaans, evenals elke volledige graaf met 3 of meer knopen.
Het bepalen of er een Hamiltonpad of Hamiltoncircuit bestaat in een gegeven graaf, die gericht of niet-gericht kan zijn, is een fundamenteel probleem in de grafentheorie. Dit Hamiltonpadprobleem is NP-volledig. Een speciaal geval van het Hamiltonpadprobleem is het handelsreizigersprobleem; dat komt neer op het vinden van het kortste Hamiltoncircuit in een gerichte graaf waarin de kanten een gewicht (afstand) hebben.
