Révision

un graphe est un “objet” mathématique très utilisé en informatique.
un graphe possède des sommets et des arêtes : un graphe G est un couple G = (V,E) avec V un ensemble de sommets et E un ensemble d'arêtes
les graphes sont utilisés par exemple pour modéliser les réseaux sociaux ou encore les cartes routières (il existe beaucoup d’autres exemples)
on trouve 2 types de graphes : les graphes non orientés et les graphes orientés (voir cours). Dans le cas des graphes orientés on parlera d’arcs à la place d’arêtes
on trouve des graphes dits pondérés : à chaque arête (ou arc) on associe une valeur (voir le cours pour un exemple)
définitions :
- Une chaîne est une suite d'arêtes consécutives dans un graphe, un peu comme si on se promenait sur le graphe. On la désigne par les lettres des sommets qu'elle comporte.
- Un cycle est une chaîne qui commence et se termine au même sommet.

Il existe deux méthodes permettant d'implémenter un graphe : les matrices d'adjacences et les listes d'adjacences (voir le cours)
le choix se fait en fonction de la densité du graphe, c'est-à-dire du rapport entre le nombre d'arêtes et le nombre de sommets. Pour un graphe dense on utilisera plutôt une matrice d'adjacence.
certains algorithmes travaillent plutôt avec les listes d'adjacences alors que d'autres travaillent plutôt avec les matrices d'adjacences. Le choix doit donc aussi dépendre des algorithmes utilisés (nous aurons très prochainement l'occasion d'étudier plusieurs de ces algorithmes).

vous devez être capable de déterminer la matrice d’adjacence d’un graphe à partir d’un schéma (et vice versa)
vous devez être capable de déterminer la liste d’adjacence d’un graphe à partir d’un schéma (et vice versa)