Notions de graphe

Exercice

Construire un graphe orienté dont les sommets sont les entiers compris entre 1 et 12 et dont les arcs représentent la relation «être diviseur de».

Plus court chemin dans un graphe

Algorithme de résolution

Énumération de tous les chemins possibles

• Étape 1 : Énumérer tous les chemins possibles entre le sommet origine et le sommet destination, et calculer leurs longueurs.
• Étape 2 : Retenir le chemin le plus court.

Cependant, si le nombre de chemins élémentaires est bien fini, il peut être extrêmement grand, de l'ordre de n! sur un graphe d'ordre n. Prenons un exemple :

• Sur un graphe de seulement 20 sommets :
  • En supposant que trouver un chemin et calculer sa longueur puissent se faire en une seule opération.
  • Sur un ordinateur pouvant effectuer 1 milliard d'opérations par seconde, il faudrait patienter 77 ans pour obtenir le meilleur trajet.
• Sur un graphe de 25 sommets :
  • Le temps nécessaire serait d'environ 490 millions d'années pour obtenir le résultat.