Graphe orienté

Question posée au conctrôle continu du 22 juin 2000

Il est aisément démontrable que lorsque l'on élève un nombre N au carré, les deux derniers chiffres du résultat ne dépendent que des deux derniers chiffres de N. Ainsi, un nombre se terminant par 05 aura toujours son carré se terminant par 25 ( 105->11025, 1905->3629025 ).

L'on peut donc définir une application reliant chacun des nombres de 00 à 99 à un autre de ces nombres, correspondant à la valeur de son carré modulo 100. Ceci compose bien entendu un graphe orienté...

1. Considérant que chacun des noeuds est l'origine d'un et un seul arc, déterminez la structure de données la plus simple adaptée à la représentation des arcs de ce graphe.

La propriété précédente amène logiquement ceci :

• puisqu'un noeud a au plus un successeur (en fait, exactement un), l'on peut définir en suivant les arcs (c'est-à-dire en réitérant le calcul) un chemin unique qui en est issu;
• puisque tous les noeuds ont au moins un successeur, ce chemin aboutit obligatoirement à un cycle (le nombre de noeuds étant limité).

L'on aimerait donc associer à chaque noeud la "séquence terminale" (cycle) qui lui correspond.

2. Écrivez une fonction imprimant, pour un noeud passé en paramètre, les noeuds composant le cycle terminal qui lui est associé.

Pensez que chaque composante du graphe ne comporte qu'un seul cycle; rappelez-vous qu'un cycle est un cas particulier de composante fortement connexe...

Solution

Site Hosting: Bronco