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.
Tutti gli articoli di questo dossier
Problemi di colorazione per tutte le età
Attribuendo colori — con i relativi vincoli — ai vertici di un grafo, si entra nell’affascinante universo dei problemi di colorazione dei grafi.
Cammino più breve: algoritmi sui grafi | Tangente
Il cammino più breve da A a B è sempre la linea retta? In genere sì, ma quando occorre seguire i percorsi definiti dalle strade e dagli incroci di una città, si impone un altro punto di vista. L’algoritmo di Dijkstra ci viene allora in grande aiuto!
Il caso in soccorso della soddisfazione
L’universo booleano è un piccolo mondo matematico in cui esistono soltanto due valori: Vero e Falso. Eppure, ottenere soddisfazione è già complicato! Per fortuna il caso viene in nostro aiuto: talvolta, scegliendo con il lancio di una moneta, ci si avvicina sorprendentemente al massimo cercato.
Gradi dei vertici di un grafo | Tangente
Qual è il grafo più piccolo che abbia un dato insieme di gradi? Quarant’anni fa, un articolo rispondeva a questa domanda in modo elegante e costruttivo.
L’arte di non incrociarsi
Artisti che usano la matematica: nulla di nuovo. Artisti che pongono problemi di ottimizzazione che i matematici ancora non sanno risolvere: questo sì che sorprende! Una congettura, apparentemente innocua, sulla rappresentazione dei grafi resiste infatti da cinquant’anni.