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

2024-129

Seja \(G\) um grafo conexo. Sabendo que cada aresta de \(G\) é uma aresta de corte, assinale a afirmativa não necessariamente correta sobre \(G\).

a) \(G\) é bipartido

b) Todo vértice \(v\) de grau \(d(v)  > 1\) em \(G\) é um vértice de corte

c) \(G\) é euleriano.

d) Sejam \(u\) e \(v\) dois vértices não adjacentes em \(G\) e \(C\) a quantidade de ciclos em \(G\). Ao inserir a aresta \(uv\) em \(G\), o grafo passará a ter \(C + 1\) ciclos.

e) N.D.A.

Ideia original de: Luiz Guistavo Aguiar

2024-128

Qual alternativa apresenta todas as afirmativas corretas?

I - Um grafo simples possui loops e arestas múltiplas.

II - A remoção de uma aresta de corte aumenta o número de componentes conexos.

III - Um passeio em um grafo pode repetir vértices e arestas; uma trilha pode repetir somente vértices.

a) I e II

b) II e III

c) I e III

d) Somente I

e) NDA

Ideia original de: Josiane Gaia Pimenta

2024-127

Considere o seguinte grafo simples \( G \):

\[ V(G) = \{a, b, c, d, e, f, g\} \]

\[ E(G) = \{ab, ac, ad, bc, be, cd, cf, dg, ef, fg\} \]

Se o grafo \( G \) representa um mapa de cidades onde vértices adjacentes compartilham uma fronteira, determine o número mínimo de cores \( \chi(G) \) que podem ser utilizadas para colorir \( V(G) \),  garantindo que vértices adjacentes tenham cores distintas.

a) \( \chi(G) = 6\)

b) \( \chi(G) = 5\)

c) \( \chi(G) = 4\)

d) \( \chi(G) = 3\)

e) NDA

Ideia original de: Glaymar A. França 

2024-126

É possível decompor K4 de qual das seguintes formas?

a) C3 + P3 + P2

b) C3 + P3 + P3

c) P3 + P3 + P4

d) P3 + P4 + P4

e) N. D. A. 

Ideia original de: Artur Silveira

2012-001

Enunciado: Dado um grafo bipartido G com matriz de adjacência A, qual o valor na linha i e coluna i da k-ésima potência ímpar de A?

a) i

b) 0

c) i^k

d) k

e) NDA