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