Cycle hamiltonien dans un Graphe en moins de 128 mots

Un cycle Hamiltonien est un cycle qui contient tous les sommets du graphe.

Il n’y a pas d’algorithme général (càd valable pour n’importe quel graphe) et efficace (càd pas d’algorithme dans le nombre d’étape de calcul soit un polynôme de la taille du graphe) pour trouver si il y a un cycle hamiltonien dans un graphe.

Cycle hamiltonien source wikipedia

Condition de DIRAC : Si pour tous les sommets u du graphe G degré(u) >= n /2 alors G contient un cycle hamiltonien

Condition de ORE : Si pour toute paire u et v de non voisins deg(u) + deg(v) >=n alors G contient un cycle hamiltorien

Si un graphe vérifie la condition de DIRAC alors il vérifie la condition de ORE (la réciproque est fausse).

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée.