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) :

Codons tout ça :

Graphes Hamiltoniens

Problèmes universels en théorie des graphes

TBD prérequis NP algorithmie.

Graphes planaires

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

thm des 4 couleurs qui est le 1er théorème assisté par ordinateur (pas une IA, c'est la preuve qui est un algorithme) tbd