Graphe simple

Modèle:Autre4Modèle:À sourcer Un graphe simple est un graphe où il n'existe qu'une seule arête par paire de sommets, par opposition aux multigraphesModèle:,. 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

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