Pour les articles homonymes, voir Graphe simple (homonymie).
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.
Graphe simple orienté
Un graphe simple orienté G est un couple
(V,A) où :
- V est appelé l'ensemble des sommets de G, et
- A ⊆ V × V est un ensemble de couples d'éléments de V appelé l'ensemble des arcs de G.
Graphe simple non-orienté
Un graphe simple non-orienté G est un couple
(V,E) où :
- V est appelé l'ensemble des sommets de G, et
- E ⊆ P 2 (V) est un ensemble de paires d'éléments de V appelé l'ensemble des arêtes de G.
(Ici P 2 (V) désigne l'ensemble des parties de cardinalité 2 de V.)