Algèbre max-plus
Un article de Wikipédia, l'encyclopédie libre.
 |
Cet article est une ébauche concernant les mathématiques.
Vous pouvez partager vos connaissances en l’améliorant. (Comment ?).
|
Une algèbre max-plus est une algèbre sur les nombres réels avec munis des opération de maximum et d'addition.
Ainsi si on note 
l'opération maximum et 
l'addition, les opérations sont définies par:
On peut alors vérifier que ces opération sur les réels vérifient bien celles exigé par la structure d'algèbre.
Cette algèbre est liée à l'algèbre des dioïdes
[modifier] Application au calcul distances dans un graphe pour l'algèbre min-plus
On se place ici dans l'algèbre min-plus (l'opération max est remplacé par l'opération min).
On peut représenter un graphe à n sommets comme une matrice A = (ai,j) des distances entre chaque sommet: si le sommet i et lié avec le sommet j alors l'élément ai,j est égale au poids de l'arrête (i,j), si les sommets i et j ne sont pas reliées alors ai,j correspond à l'infini (bien entendu on a ai,i = 0).
Ainsi la distance entre i et j en passant par au plus un sommet est: minkestunsommet(ai,k + ak,j)
Ceci correspond au produit de matrice dans l'algèbre min-plus. Ainsi pour calculer la longueur d'un plus court chemin d'un sommet à un autre dans le graphe il suffit de calculer la puissance n de A dans cette algèbre.
