Cubo | Cuboctaedro | Octaedro | truncada octaedro |
(± 1, ± 1, ± 1) | (0, ± 1, ± 1) | (0, 0, ± 1) | (0, ± 1, ± 2) |
Cuatro politopos integrales en tres dimensiones |
---|
En geometría y combinatoria poliédrica , un politopo integral es un politopo convexo cuyos vértices tienen coordenadas cartesianas enteras . [1] Es decir, es un politopo que es igual al casco convexo de sus puntos enteros . [2] politopos Integral también se llaman politopos de celosía o Z-politopos . Los casos especiales de politopos integrales bidimensionales y tridimensionales pueden denominarse polígonos o poliedros en lugar de politopos, respectivamente.
Ejemplos de
Un -el simplex regular dimensional se puede representar como un politopo entero en, el casco convexo de los puntos enteros para los que una coordenada es una y el resto es cero. Otro tipo importante de integral simplex, el ortosquema , se puede formar como el casco convexo de puntos enteros cuyas coordenadas comienzan con un número de unos consecutivos seguidos de ceros en todas las coordenadas restantes. La-cubo de unidad dimensional en tiene como vértices todos los puntos enteros cuyas coordenadas son cero o uno.
En optimización
En el contexto de la programación lineal y problemas relacionados en la optimización matemática , los politopos convexos a menudo se describen mediante un sistema de desigualdades lineales que sus puntos deben obedecer. Cuando un politopo es integral, la programación lineal se puede utilizar para resolver problemas de programación de números enteros para el sistema de desigualdades dado, un problema que de otra manera puede ser más difícil.
Algunos poliedros que surgen de problemas de optimización combinatoria son automáticamente integrales. Por ejemplo, esto es cierto para el politopo de orden de cualquier conjunto parcialmente ordenado , un politopo definido por desigualdades por pares entre coordenadas correspondientes a elementos comparables en el conjunto. [3]
Complejidad computacional
Para un politopo descrito por desigualdades lineales, cuando el politopo no es integral, se puede probar su no integralidad encontrando un vértice cuyas coordenadas no sean números enteros. Dicho vértice se puede describir de manera combinatoria especificando un subconjunto de desigualdades que, cuando se convierten en un sistema de ecuaciones lineales , tienen una solución única y verificando que este punto de solución obedece a todas las demás desigualdades. Por lo tanto, probar la integralidad pertenece a la clase de complejidad coNP de problemas para los que se puede probar fácilmente una respuesta negativa. Más específicamente, es coNP-completo . [4]
Objetos relacionados
Muchas de las propiedades importantes de un politopo integral, incluido su volumen y número de vértices, están codificadas por su polinomio de Ehrhart . [5]
Los politopos integrales se destacan de manera destacada en la teoría de las variedades tóricas , donde corresponden a variedades tóricas proyectivas polarizadas. Por ejemplo, la variedad tórica correspondiente a un simplex es un espacio proyectivo . La variedad tórica correspondiente a un cubo unitario es la incrustación Segre del-Doble producto de la línea proyectiva. [ cita requerida ]
En geometría algebraica , una instancia importante de politopos de celosía llamados politopos de Newton son los cascos convexos de vectores que representan los exponentes de cada variable en términos de un polinomio . Por ejemplo, el polinomio tiene cuatro términos, con vector exponente (1,1), con vector exponente (2,0), con vector exponente (0,5), y con vector exponente (0,0). Su politopo de Newton es el casco convexo de los cuatro puntos (1,1), (2,0), (0,5) y (0,0). Este casco es un triángulo integral con el punto (1,1) dentro del triángulo y los otros tres puntos como vértices.
Referencias
- ^ Cornuéjols, Gérard (2001), Optimización combinatoria: empaque y cobertura , Serie de conferencias regionales CBMS-NSF en matemáticas aplicadas, 74 , Filadelfia, Pensilvania: Sociedad de matemáticas industriales y aplicadas (SIAM), p. 4, doi : 10.1137 / 1.9780898717105 , ISBN 0-89871-481-8, MR 1828452
- ^ Murota, Kazuo (2003), Análisis convexo discreto , SIAM Monographs on Discrete Mathematics and Applications, Filadelfia, Pensilvania: Sociedad de Matemáticas Industriales y Aplicadas (SIAM), p. 90, doi : 10.1137 / 1.9780898718508 , hdl : 2433/149564 , ISBN 0-89871-540-7, Señor 1997998
- ^ Stanley, Richard P. (1986), "Two poset polytopes", Geometría discreta y computacional , 1 (1): 9-23, doi : 10.1007 / BF02187680 , MR 0824105
- ^ Ding, Guoli; Feng, Li; Zang, Wenan (2008), "La complejidad de reconocer sistemas lineales con ciertas propiedades de integralidad", Programación matemática, Serie A , 114 (2): 321–334, doi : 10.1007 / s10107-007-0103-y , hdl : 10722 / 58972 , MR 2393045
- ^ Barvinok, AI (1994), "Computación del polinomio de Ehrhart de un politopo de celosía convexa", Geometría discreta y computacional , 12 (1): 35–48, doi : 10.1007 / BF02574364 , MR 1280575