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 , el recorrido del cartero o el problema de inspección de ruta es encontrar un camino o circuito cerrado más corto que visite cada borde de un grafo no dirigido (conectado) al menos una vez. Cuando el grafo tiene un circuito euleriano (un paseo 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 bordes del grafo para duplicar (o el subconjunto de bordes 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, que es NP-duro . [3] Es diferente del problema del viajante en que el viajante no puede repetir los nodos visitados.
El problema fue estudiado originalmente por el matemático chino Meigu Guan en 1960, cuyo artículo 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 invención a Alan J. Goldman o Jack Edmonds , quienes estaban en la Oficina Nacional de Normas de EE. UU . en ese momento. [5] [6]
Una generalización consiste en elegir cualquier conjunto T de un número par de vértices que se unirán mediante un conjunto de aristas en el grafo cuyos vértices de grado impar sean precisamente los de T. Este conjunto se denomina T -join. Este problema, el problema de T -join , también se puede resolver en tiempo polinomial mediante el mismo enfoque que resuelve el problema del cartero.
El problema de inspección de ruta no dirigida se puede resolver en tiempo polinomial mediante un algoritmo basado en el concepto de una T -join. Sea T un conjunto de vértices en un grafo. Un conjunto de aristas J se denomina T -join si la colección de vértices que tienen un número impar de aristas incidentes en J es exactamente el conjunto T. Una T -join existe siempre que cada componente conectado del grafo contenga un número par de vértices en T. El problema de la T -join consiste en encontrar una T -join con el mínimo número posible de aristas o el mínimo peso total posible.
Para cualquier T , una T -join más pequeña (cuando existe) necesariamente consiste en caminos que unen los vértices de T en pares. Los caminos serán tales que la longitud total o el peso total de todos ellos sea lo más pequeño posible. En una solución óptima, ninguno de estos caminos compartirá ninguna arista, pero pueden tener vértices compartidos. Una T -join mínima se puede obtener construyendo un grafo completo en los vértices de T , con aristas que representan caminos más cortos en el grafo de entrada dado, y luego encontrando una coincidencia perfecta de peso mínimo en este grafo completo. Las aristas de esta coincidencia representan caminos en el grafo original, cuya unión forma la T -join deseada. Tanto la construcción del grafo completo como la posterior búsqueda de una coincidencia en él se pueden realizar en O( n 3 ) pasos computacionales.
Para el problema de inspección de ruta, T debe elegirse como el conjunto de todos los vértices de grado impar. Por los supuestos del problema, todo el grafo está conectado (de lo contrario, no existe ningún recorrido), y por el lema de handshaking tiene un número par de vértices impares, por lo que siempre existe una unión T. Duplicar los bordes de una unión T hace que el grafo dado se convierta en un multigrafo euleriano (un grafo conectado en el que cada vértice tiene 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 para el problema de inspección de ruta. [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, sólo se necesita encontrar un ciclo de Euler. Si no lo es, se deben encontrar 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 grado de entrada de manera que hagan 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 del 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. Como tal, es solucionable en tiempo O(| V | 2 | E |). Existe una solución si y sólo si el grafo dado está fuertemente conectado . [2] [8]
Varios problemas combinatorios se han reducido al problema del cartero chino, incluido el hallazgo de un corte máximo en un gráfico plano y un circuito de longitud media mínima en un gráfico no dirigido. [9]
Se han estudiado algunas variantes del problema del cartero chino y se ha demostrado que son NP-completas . [10]
Medios relacionados con Problema de inspección de ruta en Wikimedia Commons