Mathématiques tropicales
# 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). Deux algèbres tropicales ont été définies : l'algèbre min-plus, définie avec le minimum pour addition et l'addition pour multiplication, et l'algèbre max-plus, définie avec le maximum pour addition et l'addition pour multiplication.

Les mathématiques tropicales sont dénommées ainsi en l'honneur de leur inventeur brésilien, Imre Simon. L'emploi de l'adjectif tropical est attribué par Jean-Éric Pin à Dominique Perrin, alors que Imre Simon lui-même l'attribue à Christian Choffrut $^,.$ Le terme tropical n'a pas d'autre sens que de faire référence au Brésil.

## Demi-corps max-plus

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

### Opérateurs mathématiques

* 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 des opérateurs

L'addition tropicale est, comme l'addition usuelle, commutative et associative. Il n'y a pas d'élément neutre dans $\mathbb {R}$ ; si on travaille dans $\mathbb {R} \cup \{-\infty \}$, l'élément neutre est alors $-\infty$ ; en effet, $a\oplus (-\infty )=\max(a,-\infty )=a$. Il n'y a pas d'élément opposé à un élément donné : pour que $a\oplus x=\max(a,x)=(-\infty )$, il faut que $a=x=(-\infty )$.

La multiplication tropicale est, comme la multiplication usuelle, commutative et associative. Elle est distributive par rapport à l'addition tropicale $\oplus$. Le nombre 0 est l'élément neutre pour la multiplication tropicale. Pour disposer d'un élément absorbant, on travaille dans $\mathbb {R} \cup \{+\infty \}$. L'élément absorbant est alors $+\infty$. En effet, $a\oplus (+\infty )=\max(a,+\infty )=+\infty$. Tout élément possède un inverse pour la multiplication tropicale puisque en effet $a\odot (-a)=0$.

Il manque à la structure $(\mathbb {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 la structure soit un corps. On parle alors du demi-corps $(\mathbb {R} ,\oplus ,\odot )$.

### Puissance tropicale

La puissance tropicale, notée $a^{\odot n}$, avec a un réel et n un entier naturel, correspond à la multiplication usuelle. En effet,

    $a^{\odot n}=\overbrace {a\odot \cdots \odot a} ^{n{\text{ fois}}}=\overbrace {a+\cdots +a} ^{n{\text{ fois}}}=n\times a$.

Ainsi, le polynôme tropical en 2 variables

    $a\odot x\oplus b\odot y\oplus c$

s'écrit, avec les notations plus usuelles,

    $\max(a+x,b+y,c)$

### Demi-corps min-plus

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

## Polynômes tropicaux

On se place dans le demi-corps min-plus. Un polynôme tropical est une fonction $F:\mathbb {R} ^{n}\to \mathbb {R}$ qui peut s'exprimer comme une somme tropicale d'un nombre fini de termes monomiaux. Chaque monôme est un produit tropical d'une constante et de variables prises dans un ensemble $X_{1},\ldots ,X_{n}$. Ainsi, un polynôme tropical est F est le minimum d'une famille finie de transformations linéaires affines dans lesquelles les variables ont des coefficients linéaires ; c'est une fonction concave, continue, et linéaire par morceaux :

    ${\begin{aligned}F(X_{1},\ldots ,X_{n})&=\left(C_{1}\otimes X_{1}^{\otimes a_{11}}\otimes \cdots \otimes X_{n}^{\otimes a_{n1}}\right)\oplus \cdots \oplus \left(C_{s}\otimes X_{1}^{\otimes a_{1s}}\otimes \cdots \otimes X_{n}^{\otimes a_{ns}}\right)\\&=\min\{C_{1}+a_{11}X_{1}+\cdots +a_{n1}X_{n},\;\ldots ,\;C_{s}+a_{1s}X_{1}+\cdots +a_{ns}X_{n}\}.\end{aligned}}$

L'ensemble des points où un polynôme tropical F est non différentiable est appelé son hypersurface tropicale et noté $\mathrm {V} (F)$ (en analogie avec les variétés algébriques. De manière équivalente, $\mathrm {V} (F)$ est l'ensemble des points où le minimum des termes de F est atteint par au moins 2 termes.

## Application : calcul des distances dans un graphe

On ajoute à R l'élément $+\infty$ et 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 représente un graphe pondéré à n sommets par la matrice $A=(a_{i,j})$ qui donne les 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és 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, on a au plus n étapes, dans le graphe, il suffit de calculer la puissance n de A pour cette structure.

