Graphe simple

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é

Un graphe simple non orienté est un couple ${\displaystyle G=(V,E)}$ où :

• ${\displaystyle V}$ est un ensemble non vide (les sommets du graphe), et
• ${\displaystyle E\subseteq \{\{x,y\}\mid x,y\in V\}}$ est un ensemble de parties de ${\displaystyle V}$ à deux éléments (les arêtes du graphes).

Graphe simple orienté

Un graphe simple orienté

Un graphe simple orienté est un couple ${\displaystyle G=(V,A)}$ où :

• ${\displaystyle V}$ est un ensemble non vide (les sommets du graphe), et
• ${\displaystyle A\subseteq \{(x,y)\mid x,y\in V\}}$ est une partie du produit cartésien ${\displaystyle V\times V}$ (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 ${\displaystyle V=\{a,b,c,d\}}$
• 3 arêtes ${\displaystyle E=\{\{a,b\},\{b,c\},\{b,d\}\}}$

Les sommets ${\displaystyle a,b,c,d}$ ont respectivement les degrés 1, 3, 1, 1.

• Le degré de b: ${\displaystyle d(b)=3}$

Exemple de graphe simple orienté

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

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

• Les degrés entrant dans ${\displaystyle a,b,c,d}$ sont respectivement 0,1,1,1
• Les degrés sortant de ${\displaystyle a,b,c,d}$ sont respectivement 1,2,0,0

Ce graphe est un graphe orienté acyclique.

Voir aussi

• Théorie des graphes
• Graphe orienté
• Graphe non orienté
• Graphe (type abstrait)
• Lexique de la théorie des graphes

Notes et références

1. Jean-Claude Fournier, Théorie des graphes et applications : avec exercices et problèmes, Lavoisier, 2011, 332 p. (ISBN 978-2-7462-3215-0, lire en ligne), p. 21
2. Irène Larramendy Valverde et Alain Marie-Jeanne, Introduction à la théorie des graphes : Cours et exercices corrigés, Ellipses, 2018, 240 p. (ISBN 978-2-3400-2844-9, lire en ligne), p. 5