Introduction à la théorie des graphes

À partir des définitions générales sur de leur utilité algorithmique et pratique, nous allons raconter une histoire à priori simple dont les ramifications vont nous montrer de nombreuses facettes de la théorie des graphes.

Structure d'un graphe

Connexités :

Les plus simples des graphes connexes :

Aller d'un sommet à un autre

Parcourir tout le graphe

Graphes Eulérien

L'origine de la théorie des graphe :

Et une conséquence inattendue (exercice de modélisation) :

Graphes Hamiltoniens

Problèmes universels en théorie des graphes

Graphes planaires

Finissons cette introduction par une classe intéressantes de graphes, ceux qu'on peut dessiner.