« Mathématiques tropicales » : différence entre les versions

Navigation interactive dans l’historique

← Modification précédente Modification suivante →

Contenu supprimé Contenu ajouté

Intégrés

Version du 7 avril 2020 à 21:26

Cet article est une ébauche concernant les mathématiques.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

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^[1], et l'algèbre max-plus, définie avec le maximum pour addition et l'addition pour multiplication^[2].

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^[3], alors que Imre Simon lui-même l'attribue à Christian Choffrut ^[4]^,^[5]. Le terme tropical n'a pas d'autre sens que de faire référence au Brésil.

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 commutatif.

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 $\mathbb {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\leq b\leq c$ . Alors $(a\oplus b)=b$ donc $(a\oplus b)\oplus c=b\oplus c$ . Or, $b\leq 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\leq c$ donc $a\oplus c=c$ . Donc, $a\oplus (b\oplus c)=c$ De plus, $a\oplus b\oplus c=c$ car $a\leq b\leq 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 $\mathbb {R}$ Pour disposer d'un élément neutre, on travaille dans $\mathbb {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 $\mathbb {R}$ 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$ .	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 $\mathbb {R}$	Addition tropicale	Addition	Multiplication tropicale (mêmes propriétés que l'addition usuelle)	Multiplication

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 semi-corps $(\mathbb {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}=\overbrace {a\odot \cdots \odot a} ^{b{\text{ fois}}}=\overbrace {a+\cdots +a} ^{b{\text{ 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é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.

Références

↑ C'est la définition des mathématiques tropicales par leur inventeur Imre Simon, en ligne sur Scientific Commons
↑ Ilia Itenberg, « Introduction à la géométrie tropicale », p. 2
↑ Jean-Éric Pin, « Tropical Semirings », dans J. Gunawardena, Idempotency (Bristol, 1994), Cambridge, Cambridge University Press, 1998, p. 50-69.
↑ Imre Simon, « Recognizable sets with multiplicities in the tropical semiring », dans Mathematical Foundations of Computer Science (Carlsbad, 1988), Springer, coll. « Lecture Notes in Computer Science » (n^o 324), 1988 (lire en ligne).
↑ Mathoverflow, 2011, What's tropical about tropical algebra? sur Mathoverflow

Voir aussi

Bibliographie

Ilia Itenberg, « Droites tropicales », Images des mathématiques, CNRS,‎ 2011 (lire en ligne)
Diane Maclagan et Bernd Sturmfels, Introduction to Tropical Geometry, American Mathematical Society, coll. « Graduate Studies in Mathematics » (n^o 161), avril 2015, 363 p. (ISBN 9780821851982, lire en ligne)
Ilia Itenberg, Grigory Mikhalkin et Eugenii Shustin, Tropical algebraic geometry, Bâle, Birkhäuser, coll. « Oberwolfach Seminars » (n^o 35), 2009 (ISBN 9783034600477, OCLC 310400815)
Dima Grigoriev, « Tropical differential equations », Advances in Applied Mathematics, vol. 82,‎ javier 2017, p. 120–128 (DOI 10.1016/j.aam.2016.08.002, arXiv 1502.08010.pdf)
Dima Grigoriev, « Tropical recurrent sequences », Advances in Applied Mathematics, vol. 116,‎ 2020, article n^o 102012 (DOI 10.1016/j.aam.2020.102012, arXiv 1807.10714)
Antoine Chambert-Loir, « Quand la géométrie devient tropicale », Pour la science, n^o 492,‎ octobre 2018, p. 26-33
(de) Hannah Markwig, « Tropische Geometrie », dans Katrin Wendland, Annette Werner (éd.), Facettenreiche Mathematik, Wiesbaden, Vieweg+Teubner Verlag, 2011 (ISBN 978-3-8348-1414-2)

Articles connexes

[1] C'est la définition des mathématiques tropicales par leur inventeur Imre Simon, en ligne sur Scientific Commons

[2] Ilia Itenberg, « Introduction à la géométrie tropicale », p. 2

[3] Jean-Éric Pin, « Tropical Semirings », dans J. Gunawardena, Idempotency (Bristol, 1994), Cambridge, Cambridge University Press, 1998, p. 50-69.

[4] Imre Simon, « Recognizable sets with multiplicities in the tropical semiring », dans Mathematical Foundations of Computer Science (Carlsbad, 1988), Springer, coll. « Lecture Notes in Computer Science » (n^o 324), 1988 (lire en ligne).

[5] Mathoverflow, 2011, What's tropical about tropical algebra? sur Mathoverflow

[1]

[2]

[3]

[4]

[5]

@@ Ligne 242 : / Ligne 242 : @@
 }}
 * {{article| titre=Quand la géométrie devient tropicale| auteur=[[Antoine Chambert-Loir]]| pages=26-33| périodique=[[Pour la science]]| date=octobre 2018| numéro=492}}
-* {{Chapitre |langue=de |auteur1=[[Hannah Markwig]] |titre chapitre=Tropische Geometrie |auteurs ouvrage=[[Katrin Wendland]], {{Lien|langue=de|fr=Annette Werner}} (éd.) |titre ouvrage=Facettenreiche Mathematik | sous-titre ouvrage= |lieu=Wiesbaden |éditeur=Vieweg+Teubner Verlag |année=2011 |pages totales= |isbn=978-3-8348-1414-2 |lire en ligne= |page début chapitre=295 |passage= }}
+* {{Chapitre |langue=de |auteur1=[[Hannah Markwig]] |titre chapitre=Tropische Geometrie |auteurs ouvrage=[[Katrin Wendland]], [[Annette Werner]] (éd.) |titre ouvrage=Facettenreiche Mathematik | sous-titre ouvrage= |lieu=Wiesbaden |éditeur=Vieweg+Teubner Verlag |année=2011 |pages totales= |isbn=978-3-8348-1414-2 |lire en ligne= |page début chapitre=295 |passage= }}
 === Articles connexes ===