2024-184

Considerando colorações de grafos, assinale a alternativa correta:

a) Entre grafos planares, o maior número cromático é 3.

b) Se um grafo \(G\) é simples, conexo, sem ciclos ímpares e não completo, temos \( \chi(G) = \Delta(G) \).

c) Se um grafo \(G\) é simples, não possui ciclos pares e não é um clique, temos \( \chi(G) = \Delta(G) \).

d) Se um grafo \(G\) é simples, temos \( \chi(G) = \Delta(G) \).

e) N.D.A

Ideia original: Daniel Hosomi

2024-180

A Figura 1 representa o Grafo \(G\), contendo o trajeto que uma perueira escolar faz de sua casa (ponto \(A\)) até a escola (ponto \(B\)). Julgue as afirmações de I a IV e assinale a alternativa que contém a lista de todas as afirmações corretas.

I - Existe um único caminho hamiltoniano em G com vértice inicial A e vértice final B.

II - \( \chi'(G) = 4 \).

III - \( \chi(G) = 4 \).

Figura 1: Grafo G.

a) I

b) I e II

c) II e III

d) I, II e III

e) NDA

Ideia Original de: Josiane Gaia Pimenta

2024-177

Considere o grafo \(G\) com os seguintes vértices e arestas:
\[V(G)=\{A,B,C,D,E,F\}\]

\[E(G)=\{(A,B),(A,C),(A,D),(B,C),(B,D),(C,D),(C,E),(D,E),(D,F),(E,F)\}\]

Qual das alternativas a seguir é correta?

a) \(G\) é planar, possui número cromático 3, e contém um ciclo hamiltoniano: \(A\)-\(B\)-\(C\)-\(D\)-\(E\)-\(F\)-\(A\).

b) \(G\) não é planar, possui número cromático 4, e não contém um ciclo hamiltoniano.

c) \(G\) é planar, possui número cromático 3, e não contém um ciclo hamiltoniano.

d) \(G\) é planar, possui número cromático 4, e contém um ciclo hamiltoniano: \(A\)-\(D\)-\(C\)-\(E\)-\(F\)-\(B\)-\(A\).

e) N.D.A.

ideia original de: Glaymar A. França

2024-173

Considere o grafo \(G\) tal que:

\(V(G)=\{A,B,C,D\}\)

\(E(G)=\{(A,B),(A,C),(A,D),(B,C),(C,D)\}\)

Qual é o número cromático do grafo de linha \(L(G)\)?

a) 5

b) 4

c) 3

d) 2

e) N.D.A.

Ideia original de: Glaymar A. França 

2024-165

Sobre polinômios cromáticos, assinale a alternativa correta:

1. \( \chi(K_n, k) = k(k-1) \ldots (k - (n-1)) \);
   \( \chi(P_n, k) = k(k-1)^{n-1} \);
   \( \chi(C_n, k) = (k-1)^{n} + (-1)^n(k-1) \).
2. \( \chi(C_n, k) = k(k-1) \ldots (k - (n-1)) \);
   \( \chi(K_n, k) = k(k-1)^{n-1} \);
   \( \chi(P_n, k) = (k-1)^{n} + (-1)^n(k-1) \).
3. \( \chi(P_n, k) = k(k-1) \ldots (k - (n-1)) \);
   \( \chi(K_n, k) = k(k-1)^{n-1} \);
   \( \chi(C_n, k) = (k-1)^{n} + (-1)^n(k-1) \).
4. \( \chi(P_n, k) = k(k-1) \ldots (k - (n-1)) \);
   \( \chi(C_n, k) = k(k-1)^{n-1} \);
   \( \chi(K_n, k) = (k-1)^{n} + (-1)^n(k-1) \).
5. N.D.A.

Ideia original de: G. Michel Carvalho

2024-161

Dado o grafo abaixo e considerando \(k\) cores, qual das alternativas a seguir exibe uma ordem de eliminação perfeita, anotada com o número de cores livres disponível para cada vértice, no algoritmo guloso para uma coloração própria?

A) 1: \(k\), 2: \(k-1\), 3: \(k-2\), 4: \(k-1\), 5: \(k-2\)

B) 1: \(k\), 2: \(k-1\), 3: \(k-1\), 5: \(k-2\), 4: \(k-3\)

C) 1: \(k\), 2: \(k-1\), 3: \(k-1\), 4: \(k-1\), 5: \(k-3\)

D) 1: \(k\), 2: \(k-1\), 3: \(k-2\), 5: \(k-3\), 4: \(k-4\)

E) N.D.A.

Ideia original de: Artur Silveira 

2024-160

Qual é o polinômio cromático do grafo \( C_5 \):

a) \( k(k - 1)(k - 2)(k -3) \)

b) \( k(k - 1)(k - 2)(k -3)(k - 4) \)

c) \( k(k - 1)^4 \)

d) \( k^5 \)

e) N.D.A.

Ideia original de: Wellington T. A. da Silva

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