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

2024-132

Considere um jogo com as seguintes regras:

• Cada partida é entre 2 jogadores.
• A cada rodada o jogador da vez deve falar o número para ser o da mesa
• Suponha que n seja o número atual da mesa, o jogador da vez deve escolher ou n + 1 ou n + 2 para ser o próximo número da mesa.
• O valor inicial da mesa é 0.
• O jogador que falar 21 vence a partida.

Dada a descrição do jogo, considere as seguintes afirmações, assumindo que os jogadores sempre jogam de maneira ótima.

I - O jogo não possui uma estratégia ótima.

II - O segundo jogador sempre vence.

III - Numa variação onde vence quem fala o número 31, o primeiro jogador pode sempre ganhar desde que seu primeiro lance seja n = 1.

IV - Numa variação onde vence quem fala o número 31, o primeiro jogador pode sempre ganhar desde que seu primeiro lance seja n = 2.

Assinale a alternativa que contém apenas afirmações corretas.

a) II e IV

b) II e III

c) I e IV

d) I e III

e) N.D.A

Ideia original de: Luiz Gustavo Aguiar

2024-131

O grafo a seguir é uma representação das sete pontes de Königsberg. Euler demonstrou em 1736 que fazer uma trilha que passe por todas as arestas sem repetir nenhuma era impossível. Selecione a opção que representa um conjunto de arestas tal que, ao serem retiradas, o  grafo restante ainda não tenha tal trilha.

 

A) {(A,B), (B,A)}

B) {(B,D)}

C) {(A,D), (C,D)}

D) {(A,B), (B,A), (A,D)}

E) NDA

Ideia original de Gustavo Henrique Sencio de Souza.

2024-130

Considere as seguintes afirmações:

I) Um torneio é uma orientação em uma árvore completa binária começando pelas folhas e indo em direção à raiz.

II) A matriz de adjacências de um grafo direcionado é necessariamente assimétrica.

III) Considere um grafo estrela e uma orientação \( D \) nele. O máximo grau de entrada de um vértice em \( D \) é igual a \( n-1 \), sendo \( n \) o número de vértices do grafo.

IV)  Um torneio é sempre fortemente conectado.

Assinale a alternativa correta:

a) As afirmações II e III são corretas.

b) Apenas a afirmação IV é correta.

c) I, II e IV são corretas

d) Apenas a afirmação III é correta

e) N.D.A

Ideia original de: Guilherme Michel Carvalho