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

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

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

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

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.

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

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