Dans ce cours, nous chercherons à résoudre des problèmes, tels que le chemin le plus court, d’ordonnancement et d’autres, à l’aide des graphes. Nous devons donc être capables de bien formulé notre problème afin de bien choisir notre représentation par les graphes et ainsi répondre à notre problématique.
Notre représentation par les graphes peut être différente de la réalité et l’on a les propriétés suivantes :
Un graphe non orienté possède des nœuds, des arêtes et on peut y trouver des chaînes ou des cycles. Un graphe orienté possède des nœuds, des arcs, et on peut y trouver des chemins ou des circuits.
L’ordre d’un graphe est son nombre de nœuds tandis que sa taille est son nombre d’arêtes.
On parle de p-graphe ou de multigraphe. Par exemple, un 2-graphe possède au plus 2 arêtes entre 2 nœuds.
Un graphe est valué si ses arêtes possèdent une valeur, il est étiqueté / labellisé si ses nœuds possèdent des valeurs.
Pour les graphes orientés :
Degré sortant / entrant : nombre d’arcs sortants, ou respectivement entrants, d’un sommet. Pour un graphe en entier, on peut parler de degré max ou min.
Si tous les sommets d’un graphe possèdent le même degré k, on parle de graphe régulier de degré k.
Sommets adjacents : 2 sommets sont adjacents s’ils sont reliés par un arc
Voisinage : l’ensemble des sommets adjacents à un sommet
Successeur / prédécesseur : un sommet atteignable, ou respectivement atteint, par le sommet observé
Note : ces définitions s’adaptent au cas non orienté
Module : ensemble de sommets d’un graphe qui ont les mêmes voisins à l’extérieur de cet ensemble.
Arbre : un graphe connexe sans cycle
Forêt : un graphe sans cycle (un ensemble d’arbre)