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.
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.
LES ARTICLES
Le hasard au secours de la satisfaction
Christian Laforest
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é.
L'art de ne pas se croiser
Fabien Aoustin
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.
Trouver son chemin vite et bien
Christian Laforest
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 !
En bref : Satisfaire des contraintes sur les degrés des sommets
Christian LaforestQuel 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.
En bref : Questions de coloriage pour tout âge
Fabien AoustinEn 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.
Les dernières publications POLE
