Graphe simple

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie 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é est un couple où :

  • est appelé l'ensemble des sommets de , et
  • est un ensemble de couples d'éléments de appelé l'ensemble des arcs de . La condition 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
  • 3 arcs

On a (entre autres) :

  • Le degré entrant de b:
  • Le degré sortant de b:

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

Un graphe simple 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 de .

(Ici désigne l'ensemble des parties de cardinalité de .)

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
  • 3 arêtes

On a (entre autres) :

  • Le degré de b:

Voir aussi[modifier | modifier le code]