Problema da inspeção de rotas

Em teoria dos grafos, um ramo da matemática, o problema do carteiro chinês (PCC), circuito do carteiro ou problema da inspeção de rotas consiste em encontrar um caminho mais curto ou circuito fechado que visite cada aresta de um grafo (conectado) não-direcionado. Quando o grafo possui um circuito euleriano (um passeio fechado que abrange toda aresta uma vez), esse circuito é uma solução ótima.

Alan Goldman do U.S. National Bureau of Standards cunhou pela primeira vez o nome 'problema do carteiro chinês' para este problema, uma vez que foi originalmente estudado pelo matemático chinês Mei-Ku Kuan em 1962.

Caminhos e circuitos eulerianos

Para que um grafo tenha um circuito euleriano, ele certamente terá que estar conectado.

Suponha que temos um grafo conexo G = (V, E), as seguintes declarações são equivalentes:

1. Todos os vértices de G têm grau par.
2. G consiste das arestas de uma união disjunta de alguns ciclos, e os vértices destes ciclos.
3. G tem um circuito euleriano.

• 1 → 2 pode ser demonstrado por indução sobre o número de ciclos.
• 2 → 3 também pode ser demonstrado por indução sobre o número de ciclos, e
• 3 → 1 deve ser imediata.

Um caminho euleriano (um caminho que não é fechado, mas utiliza todas as arestas de G apenas uma vez) existe se e somente se G é conectado e tem exatamente dois vértices de valência ímpar.

Junções-T

Seja T um subconjunto do conjunto de vértices de um grafo. Um conjunto de arestas cujos vértices de grau ímpar são os vértices em T é chamado de junção-T. (Em um grafo conexo uma junção-T existe se e somente se |T| é par). O problema da junção-T consiste em encontrar a menor junção-T. A menor junção-T leva a uma solução do problema do carteiro chinês. Uma menor junção-T consiste necessariamente de ${\tfrac {1}{2}}$|T| caminhos, não havendo dois com uma aresta em comum, que unem os vértices de T em pares. Os percursos serão de tal forma que o comprimento total de todos eles é tão pequeno quanto possível. Uma junção-T mínima pode ser obtida por um algoritmo de correspondência ponderada que usa O(n³) passos computacionais

Solução

Se um grafo tem um circuito euleriano (ou um caminho euleriano), então um circuito euleriano (ou caminho) visita cada aresta, e assim a solução é escolher qualquer circuito euleriano (ou caminho).

Se o grafo não é euleriano, deve conter vértices de grau ímpar. Pelo lema do aperto de mãos, deve haver um número par desses vértices. Para resolver o problema do carteiro chinês primeiro encontramos a menor junção-T. Nós fazemos o grafo virar euleriano pela duplicação da junção-T. A solução para o problema do carteiro chinês no grafo original é obtida por encontrar um circuito euleriano para o novo grafo.

Variantes

A poucas variantes do problema do carteiro chinês têm sido estudadas e mostraram-se NP-completas.

• (Minimização) Problema do carteiro chinês para grafos mistos: para este problema, algumas das arestas podem ser direcionadas e só podem ser visitadas a partir de uma direção. Quando o problema é transversal mínimo de um digrafo é conhecido como o "problema do varredor de New York Street".
• (Minimização) Problema do carteiro k-Chinês: encontrar todos os ciclos de k elementos a partir de um local designado de tal forma que cada aresta seja atravessada por pelo menos um ciclo. O objetivo é minimizar o custo do ciclo mais caro.
• Problema do carteiro rural: é dado também um subconjunto das arestas. Encontre o mais barato ciclo hamiltoniano contendo cada uma dessas arestas (e possivelmente outras). Este é um caso especial do problema geral de roteamento mínimo que especifica com precisão quais vértices o ciclo deve conter.

Ver também

• Problema do caixeiro-viajante

Exemplo de Aplicação

Distribuição das vacinas da COVID-19

Neste artigo, buscamos obter o melhor caminho para distribuir as vacinas contra o COVID-19 na 11ª Regional de Saúde do Paraná, formada por 25 municípios com sede na cidade de Campo Mourão, por meio do problema do Carteiro Chinês.

Ligações externas

• Problema do carteiro chinês