Mongeovo pole - Monge array

V matematice aplikované na informatiku jsou Mongeovy matice nebo Mongeovy matice matematické objekty pojmenované podle jejich objevitele, francouzského matematika Gasparda Mongeho .

M -by- n matice se říká, že je Monge pole , jestliže pro všechny tak, že ${\ displaystyle \ scriptstyle i, \, j, \, k, \, \ ell}$

${\ displaystyle 1 \ leq já <k \ leq m {\ text {a}} 1 \ leq j <\ ell \ leq n}$

jeden získá

${\ displaystyle A [i, j] + A [k, \ ell] \ leq A [i, \ ell] + A [k, j]. \,}$

Takže pro libovolné dva řádky a dva sloupce pole Monge (2 × 2 submatice) mají čtyři prvky v průsečících vlastnost, že součet prvků vlevo nahoře a vpravo dole (přes hlavní úhlopříčku ) je menší nebo roven součtu prvků vlevo dole a vpravo nahoře (přes antidiagonální ).

Tato matice je pole Monge:

${\ displaystyle {\ begin {bmatrix} 10 a 17 a 13 a 28 a 23 \\ 17 a 22 a 16 a 29 a 23 \\ 24 a 28 a 22 a 34 a 24 \\ 11 a 13 a 6 a 17 a 7 \\ 45 a 44 a 32 a 37 a 23 \\ 36 a 33 a 19 a 21 a 6 \\ 75 a 66 a 51 a 53 a 34 \ konec {bmatrix}}}$

Vezměte si například průsečík řádků 2 a 4 se sloupci 1 a 5. Čtyři prvky jsou:

${\ displaystyle {\ begin {bmatrix} 17 & 23 \\ 11 & 7 \ end {bmatrix}}}$

17 + 7 = 24

23 + 11 = 34

Součet prvků vlevo nahoře a vpravo dole je menší nebo roven součtu prvků vlevo dole a vpravo nahoře.

Vlastnosti

• Výše uvedená definice je ekvivalentní s tvrzením

Matice je pole Monge právě tehdy, když pro všechny a .${\ displaystyle A [i, j] + A [i + 1, j + 1] \ leq A [i, j + 1] + A [i + 1, j]}$${\ displaystyle 1 \ leq i <m}$${\ displaystyle 1 \ leq j <n}$

• Jakákoli podoblast vytvořená výběrem určitých řádků a sloupců z původního pole Monge bude sama o sobě pole Monge.
• Jakákoli lineární kombinace s nezápornými koeficienty Mongeových polí je sama o sobě Mongeovým polem.
• Jedna zajímavá vlastnost Mongeových polí je, že pokud označíte kruhem nejméně vlevo od každého řádku, zjistíte, že vaše kruhy pochodují dolů doprava; to znamená, když , tak pro všechny . Symetricky, pokud označíte nejvyšší minimum každého sloupce, vaše kruhy pochodují doprava a dolů. Maxima řádků a sloupců pochodují opačným směrem: nahoru doprava a dolů doleva.${\ displaystyle f (x) = \ arg \ min _ {i \ v \ {1, \ ldots, m \}} A [x, i]}$${\ displaystyle f (j) \ leq f (j + 1)}$${\ displaystyle 1 \ leq j <n}$
• Byl navržen pojem slabých Mongeových polí ; slabé Mongeovo pole je čtvercová matice n -by- n, která splňuje vlastnost Monge pouze pro všechny .${\ displaystyle A [i, i] + A [r, s] \ leq A [i, s] + A [r, i]}$${\ Displaystyle 1 \ leq i <r, s \ leq n}$
• Každé pole Monge je zcela monotónní, což znamená, že jeho řádková minima se vyskytují v neklesající posloupnosti sloupců a že stejná vlastnost platí pro každé dílčí pole. Tato vlastnost umožňuje rychle najít minima řádků pomocí algoritmu SMAWK .
• Mongeova matice je jen jiný název pro submodulární funkci dvou diskrétních proměnných. Přesně A je Mongeova matice právě tehdy, když A [ i , j ] je submodulární funkcí proměnných  i , j .

Aplikace

• Čtvercová Mongeova matice, která je také symetrická kolem své hlavní úhlopříčky, se nazývá Supnickova matice (po Fredu Supnickovi ); tento druh matice má aplikace na problém obchodního cestujícího (jmenovitě, že problém připouští snadná řešení, když lze matici vzdálenosti zapsat jako matici Supnick). Všimněte si, že jakákoli lineární kombinace matic Supnick je sama maticí Supnick.

Reference

• Deineko, Vladimir G .; Woeginger, Gerhard J. (říjen 2006). „Některé problémy týkající se cestujících prodejců, terčů a euromincí“ (PDF) . Bulletin Evropské asociace pro teoretickou informatiku . EATCS . 90 : 43–52. ISSN  0252-9742 .