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 }^{\prime }(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^{\prime }$ abaixo:

e as afirmações:

I - Os grafos $H$ e $H^{\prime }$ são planares;

II - O grafo $H^{\prime }$ é 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\ge 0$ e para todos os grafos $G$ , se $g\le h$ então ${\nu }_g(G)\le {\nu }_h(G)$,

(2) ${\nu }_1(K_{3,3})=0$,

(4) Para todo $n\ge 1$ e todo $g\ge 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)\dots (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)\dots (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)\dots (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)\dots (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^{\ast }$ 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)\le 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\ge 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\ge 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)=\mathrm{\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)\ge 3$ possui uma representação por intervalos se e somente se $\omega (G)\ge 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\le i\le m$, podemos afirmar que $\chi (G)=\underset{1\le i\le m}{min}({\chi }_i)$.

V-) Seja $G=HUF$. 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