- Max plus
-
Algèbre max-plus
Une algèbre max-plus est une algèbre sur les nombres réels munie 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
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 (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 matriciel 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.
Portail des mathématiques
Catégorie : Algèbre
Wikimedia Foundation. 2010.
