Graphes

Un graphe est constitué d’un ensemble de points reliés par des arcs.

• Un point du graphe est appelé un sommet.
• Un arc reliant deux sommets est appelé une arête.
• Lorsque ces arêtes sont munies d’un sens, on dit que le graphe est orienté.
• Lorsque ces arêtes sont affectées de coefficients positifs, on dit que le graphe est pondéré et le coefficient associé à une arête est appelé le poids de l’arête.
• Lorsque la somme des poids des arêtes issues de chaque sommet est égale à 1, on dit que le graphe est un graphe probabiliste.