Massif Monge
Matematiikassa Monge-taulukot tai Monge- matriisit ovat kohteita, jotka on nimetty niiden löytäjän, ranskalaisen matemaatikon Gaspard Mongen mukaan .
Määritelmä
M - by- n matriisin sanotaan olevan Monge-taulukko , jos kaikille sellainen, että
ja
![{\displaystyle A[i,j]+A[k,\ell ]\leq A[i,\ell ]+A[k,j].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5b021725759ff92d6169fe4d777cfd21aab39c71)
Siten millä tahansa kahdella Monge-taulukon rivillä ja kahdella sarakkeella (2 × 2 alimatriisia) neljällä elementillä leikkauspisteissä on se ominaisuus, että vasemman ylä- ja alaoikean elementtien summa ( päädiagonaalia pitkin ) on pienempi . kuin tai yhtä suuri kuin vasemman alakulman ja yläosan elementtien summa ( antidiagonaalia pitkin ).
Tämä matriisi on Monge-taulukko:
Otetaan esimerkiksi rivien 2 ja 4 leikkauspiste sarakkeiden 1 ja 5 kanssa. Leikkauksissa olevat neljä elementtiä muodostavat matriisin:
17 + 7 = 24 23 + 11 = 34
Päälävistäjän elementtien summa on pienempi kuin antidiagonaalin elementtien summa.
Ominaisuudet
- Yllä oleva määritelmä vastaa lausetta
![{\displaystyle A[i,j]+A[i+1,j+1]\leq A[i,j+1]+A[i+1,j]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b7000d7683c86d27f50ff127740330963b64d384)
- Mikä tahansa alitaulukko, joka saadaan valitsemalla tietyt rivit ja sarakkeet alkuperäisestä monge-taulukosta, on jälleen monge-taulukko.
- Mikä tahansa lineaarinen yhdistelmä ei-negatiivisten Monge-taulukkokertoimien kanssa on Monge-taulukko.
- Monge-taulukoilla on yksi mielenkiintoinen ominaisuus. Jos ympyrät jokaisen rivin minimielementin (jos samoja on useita, valitse vasemmanpuoleisin), näet, että ympyrät liikkuvat alas ja oikealle. Eli jos , niin kaikille . Symmetrinen, jos valitset (ensimmäisen ylhäältä) minimin kustakin sarakkeesta, ympyrät liikkuvat oikealle ja alas. Kun valitset maksimiarvot , ympyrät liikkuvat vastakkaisiin suuntiin - ylös oikealle ja alas vasemmalle.
- Mikä tahansa Monge-taulukko on täysin monotoninen, mikä tarkoittaa, että rivien vähimmäiselementit tulevat ei-laskevassa sarakejärjestyksessä, ja sama ominaisuus pätee mihin tahansa alitaulukkoon. Tämän ominaisuuden avulla voit nopeasti löytää minimit merkkijonoista SMAWK -algoritmin avulla .
![{\displaystyle f(x)=\arg \min _{i\in \{1,\ldots ,m\}}A[x,i]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/33a558a5f8fc0d9f064f885f43ef0137d20b9d83)
Aiheeseen liittyvät määritelmät
- Esitettiin heikon Monge-taulukon käsite - se on neliön n -by- n matriisi, joka täyttää Monge-ominaisuuden vain kaikille .
- Monge-matriisi on vain toinen nimi kahden erillisen muuttujan submodulaariselle funktiolle . A on Monge-matriisi, jos ja vain jos A [ i , j ] on muuttujien i , j alimodulaarinen funktio .
- N-kertaa n matriisia A kutsutaan Monge-antimatriisiksi, jos se tyydyttää epäyhtälön kaikille ja
![{\displaystyle A[i,i]+A[r,s]\leq A[i,s]+A[r,i]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6ca13a9771863039e6190248c0ee7b5c177f07af)
![{\displaystyle A[i,j]+A[r,s]\geq A[i,s]+A[r,j]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0837d41201d014467206489f8c57ade8705aba7c)
(tätä epätasa-arvoa kutsutaan Mongen epätasa-arvoksi) [3] .
Sovellukset
- Neliön muotoista Monge-matriisia, joka on myös symmetrinen päälävistäjän suhteen , kutsutaan Sapnik-matriisiksi (Fred Sapnikin mukaan) [4] . Tällaisia matriiseja käytetään matkustavan myyjän ongelman ratkaisemiseen (eli tämä ongelma on helppo ratkaista, jos etäisyysmatriisi voidaan esittää Sapnik-matriisina). Huomaa, että mikä tahansa Sapnik-matriisien lineaarinen yhdistelmä on jälleen Sapnik-matriisi.
Kirjallisuus
- ↑ Rainer E. Burkard, Bettina Klinz, Rüdiger Rudolf. Monge-ominaisuuksien näkökulmat optimointiin. - ELSEVIER, 1996. - T. 70 , no. 2 . — S. 95–96 .
- ↑ Thomas Carmen, Charles Leiserson, Ronald Rivest, Clifford Stein. Algoritmit, rakentaminen ja analyysi . - Moskova, Pietari, Kiova: Williams Publishing House, 2005. - S. 137 . — ISBN 5-8459-0857-4 .
- ↑ Rainer E. Burkard, Günter Rote, Eranda Çela, Gerhard J. Woeginger. Kvadraattinen määritysongelma monotonisen anti-Mongen ja symmetrisen Toeplitz-matriisin kanssa: Helppoja ja kovia tapauksia // Matemaattinen ohjelmointi. - Kesäkuu 1998. - T. 82 , no. 1 . - S. 125-158 .
- ↑ Fred Supnick. Äärimmäiset Hamiltonin linjat // Matematiikan Annals. toinen sarja. - Heinäkuu 1957. - T. 66 , no. 1 . — S. 179–201 . — .
5.E Girlich,MKovalev,AZaporozhets Alimodulaaristen funktioiden alakartiot (Monge-matriisien alaluokat)//Otto-von-Guericke-Universitat Magdeburg-1994.-Preprint 29.-28p
- Vladimir G. Deineko, Gerhard J. Woeginger. Joitakin ongelmia matkustavien myyntimiesten, tikkataulujen ja eurokolikoiden ympärillä // Bulletin of the European Association for Theoretical Computer Science. - EATCS , lokakuu 2006. - T. 90 . — s. 43–52 . — ISSN 0252-9742 .