Dado um grafo simples não direcionado com V vértices e E arestas, qual condição necessária e suficiente…

Questão

Dado um grafo simples não direcionado com V vértices e E arestas, qual condição necessária e suficiente (usando V, E e conectividade) para que o grafo seja uma árvore?

1. A) Um grafo com menos de V - 1 arestas é uma árvore.
2. B) Um grafo é árvore se for desconectado e E = V - 1.
3. C) Um grafo é árvore se V = 0 e E = 0.
4. D) O grafo é árvore se, e somente se, for conectado e E = V - 1.
5. E) Um grafo é árvore se for conectado e E = V + 1.

✅ Resposta correta: alternativa D

Resolução passo a passo

1. Lembre a definição: uma árvore é um grafo simples, não direcionado, conexo e sem ciclos (acíclico).
2. Um resultado clássico da teoria dos grafos diz que, em um grafo com V vértices, são equivalentes: ser árvore; ser conexo com E = V - 1; ser acíclico com E = V - 1. Portanto, para caracterizar árvore usando V, E e conectividade, basta exigir conectividade e E = V - 1.
3. Verifique que a condição é necessária: toda árvore com V vértices tem exatamente V - 1 arestas, pois cada vértice além do primeiro entra ligado por uma única aresta ao restante ao ser adicionado na ordem de uma busca.
4. Verifique que a condição é suficiente: um grafo conexo com V vértices e V - 1 arestas não pode conter ciclo, pois um grafo conexo com um ciclo teria mais arestas do que o necessário para conectar os vértices; logo é acíclico e conexo, ou seja, é árvore.
5. Analise as alternativas. A) está errada, pois um grafo com poucas arestas pode ser desconectado (por exemplo, sem arestas), e não é árvore. B) está errada, pois exige desconexão, o que contradiz a conectividade necessária para ser árvore. C) está errada, pois o grafo vazio sem vértices não é uma árvore usual, e a condição não caracteriza árvores em geral. E) está errada, pois um grafo conexo com V + 1 arestas tem obrigatoriamente um ciclo.
6. Conclusão: a alternativa correta é a D, que coincide com o gabarito oficial.

💡 Dica: Lembre-se da definição de árvore em grafos.

Alternativa por alternativa

Raio-X da questão

Questões parecidas com resolução

• Para organizar uma exposição escolar, a turma desenhou as ligações diretas entre quatro setores. Cada letra indica um…
• Técnicos instalam uma rede de comunicação por cabos entre os postos de uma reserva ambiental. Os postos são Riacho…
• Moradores acompanham a criação de um aplicativo para orientar deslocamentos durante a feira do bairro. No mapa…
• Durante os preparativos para uma feira de ciências no bairro, a organização desenhou um mapa digital dos caminhos…
• Por que uma rede de aviso precisa continuar funcionando mesmo quando um ponto para de operar? Em uma cidade litorânea, a…
• — Dá para passar por todas as ruas sem repetir nenhuma? — perguntou um morador, ao ver o triciclo do mutirão de coleta…

Todas as questões de Programação - Propriedades de grafos