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 rutas consiste en encontrar un camino o circuito cerrado más corto que visite cada borde de un gráfico no dirigido (conectado) al menos una vez. . Cuando el gráfico tiene un circuito euleriano (un recorrido 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. [1] Se puede resolver en tiempo polinómico , [2] a diferencia del problema del viajante , que es NP-difícil . [3] Se diferencia del problema del viajante en que el viajante no puede repetir los nodos visitados.
El problema fue estudiado originalmente por el matemático chino Kwan Mei-Ko 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 acuñación a Alan J. Goldman o Jack Edmonds , quienes estaban en la Oficina Nacional de Estándares de EE. UU . en ese momento. [5] [6]
Una generalización consiste en elegir cualquier conjunto T de igual número de vértices que se unirán mediante un conjunto de aristas en el gráfico cuyos vértices de grado impar sean precisamente los de T. Un conjunto de este tipo se llama unión en T. Este problema, el problema de unión en T , también se puede resolver en tiempo polinomial mediante el mismo enfoque que resuelve el problema del cartero.
El problema de inspección de rutas no dirigidas se puede resolver en tiempo polinómico mediante un algoritmo basado en el concepto de unión en T. Sea T un conjunto de vértices en un gráfico. Un conjunto de aristas J se denomina unión en T si la colección de vértices que tienen un número impar de aristas incidentes en J es exactamente el conjunto T. Una unión en T existe siempre que cada componente conectado del gráfico contenga un número par de vértices en T. El problema de la unión en T consiste en encontrar una unión en T 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 consta de 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 el menor posible. En una solución óptima, dos de estos caminos no compartirán ningún borde, pero pueden haber compartido vértices. Se puede obtener una unión T mínima construyendo un gráfico completo en los vértices de T , con aristas que representen los caminos más cortos en el gráfico de entrada dado, y luego encontrando una coincidencia perfecta de peso mínimo en este gráfico completo. Los bordes de esta coincidencia representan caminos en el gráfico original, cuya unión forma la unión en T deseada . Tanto construir el gráfico completo como luego encontrar una coincidencia en él se puede realizar en O ( n 3 ) pasos computacionales.
Para el problema de inspección de rutas, se debe elegir T como el conjunto de todos los vértices de grados impares. Según los supuestos del problema, todo el gráfico está conectado (de lo contrario, no existe ningún recorrido) y según el lema del protocolo de enlace tiene un número par de vértices impares, por lo que siempre existe una unión en T. Duplicar las aristas de una unión T hace que el gráfico dado se convierta en un multigrafo euleriano (un gráfico 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 rutas. [7] [2]
En un gráfico dirigido, se aplican las mismas ideas generales, pero se deben utilizar técnicas diferentes. Si el grafo dirigido es euleriano, sólo es necesario encontrar un ciclo de Euler. Si no es así, se deben encontrar uniones en 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 modo que hagan El grado de entrada de cada vértice es igual a su grado de salida. Esto puede resolverse 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 grado de entrada y una unidad de demanda por cada unidad de exceso de grado de salida. Como tal, se puede resolver en tiempo O(| V | 2 | E |). Existe una solución si y sólo si la gráfica dada está fuertemente conexa . [2] [8]
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. [9]
Se han estudiado algunas variantes del problema del cartero chino y se ha demostrado que son NP completo . [10]
Medios relacionados con el problema de inspección de rutas en Wikimedia Commons