Matriz de Soupnik
La matriz de Supnik o arreglo de Supnik , llamado así por Fred Supnik del City College de Nueva York , quien introdujo el concepto en 1957, es un arreglo de Monge que también es una matriz simétrica .
Definición matemática
La matriz de Supnik es un arreglo Monge cuadrado , simétrico alrededor de la diagonal principal .
Una matriz de n × n es una matriz de Supnik si para todo i , j , k , l tal que
y
después
tanto como
Rudolf y Wojinger dan una definición lógicamente equivalente, quienes demostraron en 1995 que
Una matriz es una matriz de Supnik si se puede escribir como la suma de una matriz de suma S y una combinación lineal no negativa de matrices de bloques LL-UR.La matriz suma se define en términos de una secuencia de n números reales { α i }:
![{\displaystyle S=[s_{ij}]=[\alpha _{i}+\alpha _{j}];\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3987758d4f97df68c15eb03ae5621c5a2d07bb9e)
y la matriz de bloques LL-UR consta de dos rectángulos ubicados simétricamente en las esquinas inferior izquierda y superior derecha, para los cuales a ij = 1, mientras que todos los demás elementos de la matriz son iguales a cero.
Propiedades
La suma de dos matrices de Supnik da como resultado una nueva matriz de Supnik (Deineko y Wöjinger, 2006).
Multiplicando la matriz de Supnik por un número real no negativo se obtiene una nueva matriz de Supnik (Deineko y Wojinger, 2006).
Si la matriz de distancia en el problema del viajante de comercio se puede escribir como la matriz de Supnik, entonces este caso particular del problema admite una solución simple (incluso si el problema es típicamente NP-difícil ).
Enlaces
- Supnick, Fred. Líneas hamiltonianas extremas (inglés) // Annals of Mathematics : journal. - 1957. - julio ( vol. 66 , n. 1 ). - P. 179-201 . — .
- Woeginger, Gerhard J. Problemas computacionales sin computación (neopr.) // Nieuwarchief. - 2003. - junio ( vol. 5 , no. 4 ). - S. 140-147 . Archivado desde el original el 4 de septiembre de 2004.
- Deineko, Vladimir G.; Woeginger, Gerhard J. Algunos problemas en torno a los vendedores ambulantes, tableros de dardos y monedas de euro // Ciencias de la Computación Teórica : diario. - European Association for Theoretical Computer Science , 2006. - Octubre ( vol. 90 ). - P. 43-52 . — ISSN 0252-9742 .