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 simple non-orienté
Un graphe simle orienté

Un graphe non orienté est dit simple s'il n'a pas d'arêtes doubles. Formellement, 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 .

Un graphe simple orienté est un graphe orienté sans boucle et sans arc et son inverse. Formellement, un graphe simple orienté est un couple où :

  • est appelé l'ensemble des sommets de , et
  • et est un ensemble de couples d'éléments de appelé l'ensemble des arcs de . La condition interdit les boucles. La condition interdit que contienne un arc et son inverse.

Un graphe simple orienté correspond à une relation binaire irréflexive et asymétrique

Exemple de graphe simple non orienté[modifier | modifier le code]

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

  • 4 sommets
  • 3 arêtes

On a (entre autres) :

  • Le degré de b:

Exemple de graphe simple orienté[modifier | modifier le code]

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

  • 4 sommets
  • 3 arcs

On a (entre autres) :

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

Ce graphe est un graphe orienté acyclique. Mais un graphe simple orienté peut avoir un circuit.

Voir aussi[modifier | modifier le code]