Graphe simple

Un graphe simple est un graphe où il n'existe qu'une seule arête par paire de sommets distincts et aucun arête entre un sommet et lui même, 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