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.
Implémentations des graphes
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).
Ce qu’il faut savoir faire
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)