Mathématiques tropicales

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

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

Opérateurs mathématiques

Définitions des opérateurs

• 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

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$ Démonstration Soient trois réels a, b et c tels que $a \le b \le c$. Alors $(a \oplus b) = b$ donc $(a \oplus b) \oplus c = b \oplus c$. Or, $b \le c$ donc $b \oplus c = c$. Donc, $(a \oplus b) \oplus c = c$ De même, $(b \oplus c) = c$ donc $a \oplus (b \oplus c) = a \oplus c$. Or, $a \le c$ donc $a \oplus c = c$. Donc, $a \oplus (b \oplus c) = c$ De plus, $a \oplus b \oplus c = c$ car $a \le b \le c$. On a prouvé que $(a \oplus b) \oplus c = a \oplus (b \oplus c) = a \oplus b \oplus c$.	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+b, a+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

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

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

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})=\oplus_{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

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

Article connexes

• Imre Simon