Licence Info
Algorithmique Avancée
Projet de programmation
à faire en binomes
date d'echéance : vendredi 9 avril
Isomorphisme de graphes de degré maximum 2

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) ?




File translated from TEX by TTH, version 3.05.
On 19 Mar 2004, 14:09.