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 (mathématiques discrètes) et Théorie des graphes.
Un graphe non-orienté
Un graphe orienté

Graphe non orienté[modifier | modifier le code]

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.

Graphe orienté[modifier | modifier le code]

Un graphe orienté est un couple où :

  • est appelé l'ensemble des sommets, et
  • est un ensemble de couples d'éléments de appelé l'ensemble des arcs.

Un tel graphe est aussi appelé simple pour le distinguer des multigraphes, comme ci-dessus.

Le nombre d'arêtes entrant respectivement sortant d'un sommet est appelé le degré entrant respectivement le degré sortant de ce sommet.

Exemples[modifier | modifier le code]

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

Les sommets ont respectivement les degrés 1, 3, 1, 1.

  • 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
  • Les degré entrant dans sont respectivement 0,1,1,1
  • Les degré sortant de sont respectivement 1,2,0,0

Ce graphe est un graphe orienté acyclique.

Voir aussi[modifier | modifier le code]