Projet sur les graphes en Prolog (langage de programmation logique)

Résumé du document

Rapport de projet concernant le Prolog (langage de programmation logique). Le sujet est d'implémenter divers algorithmes tels que "plus court chemin", "voyageur de commerce", "kruskal", "existence d'un chemin"... en langage Prolog.

Extraits

[...] Dans le cas de graphes non-orientés on peut interchanger point de départ et point d'arrivée (ils n'ont pas de sens puisque l'arc n'est pas orienté . ) 2.2 Chemin Un chemin existe entre 2 points s'il est possible de se rendre du point de depart au point d'arrivée en passant par les arêtes prédénies Voisins d'un noeud Les successeurs (ou voisins destination) d'un sommet sont l'ensemble des sommet pointés par un arc partant de ce sommet. Les predecesseurs(ou voisins Source) sont ceux ayant un arc pointant sur ce sommet Connexité d'un graphe Un graphe est connnexe si et seulement s'il existe un chemin pour tout couple de sommets du graphe. [...]

[...] liste des voisins source/destination/ tous d'un sommet connexité du graphe parcours du graphe et cout parcours de cout minimal création d'un arbre couvrant et cout Théorie des graphes 2.1 Representation graphique Il existe plusieurs representations des graphes : par les arcs(ou arêtes) ou par les noeuds(ou sommets). Ce projet impose la representation par les arcs. On doit donc denir un graphe comme une suite d'arcs composés d'un point de départ, d'un point d'arrivée et d'un poids (pour les graphes valués). [...]

[...] Ce mode de fonctionnement utilise donc une le FIFO dans laquelle il prend le premier sommet et place en dernier ses voisins non encore explorés. Si le graphe est cyclique, il faudra en outre marquer les sommets déjà visités pour que l'algorithme puisse se terminer Mettre le noeud de départ dans la le Retirer le noeud du début de la le pour l'examiner Mettre tous les voisins non examinés dans la le (à la Si la le n'est pas vide reprendre à l'étape 2. [...]

[...] Parcours total parcours parcours de coût minimum 2.6 arbre couvrant Ecriture des algorithmes en PROLOG 3.1 dénition des faits dénition des prédicats predicats sur les listes Existence de chemin, cout et liste des sommets parcourus listes des voisins connexité d'un graphe noeuds parcours arbre couvrant de valuation minimale conclusion Introduction Le but de ce projet est d'ecrire quelques algorithmes sur les graphes. On impose de decrire les graphes par des arcs orientés et valués. Les algorithmes suivant doivent etre implementés : existence d'un chemin entre 2 sommets du grpahe ? quel est-il ? [...]

[...] Un arbre de recouvrement est un arbre connexe avec n 1 arêtes. [...]