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. \( 12 p^4(1-p)^2 \)
2. \( 10 p^2(1-p)^6 \)
3. \( 20 p^6(1-p)^2 \)
4. \( 15 p^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) = \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-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