Glossary

Définitions

• Un graphe non orienté $G$ est déterminé par la donnée :
  • d'un ensemble fini $S$ dont les éléments sont appelés sommets ;
  • d'un ensemble $U$ de parties de $S$ à un ou deux élément(s) :
    • lorsqu'une de ces parties est constituée de deux sommets distincts, cette partie est appelée arête de $G$,
    • sinon (lorsque les deux sommets sont confondus), cette partie est appelée boucle.
  L'ordre d'un graphe $G$ est le nombre de sommets de ce graphe.
  Si $u=\{s;t\}$ est une arête du graphe $G$, on dit que les sommets $s$ et $t$ sont adjacents et qu'ils constituent les extrémités de l'arête $u$.
• Le degré d'un sommet $s$ d'un graphe non orienté $G$ est le nombre d'arêtes ou de boucles dont une extrémité est $s$.