Algoritmos e Estrutura de Dados · CONSULPAM · 2025 | Questão sqc-qg433559

Algoritmos e Estrutura de DadosEstrutura de Dados

Código: qg433559
Banca: CONSULPAM
Órgão: CONAB
Ano: 2025
Nível: Superior

Cargo: Analista - Tecnologia da Informação (Desenvolvimento)

Em Estruturas de Dados, os Grafos possuem papel ímpar pela sua representação de nós e arestas. Nesse sentido, considere um grafo simples, não direcionado e conexo, contendo n vértices e n arestas. Nesse contexto, considere as sentenças a seguir:I- O grafo necessariamente contém, pelo menos, 1 (um) ciclo.II- Ao representá-lo como matriz de adjacência, haverá exatamente n ² entradas com valor 1 (um).III- A complexidade de tempo de uma busca em profundidade (DFS) para percorrer todos os vértices e arestas é O(log n).IV- Um grafo simples e conexo com n vértices e n arestas pode conter exatamente 2 (dois) vértices de grau 1 (um).Assinale a alternativa com as sentenças CORRETAS sobre o grafo apresentado.

AI e III.
BI e IV.
CII e III.
DII e IV.

Revelar gabarito e comentário

GabaritoB — I e IV.

Comentário gerado por IA. É um apoio ao estudo, ancorado em fontes, mas pode conter imprecisões — confira sempre na fonte oficial (lei, súmula, edital e gabarito da banca). Encontrou um erro? Use “Reportar”.

Grafos: propriedades de um grafo simples, não direcionado e conexo com n vértices e n arestas

Gabarito: letra B (I e IV). Um grafo conexo com n vértices e n arestas possui exatamente um ciclo (I correta); a matriz de adjacência tem $2n$ entradas com valor 1, não $n^2$ (II errada); a complexidade da DFS é $O(n)$ (III errada); e é possível construir tal grafo com exatamente dois vértices de grau 1 (IV correta).

A questão cobra conceitos fundamentais de teoria dos grafos: relação entre arestas e vértices, representação por matriz de adjacência, complexidade de algoritmos de busca e grau dos vértices. Vamos analisar cada afirmativa.

Afirmativa	Análise	Conclusão
I – O grafo necessariamente contém, pelo menos, 1 (um) ciclo.	Grafo conexo com n vértices e n arestas: mínimo para conexidade é n−1 arestas (árvore). Uma aresta extra gera exatamente um ciclo.	Correta
II – Ao representá-lo como matriz de adjacência, haverá exatamente n² entradas com valor 1 (um).	Matriz n×n; cada aresta não direcionada gera duas entradas com 1. Com n arestas, total = 2n, não n².	Incorreta
III – A complexidade de tempo de uma busca em profundidade (DFS) para percorrer todos os vértices e arestas é O(log n).	DFS em lista de adjacência: O(V+E) = O(n+n) = O(n). O(log n) é típico de busca binária.	Incorreta
IV – Um grafo simples e conexo com n vértices e n arestas pode conter exatamente 2 (dois) vértices de grau 1 (um).	Exemplo com n=5: arestas (1-2, 2-3, 3-4, 2-5, 3-5) → graus: 1, 3, 3, 1, 2. Possível.	Correta

Grafo conexo (n vértices, n arestas)

1Propriedades
- Pelo menos 1 ciclo (I)
- Matriz adjacência: n² entradas 1 (II)
- DFS: O(log n) (III)
- Pode ter 2 vértices de grau 1 (IV)

LEVEL · soulevel.com.br

Afirmativa I — ✅ Correta

Em um grafo conexo com $n$ vértices, o número mínimo de arestas para ser conexo é $n-1$ (uma árvore). Se há $n$ arestas, há exatamente uma aresta a mais, o que força a existência de pelo menos um ciclo. Pelo teorema dos grafos, um grafo conexo com $n$ vértices e $n$ arestas possui exatamente um ciclo (é uma árvore mais uma aresta). Portanto, a afirmativa está correta.

Afirmativa II — ❌ Incorreta

A matriz de adjacência de um grafo simples não direcionado com $n$ vértices é $n \times n$ . Por ser não direcionado, para cada aresta $(u,v)$ existem duas entradas com valor 1: $(u,v)$ e $(v,u)$ . Como há $n$ arestas, o número total de entradas com valor 1 é $2n$ , e não $n^2$ . A afirmativa confunde o total de células da matriz com o número de arestas representadas.

Afirmativa III — ❌ Incorreta

A busca em profundidade (DFS) percorre todos os vértices e arestas. Usando lista de adjacência, a complexidade de tempo é $O(V + E)$ , onde $V = n$ e $E = n$ , portanto $O(n)$ . A complexidade $O(\log n)$ é típica de algoritmos de busca binária, não de DFS em grafos.

Afirmativa IV — ✅ Correta

A afirmativa diz que o grafo pode conter exatamente dois vértices de grau 1. Vamos verificar se é possível. Considere um grafo com $n=5$ vértices e $5$ arestas, com arestas: $(1,2), (2,3), (3,4), (2,5), (3,5)$ . Calculando os graus: vértice 1: 1, vértice 2: 3, vértice 3: 3, vértice 4: 1, vértice 5: 2. Temos exatamente dois vértices de grau 1 (1 e 4). A construção é válida: o grafo é simples, não direcionado e conexo. Portanto, a afirmativa está correta.

PEGA ESSA DICA!

Quando um grafo conexo tem $n$ vértices e $n$ arestas, ele possui exatamente um ciclo. A soma dos graus é $2n$ (lema do aperto de mão). Para verificar a possibilidade de vértices de grau 1, tente construir exemplos pequenos.

Gabarito: letra B (I e IV).

Link permanente: /questoes/qg433559