2024-174

Um grande piloto de uma famosa categoria do automobilismo precisa percorrer um grafo passando por todos os "pit stops" (vértices) exatamente 1 única vez cada um, e dessa forma completar um ciclo que leva seu nome (ciclo Hamiltoniano). Dado que o grafo é o da figura abaixo, de quantas maneiras distintas esse grande piloto pode realizar essa tarefa?

a-) Mais do que 3

b-) 2

c-) 1

d-) 0

e-) N.D.A.

Ideia original de: Guilherme A. Terrell

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

 Considere o grafo abaixo:

Quais das afirmações abaixo estão corretas?

I - O grafo acima é planar;

II - O grafo acima possui um ciclo hamiltoniano;

III - o grafo acima é euleriano;

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

Considere as seguintes afirmações a respeito do grafo linha \(L(G)\) de um grafo \(G\) qualquer:

1) Se \(G\) é conexo, então \(L(G)\) é conexo.

2) Se \(L(G)\) é conexo, então \(G\) é conexo.

4) \(\chi'(G)=\chi(L(G))\)

8) \(K_n\) é isomorfo a \(L(K_n)\) se, e somente se, \(n=3\).

A soma das alternativas corretas é:

A) 15

B) 13

C) 10

D) 7

E) NDA

Ideia Original de: Gabriel Cruz Vitale Torkomian

2024-170

Dado o contexto de grafos-linha, assinale a alternativa incorreta:

a) O grafo \( L(G) \) possui um ponto de articulação se e somente se \( G \) tem uma ponte.

b) O índice cromático de um grafo \( G \) é igual ao número cromático de \( L(G) \).

c) O grafo linha de um grafo conexo é um grafo conexo.

d) O grafo linha de uma árvore é uma árvore.

e) N.D.A.

Ideia original: Daniel Hosomi

2024-169

 Considere as afirmações abaixo a respeito do grafo de Petersen e assinale a alternativa correta: 

I) O grafo de Petersen não é planar. 

II) O grafo de Petersen possui crossing number = 2 (lembrando que o crossing number é o menor número de cruzamentos de arestas que se pode obter ao desenhar o grafo em um plano).

III) O grafo de Petersen possui um \( K_5 \) como menor.

IV) O grafo de Petersen menos um vértice é uma subdivisão do \( K_{3,3} \).

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

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

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

d) Todas as afirmações estão corretas.

e) N.D.A.

Ideia original de: G. Michel Carvalho

2024-168

 Considere as seguintes afirmações:

I-) Seja G* (figura baixo) o grafo dual de um grafo conexo G. Podemos afirmar que G é o grafo casa.

II-) Existe um grafo planar com 8 vértices, 10 arestas e 3 faces.

III-) Seja G um grafo planar com sequência de graus S = {2, 3, 3, 5, 5}. Podemos afirmar que G tem 6 faces.

IV-) Dados os grafos G1, G2 e G3 abaixo, podemos afirmar que apenas G1 é cordal.

Assinale a alternativa CORRETA:

a-) Apenas as afirmativas I e III são VERDADEIRAS

b-) Apenas as afirmativas II e IV são VERDADEIRAS

c-) Apenas as afirmativas III e IV são VERDADEIRAS

d-) Apenas as afirmativas I, III e IV são VERDADEIRAS

e-) N.D.A.

Ideia original de: Guilherme A. Terrell

2024-167

Considere os grafos \( H \) e \( H' \) abaixo:

e as afirmações:

I - Os grafos \(H\) e \( H' \) são planares;

II - O grafo \( H' \) é um grafo triangulado;

III - O grafo \( H \) é um grafo triangulado;

Quais das afirmações acima estão corretas?

a) apenas I;

b) apenas I e II;

c) apenas I e III;

d) apenas II e III;

e) NDA;

Ideia original de: Gabriel S. Kraszczuk 

2024-166

Definimos a função \( \nu_g(G) \) como sendo o menor número de cruzamentos de uma imersão de \( G \) em uma superfície de gênus \( g \).  Atribuindo valores 1, 2, 4 e 8 às seguintes afirmações:

(1) Para todo os inteiros \( g, h \geq 0 \) e para todos os grafos \( G \) , se \( g \leq h \) então \( \nu_g(G) \leq \nu_h(G) \),

(2) \( \nu_{1}(K_{3,3}) = 0 \),

(4) Para todo \( n \geq 1 \) e todo \( g \geq 0 \), temos que  \( \nu_{g}(K_{2,n}) = 0 \),

(8) \( \nu_{0}(K_5) = 1 \),

a soma das afirmações corretas é:

A) 3

B) 10

C) 12

D) 15

E) NDA

Ideia Original de: Gabriel Cruz Vitale Torkomian

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

Considere um grafo \(G\) com 8 vértices e 12 arestas. O que podemos afirmar com certeza sobre \(G\)?

a) O grafo \(G\) é necessariamente um grafo planar.

b) O grafo \(G\) possui um ciclo hamiltoniano.

c) O grafo \(G\) é bipartido.

d) O grafo \(G\) contém um subgrafo isomórfico ao \( K_5 \)​.

e) N.D.A.

Ideia original de: Glaymar A. França 

2024-163

Considere o grafo abaixo:

Quais das afirmações a seguir não estão corretas?

I - O grafo acima é planar (pode ser desenhado no plano sem o cruzamento de arestas)

II - O número de faces do grafo acima, (em sua representação no plano sem cruzamento de arestas) é 6.

III - O número cromatíco do grafo acima é 3.

IV -  O número cromático do grafo acima é 4.

a) I e II;

b) apenas a II;

c) III e IV;

d) apenas a IV;

e) NDA;

Ideia original de: Gabriel S. Kraszczuk

2024-162

Considere as afirmações abaixo:

1) O grafo representado abaixo não é planar.

2) Considerando que um grafo plano \(G\) é legalzão se 1) \(G\) é ismorfo ao seu dual \(G^*\) e 2) é conexo. Então, todo grafo legalzão tem um número par de arestas.

4) O maior \(k\) natural que satisfaz a seguinte propriedade: "todo grafo simples com \(n(G) \leq k\) é planar" é um número quadrado perfeito.

8) Considere um grafo planar \(G\) com \( n(G)=10 \), \( e(G)=12 \). Então \(G\) tem exatamente 4 faces.

A soma das alternativas verdadeiras é:

A) 2

B) 6

C) 14

D)15

E) NDA

Ideia Original de: Gabriel Cruz Vitale Torkomian.

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