Macizo Monge
En matemáticas , los arreglos de Monge o matrices de Monge son objetos que llevan el nombre de su descubridor, el matemático francés Gaspard Monge .
Definición
Se dice que una matriz de m por n es una matriz de Monge si, para todo , tal que
y
![{\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)
Por lo tanto, para dos filas cualesquiera y dos columnas cualesquiera de un arreglo Monge (submatrices 2 × 2), los cuatro elementos en los puntos de intersección tienen la propiedad de que la suma de los elementos superior izquierdo e inferior derecho (a lo largo de la diagonal principal ) es menor que o igual a la suma de los elementos inferior izquierdo y superior (a lo largo de la antidiagonal ).
Esta matriz es una matriz de Monge:
Por ejemplo, tomemos la intersección de las filas 2 y 4 con las columnas 1 y 5. Los cuatro elementos en las intersecciones forman una matriz:
17 + 7 = 24 23 + 11 = 34
La suma de los elementos de la diagonal principal es menor que la suma de los elementos de la antidiagonal.
Propiedades
- La definición anterior es equivalente a la afirmación
![{\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)
- Cualquier subarreglo obtenido al seleccionar ciertas filas y columnas del arreglo monge inicial volverá a ser un arreglo monge.
- Cualquier combinación lineal con coeficientes de matriz Monge no negativos será una matriz Monge.
- Hay una propiedad interesante de las matrices de Monge. Si encierras en un círculo el elemento mínimo de cada fila (si hay varios iguales, elige el que está más a la izquierda), verás que los círculos se mueven hacia abajo y hacia la derecha. Es decir, si , entonces para todos . Simétricamente, si selecciona el mínimo (primero desde arriba) en cada columna, los círculos se moverán hacia la derecha y hacia abajo. Cuando selecciona los valores máximos , los círculos se mueven en direcciones opuestas: arriba a la derecha y abajo a la izquierda.
- Cualquier arreglo de Monge es completamente monótono, lo que significa que los elementos mínimos de las filas vienen en un orden de columnas no decreciente, y la misma propiedad se cumple para cualquier subarreglo. Esta propiedad le permite encontrar rápidamente mínimos en cadenas utilizando el algoritmo 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)
Definiciones relacionadas
- Se propuso el concepto de una matriz de Monge débil : es una matriz cuadrada de n por n que satisface la propiedad de Monge solo para todo .
- La matriz de Monge es solo otro nombre para una función submodular de dos variables discretas. A es una matriz de Monge si y sólo si A [ i , j ] es una función submodular de las variables i , j .
- Una matriz A de n por n se denomina antimatriz de Monge si satisface la desigualdad para todos y
![{\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)
(esta desigualdad se llama anti-desigualdad de Monge) [3] .
Aplicaciones
- La matriz cuadrada de Monge, que también es simétrica con respecto a la diagonal principal , se denomina matriz de Sapnik (después de Fred Sapnik) [4] . Estas matrices se utilizan para resolver el problema del viajante de comercio (es decir, este problema se resuelve fácilmente si la matriz de distancia se puede representar como una matriz de Sapnik). Tenga en cuenta que cualquier combinación lineal de matrices de Sapnik es nuevamente una matriz de Sapnik.
Literatura
- ↑ Rainer E. Burkard, Bettina Klinz, Rüdiger Rudolf. Perspectivas de las propiedades Monge en optimización. - ELSEVIER, 1996. - T. 70 , núm. 2 . — S. 95–96 .
- ↑ Thomas Carmen, Charles Leiserson, Ronald Rivest, Clifford Stein. Algoritmos, construcción y análisis . - Moscú, San Petersburgo, Kiev: Williams Publishing House, 2005. - P. 137 . — ISBN 5-8459-0857-4 .
- ↑ Rainer E. Burkard, Günter Rote, Eranda Çela, Gerhard J. Woeginger. El Problema de Asignación Cuadrática con una Matriz Toeplitz Simétrica y Anti-Monge Monótona: Casos Fáciles y Difíciles // Programación Matemática. - Junio 1998. - T. 82 , núm. 1 . - S. 125-158 .
- ↑ Fred Supnick. Líneas hamiltonianas extremas // Annals of Mathematics. segunda serie. - julio de 1957. - T. 66 , núm. 1 . — S. 179–201 . — .
5.E Girlich,MKovalev,AZaporozhets Subconos de funciones submodulares (subclases de matrices Monge)//Otto-von-Guericke-Universitat Magdeburg-1994.-Preprint 29.-28p
- Vladimir G. Deineko, Gerhard J. Woeginger. Algunos problemas relacionados con los vendedores ambulantes, los tableros de dardos y las monedas de euro // Boletín de la Asociación Europea de Ciencias Informáticas Teóricas. - EATCS , octubre de 2006. - T. 90 . — págs. 43–52 . — ISSN 0252-9742 .