Rappel deux graphes sont isomorphes si l'un peut être
transformé dans l'autre par une permutation des sommets.
Objet lire deux graphes, vérifier que leur degré
maximum est au plus 2 et décider si les deux sont isomorphes
Entrées un entier n £ 1000,
(les deux graphes auront n sommets numérotés de 1 à n),
des paires i j représentant une arête entre les
sommets i et j du premier graphe,
une paire 0 0,
des paires i j représentant une arête entre les
sommets i et j du deuxième graphe,
une paire 0 0,
Deux fichiers d'entrées seront fournis, l'un de deux graphes isomorphes
et l'autre de deux graphes non-isomorphes.
Bien sûr vous allez tester votre programme avec d'autres paires.
Sorties un message d'erreur si les entrées ne sont pas conformes
ou une ligne disant si les deux graphes sont isomorphes ou non.
A soumettre par mail à votre reponsable de TD le(s) fichier(s)
qui contiennent les sources (en C);
sur papier: un document expliquant l'algorithme utilisé, et une
analyse du temps de calcul (n'essayez pas d'être plus précis
que O( )) ;
pensez-vous que ce temps est optimal (à O( ) près) ?