MO417 - QUESTÃO PARA A PROVA ORAL

Número: 2013-096

Enunciado: O vértice D do grafo abaixo representa uma distribuidora de bebidas, e os demais vértices representam as cidades que um certo caminhoneiro precisará visitar. Ele deve partir da distribuidora e visitar cada cidade exatamente uma vez, retornando para a distribuidora ao final do percurso. As arestas do grafo representam as únicas conexões pelas quais o caminhoneiro pode viajar. Este conjunto de conexões, entretanto, não permite que ele realize o percurso completo sem repetir alguma cidade.

A inclusão de uma única aresta no grafo já seria suficiente para que o caminhoneiro pudesse visitar todos as cidades exatamente uma vez, voltando para a distribuidora ao final. Qual alternativa possui apenas arestas que, se incluídas individualmente no grafo, resolveriam o problema?

1. (B, I), (A, H), (D, F)
2. (D, J), (B, H), (F, A)
3. (A, G), (H, C), (J, B)
4. (C, F), (G, E), (B, I)
5. N. D. A.

Ideia original de: Hilário Seibel Júnior