Théorie des graphes/Présentation de la leçon

En mathématiques et en informatique, un graphe est la donnée d'un ensemble des sommets et d'un ensemble d'arêtes qui relient deux à deux certains des sommets. Un graphe peut être :

• orienté ou non, selon que l’on munit ou non les arêtes d'un sens de parcours ;
• pondéré ou non, selon que l’on affecte à chaque arête une « valeur » ou pas.

D'autres variations existent comme par exemple les graphes « mixtes » où seules certaines arêtes sont orientées. Les graphes sont très présents en informatique, ils sont notamment sous-jacents à la théorie des automates.