Graphes et algèbre (max,+).

Certains problèmes de graphes ont des liens forts avec les algèbre (min,+) ou (max,+), parfois appelées algèbres exotiques ou tropicales. Pour ces algèbres qui sont en fait des semi-anneaux où min (ou bien max) et + remplacent respectivement + et ×, une algèbre linéaire spécifique a été développée, avec notamment des applications aux réseaux de Petri, en évaluation de performances des réseaux et en automatique.

L'objectif de ce sujet est d'illustrer les liens entre ces algèbres et des problèmes de graphes. Les points suivants proposent des pistes :

Quelques références (pas exhaustif).
 

Retour à la page des sujets.