En matemáticas , una orientación de sumidero única es una orientación de las aristas de un politopo tal que, en cada cara del politopo (incluido el politopo completo como una de las caras), hay exactamente un vértice para el cual todas las aristas adyacentes están orientadas hacia adentro (es decir, hacia ese vértice). Si se proporciona un politopo junto con una función objetivo lineal, y las aristas se orientan desde los vértices con valores de función objetivo más pequeños a los vértices con valores objetivos más grandes, el resultado es una orientación de sumidero única. Por lo tanto, las orientaciones de sumidero únicas se pueden utilizar 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 de 2 d requerido para examinar todos los vértices. Cuando la orientación tiene la propiedad adicional de que la orientación forma un grafo acíclico dirigido , lo que sucede cuando se utilizan orientaciones de sumidero únicas para modelar problemas de tipo LP , es posible encontrar el sumidero utilizando un algoritmo aleatorio en el tiempo esperado exponencial en la raíz cuadrada de d (Gärtner 2002).
Un politopo simple de dimensión d 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 de dimensión k para la cual v es el sumidero único. Por lo tanto, el número de caras de todas las dimensiones del politopo (incluido el propio politopo, pero no el conjunto vacío) se puede calcular mediante la suma del número de subconjuntos de aristas entrantes,
donde G ( P ) es el gráfico del politopo, y d in ( 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 de sumidero única si y solo si no hay otra orientación acíclica con una suma menor. Además, un subgrafo k -regular del grafo 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 grafo (Kalai 1988). Con base en esta estructura, las redes de caras de politopos simples se pueden reconstruir a partir de sus grafos en tiempo polinomial utilizando programación lineal (Friedman 2009).
