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 $G=(V,E)$ où :

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

Graphe simple orienté

Un graphe simple orienté

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

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

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

Le degré de b: $d(b)=3$

Exemple de graphe simple orienté

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

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

Les degrés entrant dans $a,b,c,d$ sont respectivement 0,1,1,1
Les degrés sortant de $a,b,c,d$ sont respectivement 1,2,0,0

Ce graphe est un graphe orienté acyclique.

Voir aussi

Notes et références

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
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

Portail des mathématiques
Portail de l'informatique théorique

Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons – Attribution – Partage à l’identique. Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.

[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