Problema del cartero chino

En teoría de grafos, una rama de las matemáticas y la informática, el problema de la ruta de Guan, el problema del cartero chino, recorrido del cartero o problema de inspección de ruta es encontrar la ruta o circuito cerrado más corto que visita cada borde de un gráfico no dirigido (conectado) al menos una vez. Cuando el gráfico tiene un circuito euleriano (un camino cerrado que cubre cada borde una vez), ese circuito es una solución óptima. De lo contrario, el problema de optimización es encontrar el menor número de aristas del gráfico para duplicar (o el subconjunto de aristas con el mínimo peso total posible) para que el multigrafo resultante tenga un circuito euleriano. Se puede resolver en tiempo polinomial.

El problema fue estudiado originalmente por el matemático chino Kwan Mei-Ko en 1960, cuyo artículo chino se tradujo al inglés en 1962. El nombre original "problema del cartero chino" fue acuñado en su honor; diferentes fuentes atribuyen la acuñación a Alan J. Goldman o Jack Edmonds, quienes estaban en la Oficina Nacional de Normas de EE. UU. En ese momento.

Una generalización es elegir cualquier conjunto T de muchos vértices iguales que se unirán mediante un conjunto de aristas en el gráfico cuyos vértices de grado impar sean precisamente los de T. Este conjunto se denomina combinación T. Este problema, el problema T-join, también se puede resolver en tiempo polinomial con el mismo enfoque que resuelve el problema del cartero.

Solución no dirigida y uniones en T

El problema de inspección de rutas no dirigidas se puede resolver en tiempo polinomial mediante un algoritmo basado en el concepto de unión T. Sea T un conjunto de vértices en un gráfico. Un conjunto de aristas J se denomina T-unión si la colección de vértices que tiene un número impar de aristas incidentes en J es exactamente el conjunto T. Una combinación T existe siempre que cada componente conectado del gráfico contiene un número par de vértices en T. El problema de unión T es encontrar una unión T con el mínimo número posible de aristas o el mínimo peso total posible.

Para cualquier T, un más pequeño T-join (cuando existe) consiste necesariamente en 12SilencioTSilencio{fnMicroc} {1}{2} caminos que se unen a los vértices de T en parejas. Los caminos serán tales que la longitud total o el peso total de todos ellos es lo más pequeño posible. En una solución óptima, no dos de estos caminos compartirán ningún borde, pero pueden tener vértices compartidos. Un mínimo T- la unión se puede obtener mediante la construcción de un gráfico completo en los vértices T, con bordes que representan caminos más cortos en el gráfico de entrada dado, y luego encontrar un peso mínimo perfecto que coincida en este gráfico completo. Los bordes de este emparejado representan caminos en el gráfico original, cuya unión forma el deseado T- Hola. Ambos construir el gráfico completo, y luego encontrar una coincidencia en él, se puede hacer en O(n³) pasos computacionales.

Para el problema de inspección de ruta, se debe elegir T como el conjunto de todos los vértices de grado impar. Según los supuestos del problema, todo el grafo está conectado (de lo contrario, no existe ningún recorrido) y, según el lema del apretón de manos, tiene un número par de vértices impares, por lo que siempre existe una unión T. Duplicar las aristas de una combinación T hace que el grafo dado se convierta en un multigrafo euleriano (un grafo conexo en el que cada vértice tiene un grado par), de lo que se deduce que tiene un recorrido de Euler, un recorrido que visita cada borde del multigrafo exactamente una vez. Este recorrido será una solución óptima al problema de inspección de ruta.

Solución dirigida

En un gráfico dirigido, se aplican las mismas ideas generales, pero se deben usar diferentes técnicas. Si el grafo dirigido es euleriano, basta con encontrar un ciclo de Euler. Si no es así, se deben encontrar las uniones T, lo que en este caso implica encontrar caminos desde los vértices con un grado de entrada mayor que su grado de salida hasta aquellos con un grado de salida mayor que su entrada. -grado tal que harían el grado de entrada de cada vértice igual a su grado de salida. Esto se puede resolver como un ejemplo del problema de flujo de costo mínimo en el que hay una unidad de oferta por cada unidad de exceso de entrada y una unidad de demanda por cada unidad de exceso de salida. Como tal, se puede resolver en tiempo O(|V|²|E|). Existe una solución si y solo si la gráfica dada es fuertemente conexa.

Aplicaciones

Varios problemas combinatorios se han reducido al problema del cartero chino, incluido encontrar un corte máximo en un gráfico plano y un circuito de longitud media mínima en un gráfico no dirigido.

Variantes

Se han estudiado algunas variantes del problema del cartero chino y se ha demostrado que son NP-completas.

• El problema del cartero ventoso es una variante del problema de inspección de ruta en el que la entrada es un gráfico no dirigido, pero donde cada borde puede tener un costo diferente para atravesarlo en una dirección que para atravesarlo en la otra dirección. En contraste con las soluciones para gráficos dirigidos y no dirigidos, es NP-completo.
• El problema del cartero chino mixto: para este problema, algunos de los bordes pueden ser dirigidos y por lo tanto sólo pueden ser visitados desde una dirección. Cuando el problema requiere un mínimo traversal de un digraph (o multidigraph) se conoce como el "problema de la calle Nueva York".
• El k- Problema del cartero chino: encontrar k ciclos todos comenzando en un lugar designado tal que cada borde se atraviesa por al menos un ciclo. El objetivo es minimizar el coste del ciclo más caro.
• El "Problema Postrural": resolver el problema con algunos bordes no requeridos.