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.

LES ARTICLES

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é.


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 : Questions de coloriage pour tout âge

Fabien Aoustin

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.



En bref : Satisfaire des contraintes sur les degrés des sommets

Christian Laforest

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.



Les dernières publications POLE