next up previous contents index
suivant: Graphes orientés monter: Variations sur les graphes précédent: Variations sur les graphes   Table des matières   Index


Graphes simples

Un graphe simple est un graphe n'ayant pas de multi-arête (plusieurs arêtes différentes avec les mêmes extrémités).

Un tel graphe est parfois utile lorsque l'application manipule des relations simples entre les sommets. Un exemple d'une telle application peut être le réseau d'une ligne aérienne. Pour déterminer comment aller d'un aéroport $A$ à un aéroport $B$, il suffit de savoir si deux aéroports sont reliés par une route directe.

Parfois, on exige pour qu'un graphe soit simple, l'absence de boucles.