Graphe simple

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur les redirections Cet article concerne la notion de graphe simple. Pour une introduction à la théorie des graphes, voir Graphe et Théorie des graphes.

Un graphe est dit simple s'il n'a pas de liens doubles ni de boucles. Dans un graphe simple, s'il existe un arc (pour un graphe orienté, une arête pour un graphe non orienté) du sommet x vers le sommet y, alors il n'existe aucun autre arc de x vers y (mais il peut exister un arc de y vers x si le graphe est orienté), et il n'existe aucun arc (resp. aucune arête) d'un sommet vers lui-même.

Graphe orienté simple[modifier | modifier le code]

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

  • V est appelé l'ensemble des sommets de G, et
  • A \subseteq \{ (x,y)\in V^2 \;/\; x\neq y\} est un ensemble de couples d'éléments de V appelé l'ensemble des arcs de G. La condition x\neq y interdit les boucles.

La lettre V est utilisée pour les sommets car en anglais, sommet se dit vertex (au pluriel vertices).

Exemple[modifier | modifier le code]

Un petit graphe orienté

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

  • 4 sommets V = \{ a, b, c, d\}
  • 3 arcs A = \{ (a, b), (b, c), (b, d)\}

On a (entre autres) :

  • Le degré entrant de b: d^-(b) = 1
  • Le degré sortant de b: d^+(b) = 2

Graphe non orienté simple[modifier | modifier le code]

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

  • V est appelé l'ensemble des sommets de G, et
  • E \subseteq \mathcal P_2(V) est un ensemble de paires d'éléments de V appelé l'ensemble des arêtes de G.

(Ici \mathcal P_2(V) désigne l'ensemble des parties de cardinalité 2 de V.)

La lettre E est utilisée pour les arêtes car en anglais, arête se dit edge.

Exemple[modifier | modifier le code]

Un petit graphe non-orienté

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

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

On a (entre autres) :

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

Voir aussi[modifier | modifier le code]