Graphe simple

Un graphe simple est un graphe où il n'existe qu'une seule arête par paire de sommets distincts et aucune arête entre un sommet et lui même, par opposition aux multigraphes,. Il peut être orienté ou non-orienté.

Graphe simple non orienté

Un graphe simple non-orienté

Un graphe simple non orienté est un couple G=(V,E) où :

Graphe simple orienté

Un graphe simple orienté

Un graphe simple orienté est un couple G=(V,A) où :

Exemples

Exemple de graphe simple non orienté

Le schéma ci-contre représente un graphe non-orienté, composé de :

  • 4 sommets V={a,b,c,d}
  • 3 arêtes E={{a,b},{b,c},{b,d}}

Les sommets a,b,c,d ont respectivement les degrés 1, 3, 1, 1.

  • Le degré de b: d(b)=3

Exemple de graphe simple orienté

Le schéma ci-contre représente un graphe orienté, composé de :

  • 4 sommets V={a,b,c,d}
  • 3 arcs A={(a,b),(b,c),(b,d)}
  • Les degrés entrant dans a,b,c,d sont respectivement 0,1,1,1
  • Les degrés sortant de a,b,c,d sont respectivement 1,2,0,0

Ce graphe est un graphe orienté acyclique.

Voir aussi