LISP -- Maîtrise d'Informatique

Examen 1996-1997, appel

Un graphe orienté est représenté par une liste l=(l1 l2 ... lk) où chaque élément li est à son tour une liste ayant à la première position un noeud du graphe et pour suffixe la liste de ses successeurs.

Deux graphes : le premier est représenté par la liste ((a b) (b c d) (c d) (d) (e)) et le deuxième par ((a b) (b c e) (c d) (d a) (e c)).

Écrire en LISP les fonctions suivantes :

1. (noeud_tous l) qui retourne la liste des noeuds du graphe représenté par la liste l.
   Ex. (noeud_tous l) renvoie (a b c d e) si l est ((a b) (b c d) (c d) (d) (e)).

2. (noeud_succ l) qui retourne la liste des noeuds du graphe représenté par la liste l ayant au moins un successeur.
   Ex. (noeud_succ l) renvoie (a b c) si l est ((a b) (b c d) (c d) (d) (e)).

3. (noeud x l) qui teste si x est un noeud (avec ou sans succeseur(s)) dans le graphe représenté par la liste l.

4. (ajouter x y l) qui retourne le graphe l auquel on a ajouté l'arc (x,y).
   Ex. Si l est ((a b) (b c d) (c d) (d) (e)) alors

   (ajouter 'a 'd l) renvoie ((a b d) (b c d) (c d) (d) (e)),

   (ajouter 'e 'c l) renvoie ((a b) (b c d) (c d) (d) (e c)),

   (ajouter 'u 'v l) renvoie ((a b) (b c d) (c d) (d) (e) (u v)).

5. (successeur1 x l) qui retourne les successeurs directs du noeud x dans le graphe l.
   Ex. Si l est ((a b) (b c d) (c d) (d) (e)) alors
   1. (successeur1 'a l) renvoie (b),
   2. (successeur1 'b l) renvoie (c d),
   3. (successeur1 'e l) renvoie ().

6. (succ_liste l1 l) qui retourne la liste (sans doublon) des successeurs directs des noeuds de la liste l1 dans le graphe l.

7. (succ x l) qui retourne (tous) les successeurs du noeud x dans le graphe l.

8. (chemin x y l) qui teste si y est un successeur de x dans le graphe l.

9. (hamiltonien x l) qui teste si le graphe l a un chemin hamiltonien commençant par le noeud x (un chemin hamiltonien passe une fois et une seule par tous les noeuds).

10. (hamiltonien2 l) qui teste si le graphe l a un chemin hamiltonien (commencent dans n'emporte quel noeud du graph).