Licence Info de Gestion
Algorithmes Avancée
Projet de programmation à faire en binômes
Chemins Eulériens 
Objet Décider si un graphe possède un chemin eulérien entre deux sommets (c'est-à-dire un chemin reliant les deux sommets et passant une seule fois par chaque arête) et afficher un tel chemin s'il en existe un. 
Rappel Un graphe G a un chemin eulérien entre deux sommets distincts A et Z, ssi A et Z sont de degré impair, tous les autres sommets sont de degré pair et G est connexe (éventuellement avec des sommets isolés de degré 0).
Entrées Le programme va lire le graphe dans le format suivant:
un entier n <= 1000, (le graphe aura n sommets numérotés de 1 à n),
des paires i j représentant une arête entre les sommets i et j
une paire 0 0 (marquant la fin du fichier),
on cherche un chemin eulérien du sommet 1 au sommet n. 
Des fichiers d'entrées seront fournis, l'un d'un graphe possédant un chemin et d'autres sans chemin. Bien sûr vous allez tester votre programme avec d'autres graphes.
Astuce Quand on sait qu'il existe un chemin eulérien de A à Z, on sait que le chemin peut commencer par A-B (B un voisin de A), s'il existe un chemin eulérien de B à Z dans le graphe obtenu en supprimant l'arête (A,B).
Sorties une ligne disant s'il existe un chemin ou non;
si oui, la liste des numéros des sommets dans l'ordre d'un chemin.
A soumettre par mail à votre reponsable de TD le(s) fichier(s) qui contiennent les sources (en C);
dans un fichier (format .ps, .pdf ou texte ASCII) joint à votre mail ou 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) ?