Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ».
Un graphe simple est un graphe où il n'existe qu'une seule arête par paire de sommets, par opposition aux multigraphes[1],[2]. Il peut être orienté ou non-orienté.
Graphe simple non orienté
Un graphe simple non orienté est un couple où :
est un ensemble non vide (les sommets du graphe), et
est un ensemble de parties de à deux éléments (les arêtes du graphes).
Graphe simple orienté
Un graphe simple orienté est un couple où :
est un ensemble non vide (les sommets du graphe), et
est une partie du produit cartésien (les arcs du graphe).
Exemples
Exemple de graphe simple non orienté
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é
Le schéma ci-contre représente un graphe orienté, composé de :
4 sommets
3 arcs
Les degrés entrant dans sont respectivement 0,1,1,1
↑Jean-Claude Fournier, Théorie des graphes et applications : avec exercices et problèmes, Lavoisier, , 332 p. (ISBN978-2-7462-3215-0, lire en ligne), p. 21
↑Irène Larramendy Valverde et Alain Marie-Jeanne, Introduction à la théorie des graphes : Cours et exercices corrigés, Ellipses, , 240 p. (ISBN978-2-3400-2844-9, lire en ligne), p. 5