Graphes : problèmes d'optimisation

Les graphes permettent de résoudre de nombreux problèmes d'optimisation. La coloration de graphes consiste à attribuer une couleur à chaque sommet de sorte que deux sommets adjacents n'aient pas la même couleur ; le nombre chromatique χ(G) est le nombre minimal de couleurs nécessaires. L'algorithme de Dijkstra trouve le plus court chemin dans un graphe pondéré (poids positifs) depuis un sommet source : on visite les sommets par distance croissante en mettant à jour les distances. Par exemple, dans un réseau routier, Dijkstra donne l'itinéraire le plus rapide. L'algorithme de Kruskal ou Prim construit un arbre couvrant minimal : on sélectionne les arêtes de poids croissant sans créer de cycle. Le théorème des quatre couleurs affirme que tout graphe planaire est coloriable avec au plus 4 couleurs, ce qui signifie qu'une carte géographique peut toujours être coloriée avec 4 couleurs seulement.