2024-188

Pensando no modelo de grafos aleatórios de Erdos-Renyi, qual é o limiar da probabilidade da existência de arestas para a emergência de um componente gigante, onde $n$ é a quantidade de vértices do grafo aleatório?

1. $p=1/n$
2. $p=1/n^2$
3. $p=1/\sqrt{n}$
4. $p=2/n$
5. \N.D.A.

Ideia original de: G. Michel Carvalho

2024-187

Seguindo o modelo de grafos aleatórios de E. N. Gilbert para 4 vértices, qual seria a probabilidade de obter um grafo isomorfo ao grafo abaixo, sendo $p$ a probabilidade de existência de uma aresta?

1. $12p^4(1-p{)}^2$
2. $10p^2(1-p{)}^6$
3. $20p^6(1-p{)}^2$
4. $15p^2(1-p{)}^4$
5. N.D.A.

Ideia original de: Artur Silveira

2024-186

Sobre problemas extremais em grafos, assinale a alternativa que apresente a soma dos números das afirmativas corretas:

• 2 - Há uma trilha crescente de tamanho maior ou igual a $n-1$ em qualquer rotulação de $E(K_n)$ com inteiros distintos.
• 4 - Num grafo completo qualquer ordenação gera a mesma dilação.
• 8 - Todas as colorações de $K_9$ com as cores azul e vermelha vão ter pelo menos 1 clique de 3 azul ou 1 clique de 4 vermelha.

a) 2

b) 6

c) 12

d) 14

e) NDA

Ideia Original de: Josiane Gaia Pimenta

2024-185

Considere o grafo $G=(V,E)$ onde $V=\{A,B,C,D\}$ e $E=\{(A,B),(A,C),(B,C),(B,D),(C,D)\}$

Defina o matroide de ciclos $M(G)$ associado a $G$ onde os conjuntos independentes são os subconjuntos de $E$ que não contêm ciclos. Qual é a alternativa correta?

a) A cardinalidade do maior conjunto independente é 3, e $\{(A,B),(A,C),(B,D)\}$ é independente.

b) A cardinalidade do maior conjunto independente é 2, e $\{(A,B),(B,D)\}$ é independente.

c) A cardinalidade do maior conjunto independente é 3, e $\{(A,B),(A,C),(B,D)\}$ não é independente.

d) A cardinalidade do maior conjunto independente é 4, e $\{(A,B),(A,C),(B,D)\}$ não é independente.

e) N.D.A.

Ideia original de: Glaymar Albuquerque de França

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)=\mathrm{\Delta }(G)$.

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

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

e) N.D.A

Ideia original: Daniel Hosomi

2024-183

Sobre a teoria de Ramsey, qual das seguintes afirmações está INCORRETA?

a) $R(1,K)=1$, para qualquer inteiro positivo $K$

b) $R(2,K)=K$, para qualquer inteiro positivo $K$

c) $R(3,K)<6$, para qualquer inteiro positivo $K$

d) $R(S,K)=R(K,S)$, para quaisquer inteiros positivos $K$ e $S$

e) N.D.A.

Ideia original de: Artur Bernardes Mello da Silveira

2024-182

Considere as afirmações abaixo:

I-) O grafo complementar do grafo casa é perfeito.

II-) O grafo abaixo é cordal pois é triangulado:

III-) Todo grafo perfeito possui representação por intervalos.

IV-) O grafo abaixo possui 2 vértices simpliciais e 36 ordens de eliminação perfeita distintas:

Assinale a alternativa CORRETA:

a-) Somente IV está CORRETA

b-) Somente II está CORRETA

c-) Somente I está CORRETA

d-) Somente III está CORRETA

e-) N.D.A.

Ideia original de: Guilherme Terrell

2024-181

Sobre o algoritmo MCS (Maximum Cardinality Search) em um grafo $G$ qualquer, considere as afirmações:

1) O MCS visita os vértices de $G$ em uma ordem de eliminação simplicial.

2) O MCS deve ser inicializado em qualquer vértice $v$ tal que $d(v)=\mathrm{\Delta }(G)$.

4) O MCS é um algoritmo que custa $O(|V(G)|)$ e objetiva verificar se $G$ é cordal.

8) Se o MCS fornece uma eliminação simplicial, então $G$ é perfeito.

A soma das alternativas corretas é:

A) 6

B) 7

C) 12

D)14

E) NDA

Ideia Original De: Gabriel Cruz Vitale Torkomian

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 }^{\prime }(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-179

Sobre Grafos Hamiltonianos, considere as seguintes afirmações:

I) Grafos Hamiltonianos devem ter vértices com grau no mínimo 2.

II) Grafos Hamiltonianos não podem ter nenhum vértice de corte.

III) Em Grafos Hamiltonianos, a remoção de $k$ vértices provoca a existência de pelo menos $k$ componentes conexas. 

IV) Se$G$ é um grafo simples, conexo, com $n(G)\ge 3$ e possuindo dois vértices não adjacentes tais que a soma de seus graus é maior ou igual a $n(G)$, então $G$ é Hamiltoniano.

Assinale a alternativa correta:

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

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

c) Apenas as afirmações I, III estão corretas.

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

e) N.D.A.

 

Ideia original de: G. Michel Carvalho

2024-178

Considere as seguintes afirmativas

I-) Todo grafo $K_{m,n}$ possui ciclo Hamitoniano

II-) Todo grafo $C_n$ é Euleriano e Hamiltoniano

III-) O grafo abaixo não contém um ciclo Hamiltoniano

IV-) Seja $G$ o grafo casa. Podemos afirmar que o grafo abaixo é o grafo linha de $G$.

Assinale a alternativa correta:

a-) Apenas I e III são VERDADEIRAS

b-) Apenas I, II e III são VERDADEIRAS

c-) Apenas II , III e IV são VERDADEIRAS

d-) Apenas II e IV são VERDADEIRAS

e-) N.D.A.

 

Ideia original de: Guilherme Terrell

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

Considere a propriedade $P(k)$ a seguir: 

$P(k)$: Se um grafo $k$-partido $G$ com $k$-partição $X_1,X_2,\dots ,X_k$ contém um ciclo hamiltoniano, então $|X_1|=|X_2|=\dots =|X_k|$.

Então, o maior valor inteiro para o qual $P(k)$ é verdadeira é:

A) 1

B) 2

C) 3

D) 4

E) NDE

Ideia Original de: Gabriel Cruz Vitale Torkomian

2024-175

Sobre índices cromáticos, assinale a alternativa correta: 

1. ${\chi }^{\prime }(K_n)=n-1+(nmod2)$;
   ${\chi }^{\prime }(P_n)=\mathrm{\Delta }(P_n)=2$;
   ${\chi }^{\prime }(C_n)=2+(nmod2)$.
2. ${\chi }^{\prime }(K_n)=n-(nmod2)$;
   ${\chi }^{\prime }(P_n)=\mathrm{\Delta }(P_n)=n$;
   ${\chi }^{\prime }(C_n)=2+(nmod2)$.
3. ${\chi }^{\prime }(K_n)=n-1+(nmod2)$;
   ${\chi }^{\prime }(P_n)=\mathrm{\Delta }(P_n)=n$;
   ${\chi }^{\prime }(C_n)=3-(nmod2)$.
4. ${\chi }^{\prime }(K_n)=n-(nmod2)$;
   ${\chi }^{\prime }(P_n)=\mathrm{\Delta }(P_n)=2$;
   ${\chi }^{\prime }(C_n)=3-(nmod2)$.
5. N.D.A.

Ideia original de: G. Michel Carvalho