Mathématiques tropicales

Un article de Wikipédia, l'encyclopédie libre.
(Redirigé depuis Algèbre max-plus)
Aller à : navigation, rechercher

Les mathématiques tropicales, ou géométrie tropicale, sont une branche des mathématiques correspondant à l'étude d'un système modifié grâce à la redéfinition de l'addition et de la multiplication (et conséquemment d'autres opérations). Les mathématiques tropicales sont généralement définies grâce au minimum et à l'addition (algèbre min-plus)[1], mais le terme est parfois utilisé pour désigner l'algèbre max-plus, définie grâce au maximum et à l'addition[2].

Les mathématiques tropicales furent dénommées ainsi en l'honneur de leur inventeur brésilien, Imre Simon.

Semi-corps max-plus[modifier | modifier le code]

L'ensemble R des nombres réels, muni des opérations de maximum et d'addition, possède une structure de semi-corps commutatif.

Opérateurs mathématiques[modifier | modifier le code]

Définitions des opérateurs[modifier | modifier le code]

  • On définit l'addition tropicale \oplus par :
    a \oplus b = \max(a,b).

Le résultat de l'addition tropicale de deux nombres est donc le maximum de ceux-ci. Ainsi, 2 \oplus 3 = \max(2,3) = 3.

  • On définit la multiplication tropicale (ou produit tropical) \odot (ou \otimes) par :
    a \odot b = a + b.

Le résultat de la multiplication tropicale de deux nombres est donc la somme usuelle de ceux-ci. Ainsi, 2 \odot 3 = 2 + 3 = 5.

Propriétés[modifier | modifier le code]

Propriétés des opérations tropicales comparées à celles des opérations usuelles
Dans \R Addition tropicale Addition Multiplication tropicale

(mêmes propriétés que l'addition usuelle)

Multiplication
Commutativité Oui

a \oplus b = b \oplus a
car \max (a,b)=\max (b,a)

Exemple : 2 \oplus 3 = 3 et  3 \oplus 2 = 3

Oui

a + b = b + a

Exemple : 2 + 3 = 5 et 3 + 2 = 5

Oui

a \odot b = b \odot a
car a + b = b + a

Exemple : 2 \odot 3 = 5 et  3 \odot 2 = 5

Oui

a x b = b x a

Exemple : 2 x 3 = 6 et 3 x 2 = 6

Associativité Oui

(a \oplus b) \oplus c = a \oplus (b \oplus c) = a \oplus b \oplus c

Exemple : (2 \oplus 5) \oplus 6 = 5 \oplus 6 =6
2 \oplus (5 \oplus 6) = 2 \oplus 6 =6
2 \oplus 5 \oplus 6 = 6

Oui

(a + b) + c = a + (b + c) = a + b + c

Exemple:
(2 + 5) + 6 = 13
2 + (5 + 6) = 13
2 + 5 + 6 = 13

Oui

(a \odot b) \odot c = a \odot (b \odot c) = a \odot b \odot c

Exemple : (2 \odot 5) \odot 6 = 13
2 \odot (5 \odot 6) = 13
2 \odot 5 \odot 6 = 13

Oui

(a x b) x c = a x (b x c) = a x b x c

Exemple:
(2 x 5) x 6 = 60
2 x (5 x 6) = 60
2 x 5 x 6 = 60

Élément neutre Pas d'élément neutre dans \R

Pour disposer d'un élément neutre, on travaille dans \R \cup \{-\infty\}.
L'élément neutre est alors -\infty.

En effet, a \oplus (-\infty) = \max(a,-\infty) = a.

0

En effet, a + 0 = a

0

En effet, a \odot 0 = a

1

En effet, a x 1 = a

Élément symétrique de a Pas d'élément symétrique. -a

En effet, a + (-a) = 0.

-a

En effet, a \odot (-a) = 0.

	\frac{1}{a}

En effet, a \times \frac{1}{a} = 1.

Élément absorbant Pas d'élément absorbant dans \R

Pour disposer d'un élément absorbant, on travaille dans \R \cup \{+\infty\}.
L'élément absorbant est alors +\infty.

En effet, a \oplus (+\infty) = \max(a,+\infty) = +\infty.

Pas d'élément absorbant. Pas d'élément absorbant. 0

En effet, a\cdot 0 = 0\cdot a = 0.

Distributivité \odot est distributive par rapport à \oplus. En effet, (a\oplus b) \odot c = \max(a,b)+c et (a\odot c)\oplus(b \odot c) =\max(a+c, b+c)  \times est distributive par rapport à +. En effet
 (a+b)\times c = a\times c + b \times c
Dans \R Addition tropicale Addition Multiplication tropicale

(mêmes propriétés que l'addition usuelle)

Multiplication

Il manque à la structure (\R, \oplus, \odot) l'élément neutre pour la première loi et l'existence d'élément symétrique pour la première loi pour que celle-ci soit un corps. On parle alors du semi-corps (\R, \oplus, \odot).

Opérateur découlant des précédents[modifier | modifier le code]

La puissance tropicale, que l'on notera a^{\odot b}, avec a un réel et b un entier naturel, correspond à la multiplication usuelle.

En effet,

a^{\odot b} = a \odot \cdots \odot a (b fois) = a + \cdots + a (b fois) = b \times a.

Semi-corps min-plus[modifier | modifier le code]

On peut définir une autre structure de semi-corps en prenant pour première loi le minimum au lieu du maximum.

Application au calcul des distances dans un graphe pour la structure min-plus[modifier | modifier le code]

Si on ajoute à R l'élément  + \infty et qu'on munit l'ensemble de la structure min-plus, on peut utiliser la structure ainsi définie pour le calcul de plus courte distance dans un graphe.

On peut représenter un graphe pondéré à n sommets comme une matrice  A=(a_{i,j}) des distances entre chaque sommet: si le sommet i est lié avec le sommet j alors l'élément  a_{i,j} est égal au poids de l'arête (i,j), si les sommets i et j ne sont pas reliées alors  a_{i,j} correspond à l'infini (on a  a_{i,i}=0).

Ainsi la distance entre i et j en passant par au plus un sommet est :  \min_{k \in \{1, \cdots, n\}}(a_{i,k}+a_{k,j})=\bigoplus_{k \in \{1, \cdots, n\}} a_{i,k}\odot a_{k,j}

Ceci correspond au produit matriciel dans la structure min-plus. Ainsi pour calculer la longueur d'un plus court chemin d'un sommet à un autre, en au plus n étapes, dans le graphe, il suffit de calculer la puissance n de A pour cette structure.

Références[modifier | modifier le code]

  1. Définition des mathématiques tropicales par leur inventeur Imre Simon, en ligne sur Scientific Commons
  2. Introduction à la géométrie tropicale, Ilia Itenberg, p. 2, Disponible en ligne.

Voir aussi[modifier | modifier le code]

Articles connexes[modifier | modifier le code]