Problema del cartero chino

Para que un grafo tenga un circuito euleriano, ciertamente tendrá que estar conectado.

Supongamos que tenemos un grafo conexo G = (V, E); entonces, las siguientes declaraciones son equivalentes:

1. Todos los vértices (nodos) de G tienen grado par.
2. G consiste de las aristas de una unión disjunta de algunos ciclos, y de los vértices de esos ciclos.
3. G tiene un circuito euleriano.

• 1 → 2 puede ser demostrado por indución sobre el número de ciclos;
• 2 → 3 también puede ser demostrado por inducción sobre el número de ciclos; y
• 3 → 1 es inmediata.

Un camino euleriano (un camino que no es cerrado, pero que utiliza todas las aristas de G apenas una vez y solamente una vez) existe si y solamente si G es conectado y tiene dos vértices de valencia impar.

Sea T un subconjunto del conjunto de vértices de un grafo. El conjunto de aristas cuyos vértices de grado impar son los vértices en T es llamado enlace-T (en un grafo conexo, un enlace-T existe si y solamente si |T| es par). El problema del enlace-T consiste en encontrar el menor enlace-T. Y el menor enlace-T necesariamente lleva a una solución del problema del cartero chino.

En efecto, un menor enlace-T necesariamente consiste de ${\displaystyle {\tfrac {1}{2}}}$|T| caminos, no habiendo dos con una arista en común, uniendo los vértices de T en pares. Los recorridos serán de tal forma que la extensión total de cada uno de ellos es tan pequeña como sea posible. Un enlace-T mínimo puede ser obtenido por un algoritmo de correspondencia ponderada que usa O(n³) pasos computacionales.[6]

Si un grafo tiene un circuito euleriano (o un camino euleriano), entonces un circuito euleriano (o camino) visita cada arista, y así la solución resulta ser cualquier circuito euleriano (o camino).

Y si un grafo no es euleriano, debe contener vértices de grado impar, y por aplicación del lema del apretón de manos, debe haber un número par de esos vértices. Entonces, para resolver el problema del cartero chino, primero debemos encontrar el menor enlace-T, y transformamos el grafo original en otro euleriano simplemente duplicando el enlace-T. Resulta entonces que la solución al problema del cartero chino en el grafo original, podrá ser obtenida o generada, sobre la base de la determinación de un circuito euleriano para el nuevo grafo.

Pocas variantes del problema del cartero chino han sido estudiadas en forma exhaustiva (NP-completo).[7]

• (Minimización) Problema del cartero chino para grafos mixtos - En esta situación, algunas de las aristas podrían estar direccionadas y solamente podrían ser recorridas en la dirección permitida. El problema transversal mínimo de un digrafo es conocido como "problema del barrendero callejero de Nueva York".

• (Minimización) Problema del cartero k-Chino - Encontrar todos los ciclos de k elementos a partir de un local designado, de tal forma que cada arista sea atravesada por lo menos por un ciclo. El objetivo es minimizar el costo del ciclo más caro.

• Problema del cartero rural - Dado un subconjunto de aristas, encontrar el ciclo hamiltoniano más barato conteniendo una de esas aristas (y posiblemente otras). Este es un caso especial del problema general del enrutamiento mínimo, que especifica con precisión los vértices o ciclos que debe contener.

El mejor resultado que puede esperarse se obtiene encontrando un camino que pase exactamente una sola vez por cada arista, es decir, un ciclo euleriano. Tal camino existe si y solamente si cada nodo del grafo es de grado par.

En caso contrario, un camino optimal pasa al menos dos veces por una misma arista. En este último caso, es más simple considerar el problema alternativo siguiente: en vez de permitir de pasar varias veces por la misma arista, se duplican las aristas del grafo en donde se permite pasar dos veces. Obviamente, el problema planteado entonces es del mismo tipo, pero ahora aplicado a un grafo diferente.

La idea es naturalmente la de ir ampliando poco a poco el grafo, hasta que el mismo sea euleriano, y cuando se obtenga, buscar un circuito euleriano en el grafo completo.

Para mejor comprender el algoritmo propuesto, es útil comenzar pensando el caso de un grafo en donde solamente se tienen dos nodos u y v de grado impar. Entonces, la solución óptima consiste en encontrar el camino más corto del nodo u al nodo v (utilizando por ejemplo el algoritmo de Dijkstra), completando el grafo con las aristas de este camino.

• Problema del viajante
• Ciclo euleriano
• Algoritmo de Dijkstra

• (en inglés) Chinese Postman Problem.
• (en inglés) Paths, Trees, and Flowers.
• (en inglés) Special Graph Problems.

• Esta obra contiene una traducción parcial derivada de «Problema da inspeção de rotas» de Wikipedia en portugués, publicada por sus editores bajo la Licencia de documentación libre de GNU y la Licencia Creative Commons Atribución-CompartirIgual 4.0 Internacional.
• Esta obra contiene una traducción parcial derivada de «Problème du postier chinois» de Wikipedia en francés, publicada por sus editores bajo la Licencia de documentación libre de GNU y la Licencia Creative Commons Atribución-CompartirIgual 4.0 Internacional.