Graphe simple

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.

Cet article ne cite pas suffisamment ses sources (mars 2024).

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

En pratique : Quelles sources sont attendues ? Comment ajouter mes sources ?

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é[modifier | modifier le code]

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é[modifier | modifier le code]

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[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 ${\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é[modifier | modifier le code]

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[modifier | modifier le code]

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

Notes et références[modifier | modifier le code]

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