Graphe simple

Page d'aide sur l'homonymie Cet article concerne la notion de graphe simple. Pour une introduction à la théorie des graphes, voir Graphe (mathématiques discrètes) et Théorie des graphes.
Un graphe non-orienté
Un graphe orienté

Graphe non orienté

Un graphe non orienté est un couple où :

  • est appelé l'ensemble des sommets de , et
  • est un ensemble de paires d'éléments de appelé l'ensemble des arêtes.

Un tel graphe est aussi appelé simple pour le distinguer des multigraphes, construction où il peut exister plusieurs arêtes pour une même paire de sommets. La notation E est fréquente par emprunt à l'anglais, où elle dénote l'ensemble des « edges ».

Le nombre d'arêtes issues d'un sommet est le degré de ce sommet.

Other Languages