Mathématiques tropicales

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

On se place dans le demi-corps min-plus. Un polynôme tropical est une fonction ${\displaystyle 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 ${\displaystyle 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[6] :

${\displaystyle {\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é ${\displaystyle \mathrm {V} (F)}$ (en analogie avec les variétés algébriques. De manière équivalente, ${\displaystyle \mathrm {V} (F)}$ est l'ensemble des points où le minimum des termes de F est atteint par au moins 2 termes.

On ajoute à R l'élément ${\displaystyle +\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 ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle a_{i,j}}$ correspond à l'infini (on a ${\displaystyle a_{i,i}=0}$).

Ainsi la distance entre i et j en passant par au plus un sommet est :

${\displaystyle \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.