POSCOMP 2019: Questão 32 Resolvida (Teoria dos Grafos)

Questão

Sobre grafos, assinale a alternativa correta.

• (A) Um grafo ponderado é um grafo não direcionado em que todos os pares de vértices são adjacentes, isto é, há arestas ligando todos os vértices entre si.
• (B) Todo grafo completo tem pesos associados às suas arestas.
• (C) Um caminho em um grafo é complexo se todos os vértices do caminho são distintos.
• (D) O grau de um vértice em um grafo não direcionado é o número de arestas que incidem nele.
• (E) Se existir um caminho c de x a y, então x é alcançável a partir de c via y.

Resolução

A alternativa A está errada, pois um grafo ponderado (ou valorado) é um grafo em que as arestas possuem um peso associado. Um grafo onde todos os pares de vértices são adjacentes é denominado grafo completo.

A alternativa B está errada, pois um grafo completo pode ou não ter pesos associados às suas arestas.

A alternativa C também está errada, já que um caminho em um grafo onde todos os vértices são distintos é denominado caminho simples.

A alternativa E está incorreta, uma vez que se existir um caminho c de x a y, então o correto é dizer que y é alcançável a partir de x via c.

A alternativa D é a correta.

Mais questões

Se você deseja mais questões resolvidas do POSCOMP 2019, acesse a tag Questões do POSCOMP 2019.

Agora, se você procura questões, gabaritos e caderno de questões de outras edições, então acesse a página POSCOMP.

Resolverei as questões conforme o tempo permitir e de acordo com os meus conhecimentos. Como eu não sei resolver todas as questões, recomendo que você consulte também o gabarito oficial do exame.

Referências

• [1] SOUSA, E. P. M.; CIFERRI, C. D. A. Grafos - Conceitos Básicos (Parte 1). ICMC-USP. Acesso em 15 de março de 2020.
• [2] CARVALHO, M. A. G. Teoria dos Grafos - Uma Introdução. UNICAMP: Limeira, 2005. Acesso em 15 de março de 2020.
• [3] FEOFILOFF, P. Caminhos e ciclos em grafos. IME-USP. Acesso em 15 de março de 2020.