Otimização em Grafos: Problemas e Modelos
Classificado em Tecnologia
Escrito em em português com um tamanho de 7,12 KB
Problema do Carteiro Chinês
Este problema surge porque o grafo construído para representar o percurso nem sempre é um grafo euleriano. Portanto, nem sempre é possível computar diretamente um ciclo euleriano (um caminho que percorre todas as arestas exatamente uma vez e retorna ao início).
O critério para um grafo ser euleriano é que todos os seus vértices tenham grau par. No contexto do problema do carteiro, os vértices representam cruzamentos e as arestas representam ruas. Se nem todos os cruzamentos tiverem um número par de ruas conectadas a eles (ou seja, se existirem vértices de grau ímpar), o grafo não será euleriano.
Uma estratégia para transformar o problema em euleriano é modificar o grafo. Isso envolve identificar todos... Continue a ler "Otimização em Grafos: Problemas e Modelos" »