Problema de inspeção de rota - Route inspection problem

Na teoria dos grafos , um ramo da matemática e da ciência da computação , o problema do carteiro chinês , o passeio do carteiro ou o problema de inspeção de rota é encontrar um caminho ou circuito fechado mais curto que visite cada borda de um gráfico não direcionado (conectado) . Quando o gráfico tem um circuito Euleriano (uma caminhada fechada que cobre todas as arestas uma vez), esse circuito é uma solução ótima. Caso contrário, o problema de otimização é encontrar o menor número de arestas do gráfico para duplicar (ou o subconjunto de arestas com o peso total mínimo possível) de modo que o multigrafo resultante tenha um circuito Euleriano. Pode ser resolvido em tempo polinomial .

O problema foi originalmente estudado pelo matemático chinês Kwan Mei-Ko em 1960, cujo artigo chinês foi traduzido para o inglês em 1962. O nome original "problema do carteiro chinês" foi cunhado em sua homenagem; fontes diferentes atribuem a cunhagem a Alan J. Goldman ou Jack Edmonds , ambos do Bureau Nacional de Padrões dos Estados Unidos na época.

Uma generalização é escolher qualquer conjunto T de diversos uniformemente vértices que são para serem unidas por um conjunto de arestas no gráfico cujo ângulo diferente graus vértices são precisamente aquelas de T . Esse conjunto é chamado de T -join. Este problema, o problema T -join , também pode ser resolvido em tempo polinomial pela mesma abordagem que resolve o problema do carteiro.

Solução não direcionada e T -joins

O problema de inspeção de rota não direcionada pode ser resolvido em tempo polinomial por um algoritmo baseado no conceito de um T -join. Seja T um conjunto de vértices em um gráfico. Um set borda J é chamado de T -Junte se a coleção de vértices que têm um número ímpar de arestas incidentes em J é exatamente conjunto do T . Um t -Junte existe sempre que cada componente ligado do gráfico contém um número par de vértices em T . O problema da união em T é encontrar uma união em T com o número mínimo possível de arestas ou o peso total mínimo possível.

Para qualquer T , um menor T -join (quando existe) consiste necessariamente em caminhos que unem os vértices de T em pares. Os caminhos serão tais que o comprimento total ou peso total de todos eles seja o menor possível. Em uma solução ideal, dois desses caminhos não compartilharão nenhuma aresta, mas podem ter vértices compartilhados. Um T -join mínimo pode ser obtido construindo um grafo completo nos vértices de T , com arestas que representam os caminhos mais curtos no grafo de entrada dado, e então encontrando uma correspondência perfeita de peso mínimo neste grafo completo. As arestas desse casamento representam caminhos no grafo original, cuja união forma o T -join desejado . A construção do gráfico completo e, em seguida, a localização de uma correspondência nele podem ser feitas em O ( n 3 ) etapas computacionais.

Para o problema de inspeção de rota, T deve ser escolhido como o conjunto de todos os vértices de grau ímpar. Pelas suposições do problema, o gráfico inteiro está conectado (caso contrário, não existe nenhum passeio) e, pelo lema do aperto de mão, ele tem um número par de vértices ímpares, então sempre existe um T -join. Dobrar as arestas de um T -join faz com que o grafo dado se torne um multigrafo Euleriano (um grafo conectado em que cada vértice tem grau par), do qual segue que tem um passeio de Euler , um passeio que visita cada aresta do multigrafo exatamente uma vez. Este passeio será uma solução ideal para o problema de inspeção de rota.

Solução direcionada

Em um gráfico direcionado, as mesmas idéias gerais se aplicam, mas técnicas diferentes devem ser usadas. Se o gráfico direcionado for Euleriano, basta encontrar um ciclo de Euler. Se não for, deve-se encontrar T -joins, o que, neste caso, envolve encontrar caminhos a partir dos vértices com um grau maior que seu grau para aqueles com um grau maior que seu grau de modo que eles fariam em grau de cada vértice igual ao seu grau externo. Isso pode ser resolvido como uma instância do problema de fluxo de custo mínimo, no qual há uma unidade de suprimento para cada unidade de excesso em grau e uma unidade de demanda para cada unidade de excesso de grau externo. Como tal, é solucionável em tempo O (| V | 2 | E |). Existe uma solução se e somente se o gráfico fornecido estiver fortemente conectado .

Problema com o carteiro ventoso

O problema do carteiro ventoso é uma variante do problema de inspeção de rota em que a entrada é um gráfico não direcionado, mas onde cada aresta pode ter um custo diferente para percorrê-la em uma direção do que para percorrê-la na outra direção. Em contraste com as soluções para gráficos direcionados e não direcionados, é NP-completo .

Formulários

Vários problemas combinatórios foram reduzidos ao Problema do Carteiro Chinês, incluindo encontrar um corte máximo em um gráfico planar e um circuito de comprimento médio mínimo em um gráfico não direcionado.

Variantes

Algumas variantes do Problema do Carteiro Chinês foram estudadas e mostraram-se NP-completas .

  • O problema do carteiro chinês para grafos mistos: para este problema, algumas das arestas podem ser direcionadas e, portanto, só podem ser visitadas de uma direção. Quando o problema exige uma travessia mínima de um dígrafo (ou multidígrafo), é conhecido como o "problema do Varredor de Rua de Nova York".
  • O problema do carteiro k- chinês: encontre k ciclos todos começando em um local designado de forma que cada aresta seja atravessada por pelo menos um ciclo. O objetivo é minimizar o custo do ciclo mais caro.
  • O "Problema do Carteiro Rural": resolva o problema com algumas arestas desnecessárias.

Veja também

Referências

links externos