El problema del cartero chino

En teoría de grafos y optimización combinatoria , el problema de ruta de Guan , el problema del cartero chino , el problema de recorrido del cartero o el problema de inspección de ruta consiste en encontrar el camino cerrado más corto o circuito que visite cada arista de un grafo no dirigido (conectado) al menos una vez. Cuando el grafo tiene un circuito euleriano (un camino cerrado que cubre cada arista una vez), ese circuito es una solución óptima. De lo contrario, el problema de optimización consiste en encontrar el número más pequeño de aristas del grafo para duplicar (o el subconjunto de aristas con el peso total mínimo posible) de modo que el multigrafo resultante tenga un circuito euleriano. ^{[ 1 ]} Se puede resolver en tiempo polinomial , ^{[ 2 ]} a diferencia del problema del viajante de comercio , que es NP-difícil . ^{[ 3 ]} Se diferencia del problema del viajante de comercio en que el viajante de comercio no puede repetir nodos visitados y no tiene que visitar cada arista.

El problema fue estudiado originalmente por el matemático chino Meigu Guan en 1960, cuyo artículo en chino fue traducido al inglés en 1962. ^{[ 4 ]} El nombre original "problema del cartero chino" fue acuñado en su honor; diferentes fuentes atribuyen la creación del nombre a Alan J. Goldman o a Jack Edmonds , ambos empleados de la Oficina Nacional de Estándares de EE . UU . en ese momento. ^{[ 5 ] [ 6 ]}

Una generalización toma como entrada cualquier conjunto T con igual número de vértices y debe producir como salida un conjunto de aristas de peso mínimo en el grafo cuyos vértices de grado impar sean precisamente los de T. Esta salida se denomina unión T. Este problema, el problema de la unión T , también se puede resolver en tiempo polinomial mediante el mismo método que resuelve el problema del cartero.

El problema de inspección de rutas no dirigidas se puede resolver en tiempo polinomial mediante un algoritmo basado en el concepto de T- unión. Sea T un conjunto de vértices en un grafo. Un conjunto de aristas J se denomina T -unión si la colección de vértices que tienen un número impar de aristas incidentes en J es exactamente el conjunto T. Existe una T -unión siempre que cada componente conexa del grafo contenga un número par de vértices en T. El problema de la T -unión consiste en encontrar una T -unión con el mínimo número posible de aristas o el mínimo peso total posible.

Para cualquier T , una unión T más pequeña (cuando existe) necesariamente consiste en${\displaystyle {\tfrac {1}{2}}|T|}$Caminos que unen los vértices de T en pares. Los caminos serán tales que la longitud o el peso total de todos ellos sea lo más pequeño posible. En una solución óptima, ningún par de estos caminos compartirá ninguna arista, pero pueden tener vértices compartidos. Se puede obtener una unión T mínima construyendo un grafo completo sobre los vértices de T , con aristas que representan los caminos más cortos en el grafo de entrada dado, y luego encontrando un emparejamiento perfecto de peso mínimo en este grafo completo. Las aristas de este emparejamiento representan caminos en el grafo original, cuya unión forma la unión T deseada ^. Tanto la construcción del grafo completo como la búsqueda de un emparejamiento en él se pueden realizar en O( n³ ) pasos computacionales.

Para el problema de inspección de rutas, se debe elegir T como el conjunto de todos los vértices de grado impar. Según las suposiciones del problema, todo el grafo es conexo (de lo contrario no existe un recorrido), y por 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 unión T hace que el grafo dado se convierta en un multigrafo euleriano (un grafo conexo en el que cada vértice tiene grado par), de lo cual se deduce que tiene un recorrido euleriano , un recorrido que visita cada arista del multigrafo exactamente una vez. Este recorrido será una solución óptima al problema de inspección de rutas. ^{[ 7 ] [ 2 ]}

En un grafo dirigido, se aplican las mismas ideas generales, pero se deben utilizar técnicas diferentes. Si el grafo dirigido es euleriano, basta con encontrar un ciclo de Euler. Si no lo es, se deben encontrar T -uniones, lo que en este caso implica encontrar caminos desde vértices con un grado de entrada mayor que su grado de salida hacia aquellos con un grado de salida mayor que su grado de entrada , de manera que el grado de entrada de cada vértice sea igual a su grado de salida. Esto se puede resolver como una instancia del problema de flujo de costo mínimo, en el que hay una unidad de oferta por cada unidad de exceso de grado de entrada, y una unidad de demanda por cada unidad de exceso de grado de salida. Por lo tanto, es resoluble en tiempo O(| V | ² | E |). Existe una solución si y solo si el grafo dado es fuertemente conexo . ^{[ 2 ] [ 8 ]}

Diversos problemas combinatorios se han reducido al problema del cartero chino, incluyendo encontrar un corte máximo en un grafo planar y un circuito de longitud media mínima en un grafo no dirigido. ^{[ 9 ]}

Se han estudiado algunas variantes del problema del cartero chino y se ha demostrado que son NP-completas . ^{[ 10 ]}

• El problema del cartero ventoso es una variante del problema de inspección de rutas en la que la entrada es un grafo no dirigido, pero donde cada arista puede tener un costo diferente para recorrerla en una dirección que para recorrerla en la otra. A diferencia de las soluciones para grafos dirigidos y no dirigidos, es NP-completo . ^{[ 11 ] [ 12 ]}
• El problema del cartero chino mixto : en este problema, algunas aristas pueden ser dirigidas y, por lo tanto, solo pueden visitarse desde una dirección. Cuando el problema requiere un recorrido mínimo de un digrafo (o multidigrafo), se conoce como el "problema del barrendero de Nueva York". ^{[ 13 ]}
• El problema del cartero chino k : encontrar k ciclos que comiencen en una ubicación designada, de manera que cada arista sea recorrida por al menos un ciclo. El objetivo es minimizar el costo del ciclo más costoso.
• El "Problema del cartero rural": resolver el problema con algunos bordes no necesarios. ^{[ 12 ]}

• El problema del viajante
• Enrutamiento de arco
• Problema del cartero chino mixto

• Weisstein, Eric W. , "Problema del cartero chino" , MathWorld
• Contenido multimedia relacionado con el problema de la inspección de rutas en Wikimedia Commons.