En matemáticas , una orientación de sumidero única es una orientación de los bordes de un politopo tal que, en cada cara del politopo (incluido todo el politopo como una de las caras), hay exactamente un vértice para el cual todos los bordes contiguos están orientados hacia adentro. (es decir, hacia ese vértice). Si se proporciona un politopo junto con una función objetivo lineal, y los bordes se orientan desde vértices con valores de función objetivo más pequeños hasta vértices con valores objetivos más grandes, el resultado es una orientación de sumidero única. Por lo tanto, se pueden utilizar orientaciones de sumidero únicas para modelar programas lineales , así como ciertos programas no lineales, como el problema del círculo más pequeño .
El problema de encontrar el sumidero en una orientación de sumidero única de un hipercubo fue formulado como una abstracción de problemas de complementariedad lineal por Stickney y Watson (1978) y se denominó "orientación de sumidero única" en 2001 (Szabó y Welzl 2001). Es posible que un algoritmo determine el sumidero único de un hipercubo d -dimensional en el tiempo c d para c < 2 , sustancialmente menor que el tiempo 2 d requerido para examinar todos los vértices. Cuando la orientación tiene la propiedad adicional de que la orientación forma un gráfico acíclico dirigido , lo que sucede cuando se usan orientaciones de sumidero únicas para modelar problemas de tipo LP , es posible encontrar el sumidero usando un algoritmo aleatorio en el tiempo esperado exponencial en la raíz cuadrada. de d (Gärtner 2002).
Un politopo d -dimensional simple es un politopo en el que cada vértice tiene exactamente d aristas incidentes. En una orientación de sumidero único de un politopo simple, cada subconjunto de k aristas entrantes en un vértice v determina una cara k -dimensional para la cual v es el sumidero único. Por lo tanto, el número de caras de todas las dimensiones del politopo (incluido el politopo en sí, pero no el conjunto vacío) se puede calcular mediante la suma del número de subconjuntos de aristas entrantes,
donde G ( P ) es la gráfica del politopo y d en ( v ) es el grado de entrada (número de aristas entrantes) de un vértice v en la orientación dada (Kalai 1988).
De manera más general, para cualquier orientación de un politopo simple, la misma suma cuenta el número de pares incidentes de una cara del politopo y un sumidero de la cara. Y en una orientación acíclica , cada cara debe tener al menos un sumidero. Por lo tanto, una orientación acíclica es una orientación sumidero única si y sólo si no existe otra orientación acíclica con una suma menor. Además, un k -subgrafo regular del gráfico dado forma una cara del politopo si y solo si sus vértices forman un conjunto inferior para al menos una orientación de sumidero única acíclica. De esta manera, la red de caras del politopo se determina de forma única a partir del gráfico (Kalai 1988). Con base en esta estructura, las redes de caras de politopos simples se pueden reconstruir a partir de sus gráficos en tiempo polinomial usando programación lineal (Friedman 2009).
