2024-159

 Considere as seguintes afirmativas:

I) Seja \(G\) um grafo conexo com \(n\) vértices, \(m\) arestas e número cromático 4. Podemos afirmar que \( m \geq 6 \).

II) O grafo abaixo não contém uma subdivisão de \( K_4 \):

III) Se \(G\) é 3-crítico, podemos afirmar que \(G\) é um ciclo ímpar e que todo subgrafo próprio \( H \subseteq G \) é bipartido.

IV) Seja \(G\) um grafo conexo de número cromático \( k \geq 2 \) e que pode ser separado em \(b\) blocos, sendo um desses blocos um grafo caminho. Podemos afirmar que \(G\) é \(k\)-crítico.

Assinale a alternativa CORRETA:

a-) Apenas as afirmativas III e IV estão CORRETAS

b-) Apenas as afirmativas II e IV estão CORRETAS

c-) Apenas as afirmativas I, II e IV estão CORRETAS

d-) Apenas as afirmativas I e III estão CORRETAS

e-) N.D.A.

 

Ideia original de: Gabriel S. Kraszczuk

 

2024-158

Considere uma rede social com 10000 usuários onde a relação de "seguir" é simétrica, o limite de seguidores é 1000 por usuário e, dadas quaisquer 26 pessoas, existem pelo menos duas que se seguem. A rede deseja fazer um sorteio com as seguintes condições: 

(1) Cada usuário da rede recebe um número de 1 a \(n\).

(2) Quaisquer dois usuários que se seguem não recebem o mesmo número.

Então, o intervalo que contém exatamente os valores de \(n\) para os quais (1) e (2) podem ser satisfeitas é:

A) 200 a 1000.

B) 200 a 501.

C) 401 a 1000.

D) 401 a 501.

E) NDA.

Ideia Original de: Gabriel Cruz Vitale Torkomian.

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-156

Assinale a proposição correta para grafos de intervalos \( G \): 

a) \( \chi(G) = \alpha(G) \) 

b) \( \chi(G) = \omega(G) \)

c) \( \chi(G) = \Delta(G) \)

d) \( \chi(G) = \delta(G) \) 

e) NDA 

Ideia original de: Josiane Gaia Pimenta

2024-155

Considere as seguintes afirmações:

I-) O grafo intervalo abaixo representa um grafo \(K_4\).

II-) Um grafo \(G\) de ordem \(n(G) \geq 3\) possui uma representação por intervalos se e somente se \( \omega(G) \geq 3 \).

III-) Se \(G\) é o grafo de Petersen, então \( \chi(G) = 3 \), \( \omega(G) = 2 \) e \( \alpha(G) = 4 \).

IV-) Seja \(G\) um grafo conexo com \(m\) blocos. Denotando por \( \chi_i \) o número cromático de cada bloco de \(G\), para \( 1 \leq i \leq m \), podemos afirmar que \( \chi(G) = \min_{1 \leq i \leq m}(\chi_i) \).

V-) Seja \( G = H U F \). Podemos afirmar que \( \chi(G) = \max(\chi(H), \chi(F)) \).

Assinale a alternativa CORRETA:

a-) Apenas as afirmativas I, III e V estão CORRETAS

b-) Apenas as afirmativas II e IV estão CORRETAS

c-) Apenas as alternativas I e III estão CORRETAS

d-) Apenas as afirmativas I, II e V estão CORRETAS

e-) N.D.A.

Ideia original de: Guilherme Terrell

2024-154

 Considere os seguintes intervalos, o grafo de intervalos \(G\) resultante (nota: \(e\) e \(f\) são adjacentes):

Quais das seguintes afirmações:

I - O número cromático de \(G\) é 3.

II - Considerando o Algoritimo de Coloração Gulosa, as ordens (a,b,c,d,e,f,g,h) e (h,g,f,e,d,c,b,a) resultam em colorações que usam o mesmo número de cores.

III - O grafo \(G\) não possui ciclos.

estão corretas?

a) I, II e III;

b) I e II;

c) II e III;

d) I e III;

e) NDA;

Ideia original de: Gabriel S. Kraszczuk

2024-153

Questão 9 - Dado os contextos de fluxos máximos e grafos k-coloráveis, assinale a alternativa correta:

a) O problema de min-edge-cover pode ser resolvido com algoritmos de fluxo máximo em tempo polinomial para grafos bipartidos.

b) Todo grafo k-colorável dá origem a um grafo (k-1)-colorável se qualquer vértice for retirado.

c) Se um grafo é bipartido então o maior grau do grafo é menor que o número cromático do grafo.

d) O problema de min-vertex-cover é mais difícil do que o problema de max-independent-set para grafos quaisquer.

e) N.D.A

Ideia original: Daniel Hosomi