Optimum et théorie des graphes
La notion d'optimum évoque souvent celle de maximum ou de minimum d'une fonction qui, comme un fluide, évoluerait de manière continue, et même dérivable. L'arsenal de l'analyse et du calcul différentiel s'impose alors à l'esprit. Mais l'optimisation concerne aussi, souvent, des quantités ne pouvant prendre qu'un nombre fini ou dénombrable de valeurs. Si l'éventail des techniques issues de l'analyse n'est alors plus d'aucun secours, les mathématiques discrètes et la théorie des graphes prennent le relais. C'est l'ordinateur, machine séquentielle la mieux adaptée aux environnements combinatoires, qui sera alors, le plus souvent, mis à contribution pour résoudre les problèmes d'optimum.
Tous les articles de ce dossier
PodcastQuestions de coloriage pour tout âge
En attribuant des couleurs (avec leurs ensembles de contraintes) aux sommets d'un graphe, on entre dans l'univers passionnant des problèmes de coloration de graphes.
Plus court chemin : algorithmes de graphes | Tangente
Le plus court chemin de A à B est-il toujours la ligne droite ? En général oui, mais lorsqu'il faut suivre les voies délimitées par les routes et les carrefours d'une ville, un autre point de vue s'impose. L'algorithme de Dijkstra nous est alors d'un grand secours !
Le hasard au secours de la satisfaction
L'univers booléen est un petit monde mathématiques où deux valeurs seulement existent : Vrai et Faux. Pourtant, il est déjà compliqué d'obtenir satisfaction ! Heureusement, le hasard vient à notre secours : parfois, en choisissant à pile ou face, on tombe étonnamment près d'un maximum recherché.
Contraintes de degrés des sommets d'un graphe | Tangente
Quel est le plus petit graphe ayant un ensemble donné de degrés ? Il y a quarante ans, un article répondait de manière élégante et constructive à cette question.
L'art de ne pas se croiser
Des artistes qui utilisent des mathématiques : rien de nouveau. Des artistes qui posent des questions d'optimisation que les mathématiciens ne savent toujours pas résoudre : voilà qui étonne ! Une conjecture, anodine en apparence, sur la représentation des graphes résiste en effet depuis cinquante ans.