... hamiltonien¹

Un cycle hamiltonien dans un graphe non-orienté $G=(S,A)$ contenant $n$ sommets $(S_1,S_2,\cdots,S_n)$ est une séquence de $n$ sommets où chaque sommet de $G$ est présent exactement une fois dans la séquence et où $\forall{i<n},\;(S_i, S_i+1) \in A$ et $(S_n,S_1) \in A$.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... cycle²

Définition d'un arbre.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... algorithme³

Il s'agit de l'algorithme de Prim. Il peut être optimisé en utilisant les tas de Fibonacci. Sa complexité devient alors $O(A+S\log{S})$.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... algorithme⁴

Il est décrit par Keld Helsgaun dans «An Effective Implementation of the Lin-Kernighan Traveling Salesman Heuristic«.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... montre⁵

cf. tableau 3 page

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... Karp⁶

Held et Karp «The traveling salesman problem and minimum spanning trees«.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... candidats⁷

On rappelera que pour la restriction par les distances il faut chercher dans les $20$ plus proches voisins suivant les problèmes.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.