Graphe simple

Pour les articles homonymes, voir Graphe.

On pourra se reporter à la page Théorie des graphes pour une définition du concept général de graphe, pour une explication du vocabulaire utilisé, et pour une représentation des objets définis ici.

Un graphe est dit simple s'il n'a pas de liens doubles ni de boucles. Dans un graphe simple , s'il existe un arc (pour un graphe orienté, une arête pour un graphe non orienté) du sommet x vers le sommet y, alors il n'existe aucun autre arc de x vers y (mais il peut exister un arc de y vers x si le graphe est orienté), et il n'existe aucun arc (resp. aucune arête) d'un sommet vers lui-même.

Graphe orienté simple

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

• V est appelé l'ensemble des sommets de G, et
• $A \subseteq V \times V$ est un ensemble de couples d'éléments de V appelé l'ensemble des arcs de G.

La lettre V est utilisée pour les sommets car en anglais, sommet se dit vertex (au pluriel vertices).

Exemple

Un petit graphe orienté

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

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

On a (entre autres) :

• Le degré entrant de b: d ⁻ (b) = 1
• Le degré sortant de b: d ⁺ (b) = 2

Graphe non-orienté simple

Un graphe simple non-orienté G est un couple (V,E) où :

• V est appelé l'ensemble des sommets de G, et
• $E \subseteq \mathcal P_2(V)$ est un ensemble de paires d'éléments de V appelé l'ensemble des arêtes de G.

(Ici $\mathcal P_2(V)$ désigne l'ensemble des parties de cardinalité 2 de V.)

La lettre E est utilisée pour les arêtes car en anglais, arête se dit edge.

Exemple

Un petit graphe non-orienté

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

• 4 sommets V = {a,b,c,d}
• 3 arêtes E = {{a,b},{b,c},{b,d}}

On a (entre autres) :

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

Voir aussi

• Théorie des graphes
• Lexique de la théorie des graphes