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?
Ideia original de: G. Michel Carvalho
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?
Ideia original de: Artur Silveira
Sobre problemas extremais em grafos, assinale a alternativa que apresente a soma dos números das afirmativas corretas:
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
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
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
Considere as afirmações abaixo:
I-) O grafo complementar do grafo casa é perfeito.
II-) O grafo abaixo é cordal pois é triangulado:
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) = \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
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'(G) = 4 \).
III - \( \chi(G) = 4 \).
.png) |
| 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
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) \geq 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
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
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
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)\}\]
Considere a propriedade \(P(k)\) a seguir:
\(P(k)\): Se um grafo \(k\)-partido \(G\) com \(k\)-partição \( X_1, X_2, \ldots, X_k \) contém um ciclo hamiltoniano, então \(|X_1| = |X_2| = \ldots = |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
Sobre índices cromáticos, assinale a alternativa correta:
Ideia original de: G. Michel Carvalho
