Monge matriz - Monge array

Em matemática aplicada à ciência da computação , matrizes Monge , ou matrizes Monge , são objetos matemáticos chamados por seu descobridor, o matemático francês Gaspard Monge .

Um m -by- n matriz é dito ser uma matriz Monge se, para todos tal que ${\ Displaystyle \ scriptstyle i, \, j, \, K, \, \} ell$

${\ Displaystyle 1 \ leq i <k \ leq m {\ texto {e}} 1 \ leq j <\ ell \ n} leq$

obtém-se

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

Assim para quaisquer duas linhas e duas colunas de uma matriz de Monge (um sub-matriz 2 x 2) os quatro elementos nos pontos de intersecção tem a propriedade de que a soma dos elementos superior esquerdo e inferior direito (em toda a diagonal principal ) é inferior ou igual à soma dos elementos inferior esquerdo e superior direito (em relação à antidiagonais ).

Esta matriz é uma matriz Monge:

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

Por exemplo, tomar a intersecção das linhas 2 e 4 com as colunas 1 e 5. Os quatro elementos são os seguintes:

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

17 + 7 = 24

23 + 11 = 34

A soma dos elementos superior esquerdo e inferior direito é menor ou igual à soma dos elementos inferior esquerdo e superior direito.

propriedades

• A definição acima é equivalente à declaração

A matriz é uma matriz Monge se e somente se para todos e .${\ Displaystyle Uma [i, j] + A [i + 1, j + 1] \ leq Uma [i, j + 1] + A [i + 1, j]}$${\ Displaystyle 1 \ leq i <m}$${\ Displaystyle 1 \ leq j <n}$

• Qualquer sub-disposição produzida por determinadas seleccionando linhas e colunas de uma matriz Monge original será ela própria ser uma matriz Monge.
• Qualquer combinação linear com coeficientes não negativos de matrizes Monge é ele próprio uma matriz Monge.
• Uma propriedade interessante de matrizes Monge é que se você marcar com um círculo o mínimo mais à esquerda de cada linha, você vai descobrir que seus círculos marchar para baixo, para a direita; ou seja, se , em seguida, para todos . Simetricamente, se você marcar a mínima superior de cada coluna, seus círculos vão marchar para a direita e para baixo. A linha e coluna máximos marcha no sentido oposto: para cima para a direita e para baixo, para a esquerda.${\ Displaystyle f (x) = \ arg \ min _ {i \ in \ {1, \ ldots, m \}} A [x, i]}$${\ Displaystyle f (j) \ leq f (j + 1)}$${\ Displaystyle 1 \ leq j <n}$
• A noção de fracas matrizes Monge foi proposto; uma matriz Monge fraco é um quadrado n -by- n matriz que satisfaz a propriedade Monge apenas para todos .${\ Displaystyle Uma [i, i] + A [R, S] \ leq Uma [i, s] + A [r, i]}$${\ Displaystyle 1 \ leq i <r, s leq n \}$
• Cada variedade Monge é totalmente monótona, o que significa que seus mínimos linha ocorrer em uma seqüência não decrescente de colunas, e que a mesma propriedade é verdadeiro para cada subarray. Esta propriedade permite que os mínimos de linha a ser encontrado rapidamente, utilizando o algoritmo de SMAWK .
• Matriz Monge é apenas outro nome para a função submodulares de duas variáveis discretas. Precisamente, A é uma matriz Monge se e apenas se um [ i , j ] é uma função de variáveis submodulares  i , j .

aplicações

• Uma matriz quadrada Monge que também é simétrica em relação a sua diagonal principal é chamado uma matriz Supnick (após Fred Supnick ); este tipo de matriz tem aplicações para o problema do caixeiro viajante (isto é, que o problema não admite soluções fáceis quando a matriz de distância pode ser escrita como uma matriz Supnick). Note-se que qualquer combinação linear das matrizes Supnick é ele próprio uma matriz Supnick.

Referências

• Deineko, Vladimir G .; Woeginger, Gerhard J. (Outubro de 2006). "Alguns problemas em torno vendedores ambulantes, placas de dardo e Euro-moedas" (PDF) . Boletim da Associação Europeia para a Ciência da Computação Teórica . EATCS . 90 : 43-52. ISSN  0252-9742 .