Tropická matematika
Tropické matematické nebo tropické geometrii , jsou odvětví matematiky odpovídajících studiu modifikovaného systému nově definuje sčítání a násobení (a tudíž další operace). Byly definovány dvě tropické algebry: min-plus algebra definovaná s minimem pro sčítání a sčítání pro násobení a max-plus algebra , definovaná s maximem pro sčítání a sčítání pro násobení.
Tropické matematika je tak pojmenovaný na počest svého brazilského vynálezce , Imre Simon . Použití adjektiva tropický připisuje Jean-Éric Pin Dominique Perrinovi , zatímco sám Imre Simon jej připisuje Christianovi Choffrutovi. Termín tropický nemá jiný význam, než odkazovat na Brazílii.
Polovina těla max-plus
Sada R reálných čísel, pokud se operace maximální a navíc má komutativní poloviny - strukturu pole .
Matematické operátory
- Tropické přidání je definováno jako:
⊕{\ displaystyle \ oplus}
na⊕b=max(na,b){\ displaystyle a \ oplus b = \ max (a, b)}
.
Výsledkem tropického sčítání dvou čísel je tedy maximum z nich. Takže .
2⊕3=max(2,3)=3{\ displaystyle 2 \ oplus 3 = \ max (2,3) = 3}![2 \ oplus 3 = \ max (2,3) = 3](https://wikimedia.org/api/rest_v1/media/math/render/svg/fd44c75577741ef31dcb86840f2c7a3d403f1e78)
- Tropické rozmnožování (nebo tropický produkt) (nebo ) je definováno :
⊙{\ displaystyle \ odot}
⊗{\ displaystyle \ otimes}
na⊙b=na+b{\ displaystyle a \ odot b = a + b}
.
Výsledkem tropického násobení dvou čísel je tedy jejich obvyklý součet. Takže .
2⊙3=2+3=5{\ displaystyle 2 \ odot 3 = 2 + 3 = 5}![2 \ odot 3 = 2 + 3 = 5](https://wikimedia.org/api/rest_v1/media/math/render/svg/c629d251eaabfbdcaf7589272cd741eb5f7563eb)
Vlastnosti operátora
Tropických přídavek , jako je kromě obvyklé, komutativní a asociativní . V něm není žádný neutrální prvek ; pokud pracujeme , neutrální prvek je pak ; vskutku ,. Proti danému prvku neexistuje žádný prvek: k tomu je nutné .
R{\ displaystyle \ mathbb {R}}
R∪{-∞}{\ displaystyle \ mathbb {R} \ pohár \ {- \ infty \}}
-∞{\ displaystyle - \ infty}
na⊕(-∞)=max(na,-∞)=na{\ displaystyle a \ oplus (- \ infty) = \ max (a, - \ infty) = a}
na⊕X=max(na,X)=(-∞){\ displaystyle a \ oplus x = \ max (a, x) = (- \ infty)}
na=X=(-∞){\ displaystyle a = x = (- \ infty)}![{\ displaystyle a = x = (- \ infty)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7c1a11561a3a79fcbdd7efa8527e1bf209a91085)
Tropických násobení , stejně jako násobení je obvyklé, komutativní a asociativní . Je distribuční s ohledem na tropický doplněk . Číslo 0 je neutrální prvek pro tropické množení. Abychom měli absorpční prvek, pracujeme . Absorpční prvek je tedy . Opravdu . Každý prvek má inverzi pro tropické rozmnožování, protože skutečně .
⊕{\ displaystyle \ oplus}
R∪{+∞}{\ displaystyle \ mathbb {R} \ pohár \ {+ \ infty \}}
+∞{\ displaystyle + \ infty}
na⊕(+∞)=max(na,+∞)=+∞{\ displaystyle a \ oplus (+ \ infty) = \ max (a, + \ infty) = + \ infty}
na⊙(-na)=0{\ displaystyle a \ odot (-a) = 0}![a \ odot (-a) = 0](https://wikimedia.org/api/rest_v1/media/math/render/svg/19d51787e667c5cb8c4beea69447d036209e84b6)
Struktuře chybí neutrální prvek pro první zákon a existence symetrického prvku pro první zákon, takže struktura je tělo. Mluvíme pak o polotěle .
(R,⊕,⊙){\ displaystyle (\ mathbb {R}, \ oplus, \ odot)}
(R,⊕,⊙){\ displaystyle (\ mathbb {R}, \ oplus, \ odot)}![(\ mathbb {R}, \ oplus, \ odot)](https://wikimedia.org/api/rest_v1/media/math/render/svg/5ebb91404e294024551489dd8d814420d5d811a9)
Tropická síla
Tropických energie , uvedeno , se na reálné číslo a n je přirozené číslo, odpovídá obvyklému násobení. Vskutku,
na⊙ne{\ displaystyle a ^ {\ odot n}}![{\ displaystyle a ^ {\ odot n}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b22b7f53176733e4deb050802fdda719f4db0dd8)
na⊙ne=na⊙⋯⊙na⏞ne čas=na+⋯+na⏞ne čas=ne×na{\ displaystyle a ^ {\ odot n} = \ overbrace {a \ odot \ cdots \ odot a} ^ {n {\ text {times}}} = \ overbrace {a + \ cdots + a} ^ {n {\ text {times}}} = n \ times a}![{\ displaystyle a ^ {\ odot n} = \ overbrace {a \ odot \ cdots \ odot a} ^ {n {\ text {times}}} = \ overbrace {a + \ cdots + a} ^ {n {\ text {times}}} = n \ times a}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8449829a9e2fefcc1d6b0987b5ba3ee3785a49a2)
.
Tedy tropický polynom ve 2 proměnných
na⊙X⊕b⊙y⊕vs.{\ displaystyle a \ odot x \ oplus b \ odot y \ oplus c}![{\ displaystyle a \ odot x \ oplus b \ odot y \ oplus c}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ab201b71b698847d599d1b3b92e0bc05573c43d6)
je napsán s obvyklejšími zápisy,
max(na+X,b+y,vs.){\ displaystyle \ max (a + x, b + y, c)}![{\ displaystyle \ max (a + x, b + y, c)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7e8688143a33ab3f5b091ec2763321de75668cb8)
Polovina těla min-plus
Další struktura polovičního těla je definována tak, že jako první zákon se vezme minimum místo maxima.
Tropické polynomy
Umístíme se do min-plus poloviny těla. Tropické polynom je funkce , která může být vyjádřena jako tropické součet konečného počtu monomial podmínek. Každá monomie je tropickým produktem konstanty a proměnných v sadě . Tropický polynom je tedy F je minimum konečné rodiny afinních lineárních transformací, ve kterých mají proměnné lineární koeficienty; je to konkávní , spojitá a po částech lineární funkce :
F:Rne→R{\ displaystyle F: \ mathbb {R} ^ {n} \ to \ mathbb {R}}
X1,...,Xne{\ displaystyle X_ {1}, \ ldots, X_ {n}}![{\ displaystyle X_ {1}, \ ldots, X_ {n}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ac794f5521dcce89913085a6d566e7cdb615dbb0)
F(X1,...,Xne)=(VS1⊗X1⊗na11⊗⋯⊗Xne⊗nane1)⊕⋯⊕(VSs⊗X1⊗na1s⊗⋯⊗Xne⊗nanes)=min{VS1+na11X1+⋯+nane1Xne,...,VSs+na1sX1+⋯+nanesXne}.{\ displaystyle {\ begin {zarovnáno} 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 {zarovnáno}}}![{\ displaystyle {\ begin {zarovnáno} 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 {zarovnáno}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/945ef575435e334a50572e62d936493d81433199)
Soubor bodů, kde je tropický polynom F nediferencovatelný, se nazývá jeho tropický nadpovrch a označuje se (analogicky s algebraickými varietami . Rovnocenně) je soubor bodů, kde je minimum podmínek F dosaženo alespoň 2 členy.
PROTI(F){\ displaystyle \ mathrm {V} (F)}
PROTI(F){\ displaystyle \ mathrm {V} (F)}![{\ displaystyle \ mathrm {V} (F)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/106b5230121985e2de94033b7aab7c1036ccb577)
Aplikace: výpočet vzdáleností v grafu
Prvek se přidá k R a celá struktura se poskytne min-plus; takto definovanou strukturu lze použít pro výpočet nejkratší vzdálenosti v grafu.
+∞{\ displaystyle + \ infty}![+ \ infty](https://wikimedia.org/api/rest_v1/media/math/render/svg/bddbb0e4420a7e744cf71bd71216e11b0bf88831)
Představujeme graf vážený na n vrcholech maticí, která udává vzdálenosti mezi jednotlivými vrcholy: pokud je vrchol i spojen s vrcholem j, pak se prvek rovná hmotnosti hrany ( i , j ), pokud jsou vrcholy i a j nejsou spojeny, pak odpovídá nekonečnu (máme ).
NA=(nai,j){\ displaystyle A = (a_ {i, j})}
nai,j{\ displaystyle a_ {i, j}}
nai,j{\ displaystyle a_ {i, j}}
nai,i=0{\ displaystyle a_ {i, i} = 0}![a _ {{i, i}} = 0](https://wikimedia.org/api/rest_v1/media/math/render/svg/a5b156d2a892ef1df345b080e4a52143e1d70a62)
Takže vzdálenost mezi i a j procházející nejvýše jedním vrcholem je:
mink∈{1,⋯,ne}(nai,k+nak,j)=⨁k∈{1,⋯,ne}nai,k⊙nak,j{\ displaystyle \ min _ {k \ v \ {1, \ cdots, n \}} (a_ {i, k} + a_ {k, j}) = \ bigoplus _ {k \ v \ {1, \ cdots , n \}} a_ {i, k} \ odot a_ {k, j}}![\ 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}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cb146a63c4ef5edba08891b5c28095fdfcc1d992)
To odpovídá maticovému produktu ve struktuře min-plus. Takže pro výpočet délky nejkratší cesty z jednoho vrcholu k druhému, máme nanejvýš n krocích, v grafu, postačí pro výpočet výkonu n o A pro tuto strukturu.
Reference
-
Toto je definice tropické matematiky jejich vynálezce Imre Simon, online na Scientific Commons
-
Ilia Itenberg, „ Úvod do tropické geometrie » ,P. 2
-
Jean-Éric Pin, „Tropical Semirings“ , J. Gunawardena, Idempotency (Bristol, 1994) , Cambridge, Cambridge University Press,1998, str. 50-69.
-
Imre Simon, „Rozpoznatelné množiny s multiplicitou v tropickém semiringu“ , Mathematical Foundations of Computer Science (Carlsbad, 1988) , Springer, kol. "Lecture Notes in Computer Science" ( n O 324),
1988( číst online ) , s. 107–120.
-
Mathoverflow, 2011, Co je tropické na tropické algebře? na Mathoverflow
-
David Speyer a Bernd Sturmfels , „ Tropická matematika “, Mathematics Magazine , roč. 82, n o 3,2009, str. 163–173 ( DOI 10.1080 / 0025570X.2009.11953615 , číst online ).
Podívejte se také
Bibliografie
- Ilia Itenberg, „ Tropická práva “, Obrazy matematiky , CNRS,2011( číst online )
- (en) Diane Maclagan and Bernd Sturmfels, Introduction to Tropical Geometry , Providence (RI), American Mathematical Society, coll. " Postgraduální studium matematiky " ( n o 161)dubna 2015, 363 s. ( ISBN 978-0-8218-5198-2 , číst online )
- Ilia Itenberg, Grigory Mikhalkin a Eugenii Shustin, tropická algebraická geometrie , Basilej, Birkhäuser, kol. "Oberwolfach Cvičení" ( n o 35)2009( ISBN 978-3-0346-0047-7 , OCLC 310400815 )
- Dima Grigorjev, „ Tropické diferenciální rovnice “, Advances in Applied Mathematics , sv. 82,Javier 2017, str. 120–128 ( DOI 10.1016 / j.yam.2016.08.002 , arXiv 1502.08010.pdf )
- Dima Grigorjev , „ Tropické opakující se sekvence “, Advances in Applied Mathematics , sv. 116,2020, Článek n o 102012 ( DOI 10.1016 / j.aam.2020.102012 , arXiv 1807,10714 )
- Antoine Chambert-Loir , „ Když geometrie stane tropický “, Pour la vědu , n o 492,října 2018, str. 26-33
- (de) Hannah Markwig , „ Tropische Geometrie“ , Katrin Wendland , Annette Werner (ed.), Facettenreiche Mathematik , Wiesbaden, Vieweg + Teubner Verlag,2011( ISBN 978-3-8348-1414-2 )
Související články
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">