GabaritoB — 99.
Gabarito: letra B. Um grafo conexo e acíclico é uma árvore. Uma árvore com n vértices possui exatamente n-1 arestas. Portanto, para 100 vértices, o número máximo de arestas que mantém o grafo conexo e sem ciclos é 99. Esse é um resultado clássico da Teoria dos Grafos.
A banca testa o conhecimento sobre a relação entre vértices e arestas em árvores. A pegadinha comum é confundir com o número de arestas em um grafo completo (que para 100 vértices seria 100*99/2 = 4950), mas aqui as restrições são conexo e acíclico.
98 arestas seria insuficiente para conectar todos os 100 vértices: uma árvore precisa de n-1 arestas; com 98 o grafo teria pelo menos dois componentes, não sendo conexo.
99 arestas é exatamente o número de arestas de uma árvore com 100 vértices. É a quantidade máxima que mantém o grafo acíclico e conexo.
100 arestas ultrapassa n-1, formando pelo menos um ciclo. O grafo deixa de ser acíclico.
101 arestas também forma ciclo(s), falhando na condição de ser acíclico.
Lembre-se da fórmula arestas = vértices - 1 para árvores. Em provas de concurso, essa relação é frequentemente cobrada. Decore: "árvore com n vértices tem n-1 arestas".
Gabarito: letra B (99 arestas).
Link permanente: /questoes/qg120162