En matemáticas aplicadas a la informática , las matrices de Monge , o matrices de Monge , son objetos matemáticos que llevan el nombre de su descubridor, el matemático francés Gaspard Monge .
Una m -by- n matriz se dice que es un array Monge si, por todo tal que
uno obtiene [1]
Entonces, para dos filas y dos columnas cualesquiera de una matriz de Monge (una submatriz de 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 través de la diagonal principal ) es menor o igual que la suma de los elementos inferior izquierdo y superior derecho (a través de la antidiagonal ).
Esta matriz es una matriz de Monge:
Por ejemplo, tome la intersección de las filas 2 y 4 con las columnas 1 y 5. Los cuatro elementos son:
- 17 + 7 = 24
- 23 + 11 = 34
La suma de los elementos superior izquierda e inferior derecha es menor o igual que la suma de los elementos inferior izquierda y superior derecha.
Propiedades
- La definición anterior es equivalente a la declaración
- Una matriz es una matriz de Monge si y solo si para todos y .
- Cualquier subarreglo producido al seleccionar ciertas filas y columnas de un arreglo de Monge original será en sí mismo un arreglo de Monge.
- Cualquier combinación lineal con coeficientes no negativos de matrices Monge es en sí misma una matriz Monge.
- Una propiedad interesante de los arreglos de Monge es que si marca con un círculo el mínimo más a la izquierda de cada fila, descubrirá que sus círculos marchan hacia abajo a la derecha; es decir, si, luego para todos . Simétricamente, si marca el mínimo superior de cada columna, sus círculos marcharán hacia la derecha y hacia abajo. Los máximos de fila y columna marchan en sentido contrario: hacia arriba a la derecha y hacia abajo a la izquierda.
- Se ha propuesto la noción de matrices débiles de Monge ; una matriz de Monge débil es una matriz cuadrada n- por- n que satisface la propiedad de Monge solo para todos .
- Cada arreglo de Monge es totalmente monótono, lo que significa que sus mínimos de fila ocurren en una secuencia de columnas no decreciente, y que la misma propiedad es verdadera para cada subarreglo. Esta propiedad permite encontrar rápidamente los mínimos de fila mediante el algoritmo SMAWK .
- La matriz de Monge es solo otro nombre para la función submodular de dos variables discretas. Precisamente, A es una matriz de Monge si y solo si A [ i , j ] es una función submodular de las variables i , j .
Aplicaciones
- Una matriz de Monge cuadrada que también es simétrica con respecto a su diagonal principal se llama matriz de Supnick (en honor a Fred Supnick ); este tipo de matriz tiene aplicaciones para el problema del viajante de comercio (es decir, que el problema admite soluciones fáciles cuando la matriz de distancias se puede escribir como una matriz Supnick). Cualquier combinación lineal de matrices de Supnick es en sí misma una matriz de Supnick.
Referencias
- ^ Burkard, Rainer E .; Klinz, Bettina; Rudolf, Rüdiger (1996). "Perspectivas de las propiedades de Monge en optimización" . Matemáticas aplicadas discretas . ELSEVIER. 70 (2): 95–96. doi : 10.1016 / 0166-218x (95) 00103-x .
- Deineko, Vladimir G .; Woeginger, Gerhard J. (octubre de 2006). "Algunos problemas relacionados con los vendedores ambulantes, los dardos y las monedas de euro" (PDF) . Boletín de la Asociación Europea de Informática Teórica . EATCS . 90 : 43–52. ISSN 0252-9742 .