Masiv Monge
V matematice , Monge pole nebo Monge matice jsou objekty pojmenované po jejich objeviteli, francouzský matematik Gaspard Monge .
Definice
O matici m -by- n se říká, že je Mongeovým polem , pokud pro všechny platí , že
a
![{\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)
Pro libovolné dva řádky a libovolné dva sloupce Mongeova pole (2 × 2 podmatice) mají čtyři prvky v průsečících tu vlastnost, že součet prvků vlevo nahoře a vpravo dole (podél hlavní diagonály ) je menší . než nebo rovno součtu levého dolního a horního prvku ( podél antidiagonál ).
Tato matice je pole Monge:
Vezměme si například průsečík řádků 2 a 4 se sloupci 1 a 5. Čtyři prvky na průsečíkech tvoří matici:
17 + 7 = 24 23 + 11 = 34
Součet prvků podél hlavní diagonály je menší než součet prvků podél antidiagonál.
Vlastnosti
- Výše uvedená definice je ekvivalentní prohlášení
![{\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)
- Jakékoli podpole získané výběrem určitých řádků a sloupců z počátečního pole monge bude opět pole monge.
- Jakákoli lineární kombinace s nezápornými koeficienty Mongeova pole bude Mongeovým polem.
- Mongeova pole mají jednu zajímavou vlastnost. Pokud zakroužkujete minimální prvek každého řádku (pokud je několik stejných, vyberte ten úplně vlevo), uvidíte, že se kruhy posouvají dolů a doprava. Tedy pokud , tak pro všechny . Symetricky, pokud vyberete (první odshora) minimum v každém sloupci, budou se kruhy pohybovat doprava a dolů. Když vyberete maximální hodnoty, kroužky se pohybují v opačných směrech - nahoru doprava a dolů doleva.
- Jakékoli pole Monge je zcela monotónní, což znamená, že minimální prvky řádků přicházejí v neklesajícím pořadí sloupců a stejná vlastnost platí pro jakékoli podpole. Tato vlastnost vám umožňuje rychle najít minima v řetězcích pomocí algoritmu SMAWK .
![{\displaystyle f(x)=\arg \min _{i\in \{1,\ldots ,m\}}A[x,i]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/33a558a5f8fc0d9f064f885f43ef0137d20b9d83)
Související definice
- Byl navržen koncept slabého Mongeova pole - je to čtvercová matice n -by- n , která splňuje Mongeovu vlastnost pouze pro všechny .
- Mongeova matice je jen jiný název pro submodulární funkci dvou diskrétních proměnných. A je Mongeova matice právě tehdy, když A [ i , j ] je submodulární funkcí proměnných i , j .
- Matice A n-by-n se nazývá Mongeova antimatice, pokud splňuje nerovnost pro všechny a
![{\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)
(tato nerovnost se nazývá Mongeova antinerovnost) [3] .
Aplikace
- Čtvercová Mongeova matice, která je také symetrická vzhledem k hlavní diagonále , se nazývá Sapnikova matice (podle Freda Sapnika) [4] . Takové matice se používají k řešení problému obchodního cestujícího (konkrétně tento problém lze snadno vyřešit, pokud lze matici vzdálenosti reprezentovat jako Sapnikovu matici). Všimněte si, že jakákoli lineární kombinace Sapnikových matic je opět Sapnikova matice.
Literatura
- ↑ Rainer E. Burkard, Bettina Klinz, Rüdiger Rudolf. Perspektivy Mongeových vlastností v optimalizaci. - ELSEVIER, 1996. - T. 70 , no. 2 . — S. 95–96 .
- ↑ Thomas Carmen, Charles Leiserson, Ronald Rivest, Clifford Stein. Algoritmy, konstrukce a analýza . - Moskva, Petrohrad, Kyjev: Williams Publishing House, 2005. - S. 137 . — ISBN 5-8459-0857-4 .
- ↑ Rainer E. Burkard, Günter Rote, Eranda Çela, Gerhard J. Woeginger. Problém kvadratického přiřazení s monotónním anti-Mongem a symetrickou Toeplitzovou maticí: Snadné a těžké případy // Matematické programování. - červen 1998. - T. 82 , no. 1 . - S. 125-158 .
- ↑ Fred Supnick. Extrémní hamiltonovské čáry // Annals of Mathematics. druhá série. - červenec 1957. - T. 66 , no. 1 . — S. 179–201 . — .
5.E Girlich,MKovalev,AZaporozhets Podkužele submodulárních funkcí (podtřídy Mongeových matic)//Otto-von-Guericke-Universitat Magdeburg-1994.-Předtisk 29.-28s.
- Vladimír G. Deineko, Gerhard J. Woeginger. Některé problémy kolem cestujících prodejců, šipek a euromincí // Bulletin Evropské asociace pro teoretickou informatiku. - EATCS , říjen 2006. - T. 90 . — s. 43–52 . — ISSN 0252-9742 .