Questões

O procedimento troca de r arestas (r-exchange) é uma das heurísticas de maior sucesso em obter uma solução aproximadamente ótima para o problema do caixeiro-viajante com n vértices. Em relação a esse procedimento, considere as afirmativas a seguir.

I - A partir de um ciclo Hamiltoniano H, o procedimento retira r arestas de H, produzindo r caminhos desconexos e os reconecta usando arestas diferentes daquelas retiradas, produzindo uma nova rota H’.

II - De um ciclo Hamiltoniano H é produzido um novo ciclo H’, o qual difere de H em exatamente r arestas, as demais (n-r) arestas coincidem.

III - Caso o custo de H’, produzido a partir da troca de r arestas de um ciclo Hamiltoniano H, seja maior que o custo de H, então H é substituído por H’, senão um novo conjunto de r arestas de H é selecionado para troca.

IV - O processo de troca de r arestas é repetido até que nenhuma melhora adicional seja alcançada.

V - O procedimento r-exchange termina em um ótimo global, chamado de r-ótimo ou r-opt.

São corretas APENAS as afirmativas

Um grafo é uma estrutura de dados consistida em um conjunto de nós (ou vértices) e um conjunto de arcos (ou arestas). O grafo em que os arcos possuem um número ou peso associados a eles, é chamado de grafo

Na teoria dos grafos, dois nós ligados por um arco são chamados de nós

Um grafo completo contém pelo menos um subgrafo ponderado.

É misto o grafo com arestas não dirigidas que representam ruas de dois sentidos e com arestas dirigidas que correspondem a trechos de um único sentido, modelado para representar o mapa de uma cidade cujos vértices sejam os cruzamentos ou finais de ruas e cujas arestas sejam os trechos de ruas sem cruzamentos.

Um grafo que não possui ciclos é chamado de conexo.

Julgue os itens a seguir, relativos aos tipos básicos de estruturas.


Define-se um grafo como fortemente conexo se todos os nós puderem ser atingidos a partir de qualquer outro nó.