2024-157

Qual das alternativas difere de forma CORRETA os algoritmos de Prim e Kruskal?

a) O algoritmo de Prim calcula a distância mínima entre dois vértices e o de Kruskal constrói uma árvore geradora mínima

b) Os dois algoritmos constroem uma árvore geradora mínima, mas o de Prim une componentes desconexas até gerar uma árvore, enquanto que o de Kruskal parte de um ponto e mantém uma única árvore que vai sendo aumentada ao longo do algoritmo

c) Os dois algoritmos constroem uma árvore geradora mínima, mas o de Kruskal une componentes desconexas até gerar uma árvore, enquanto que o de Prim parte de um ponto e mantém uma única árvore que vai sendo aumentada ao longo do algoritmo

d) Os dois algoritmos calculam a distância mínima entre dois vértices quaisquer.

e) N.D.A

Ideia original de: Wellington T. A. da Silva 

2024-140

Suponha que temos um grafo \(G\) com \(n\) vértices e \(m\) arestas. Se \(G\) possui um emparelhamento máximo com \(k\) arestas, o que se pode afirmar sobre a relação entre \(n\), \(m\) e \(k\)?

a) \(m/2 \leq k \leq n/2\)

b) \(k \leq m/2\)

c) \(k = n\)

d) \(k \leq n/2\)

e) NDA

Ideia original de: Juan David Nieto 

2024-139

Considere as seguintes afirmações:

I) O algoritmo de Dijkstra serve para encontrar a mínima distância ponderada entre um vértice u e todos outros vértices. 

II) O algoritmo de Kruskal encontra os caminhos mínimos entre quaisquer dois vértices a partir da árvore geradora mínima. 

III) Se os pesos das arestas em um grafo G forem todos diferentes, então o algoritmo de Prim e o Algoritmo de Kruskal irão fornecer a mesma árvore geradora mínima.

IV) O algoritmo de Kruskal tem uma complexidade maior do que o de Prim.

Assinale a alternativa correta:

a) Todas as afirmações são corretas.

b) Apenas as afirmações I e III são corretas.

c) Apenas a afirmação II é correta.

d) Apenas as afirmações I, III e IV são corretas.

e) N.D.A

Ideia Original de: G. Michel Carvalho

2024-138

Considere as afirmações abaixo:

I) Em um ecossistema, existem \(x\) espécies de animais e \(y\) possíveis nichos ecológicos. Suponha que existe um natural \(z\) não nulo com a seguinte propriedade:

Para cada espécie, existem exatamente \(z\) possíveis nichos em que a espécie sobrevive e, para cada nicho, existem exatamente \(z\) espécies de animais que podem habitá-lo.

Então, podemos alocar uma espécie por nicho de modo que todas sobrevivam.

II) Dado um grafo ponderado \(G\) conexo com \(n(G) \geq 2\), então quaisquer duas árvores espalhadas de peso mínimo tem pelo menos uma aresta em comum.

III) Seja \(G\) um grafo simples. Então, \(G\) possui um conjunto independente de \(k\) vértices se, e somente se,  \(\overline{G}\) (complementar de \(G\)) possuí um \(K_k\) como subgrafo. Portanto, o maior clique subgrafo de \(\overline{G}\) tem \(\alpha(G)\) vértices, lembrando que \(\alpha(G)\) é o tamanho de um conjunto independente máximo de \(G\).

São verdadeiras somente:

A) I, III.

B) II, III.

C) I, II.

D) III.

E) NDE

Ideia original de: Gabriel Cruz Vitale Torkomian

2024-137

Qual o menor número de saltos necessários pra chegar no ponto B saindo do ponto A?

                  

Imagem adaptada de uma figura da página https://www.pngwing.com/pt/free-png-vteaz. Acesso em 04/04/2024.

A) 8

B) 9

C) 10

D) 11

E) N.D.A.

Ideia original de: Artur Silveira 

2024-136

Seja um \(P\) um caminho de 5 vértices. Quais rótulos poderiam ser dados a uma bipartição de \(P\) para torná-lo um grafo gracioso?

a) X = {0, 1} e Y = {2, 3, 4}
b) X = {0, 3} e Y = {1, 2 ,4}
c) X = {0, 1, 4} e Y = {2, 3}
d) X = {1, 2} e Y = {0, 3, 4}
e) N.D.A

Ideia original de: Wellington T. A. da Silva

2024-135

Qual das alternativas a seguir está correta?

a) Árvores são grafos acíclicos desconexos.

b) Grafos sem ciclos têm mais vértices que arestas.

c) Uma floresta não tem grafos acíclicos.

d) Um vértice de grau dois forma uma folha.

e) NDA

Ideia original de: Josiane Gaia Pimenta

2024-134

Considere as seguintes afirmações a respeito de árvores:

I) As árvores são grafos conectados e que não possuem ciclos.

II) Toda árvore é um grafo bipartido.

III) Todo grafo bipartido é uma árvore.

IV) Considerando a classe de árvores com quantidade de vértices \(n\), o máximo grau de um vértice que pode-se obter em uma árvore é de \(n-1\).

Assinale a alternativa correta:

a) Apenas as afirmações I, II e III são corretas.

b) Apenas as afirmações I e II são corretas.

c) Apenas as afirmações I, II e  IV são corretas.

d) Todas as afirmações são corretas

e) N.D.A

Ideia original de: G. Michel Carvalho

2024-133

Considere as afirmações abaixo sobre um grafo simples G.

I) Se \(G\) é uma árvore com \( n(G) \geq 3 \), então \( 2 \leq diam(G) \leq n(G)-1 \), onde a igualdade \( 2 = diam(G) \) é válida se, e somente se, \(G\) é uma estrela e a igualdade \( diam(G) = n(G)-1 \) é valida se, e somente se, \( G = P_{n} \).

II) \( raio(G) \leq diam(G) \), com igualdade se, e somente se, todo vértice de \(G\) tem a mesma excentricidade.

III) Considere o grafo abaixo:

Este grafo tem exatamente 4 árvores espalhadas.

Das afirmações, são verdadeiras exatamente:

a) I, II

b) I, III

c) II, III

d) I, II, III

e) NDA

Ideia Original de: Gabriel Cruz Vitale Torkomian