MO405 - Questão para a prova oral

Número:

Enunciado:
Seja G um grafo aleatório de 4 vértices. Sabendo que a probabilidade de G ser um grafo completo é igual a 0,000064. Qual é a probabilidade do grafo G ser um ciclo?

A. 0,000256
B. 0,001024
C. 0,004096
D. 0,016384
E. NDA

Ideia original de: Zhenlei Ji

MO405 - Questão para a prova oral

Número:

Enunciado:
Sobre as afirmações a seguir:

I- Os conjuntos independentes de um grafo são os conjuntos independentes de um matróide.
II- Todo matróide particionado é um matróide transversal
III- O valor R(3,3), número de Ramsey, é 6
IV- Seja T uma árvore geradora do grafo cubo Q7, então existe uma aresta de Q7 diferente das arestas de T cuja adição em T cria um ciclo de tamanho pelo menos 12

Quais são as  INCORRETAS?

A. Somente a I
B. I e II
C. II e IV
D. I e IV
E. NDA

Ideia original de: Zhenlei Ji

MO405 - Questão para a prova oral

Número:

Enunciado:
Seja G o grafo abaixo.

Considerando o grafo G como entrada do programa MCS (Maximum Cardinality Search). Qual é a ordem dos vértices retornado pelo programa?

A. 271643589
B. 271634859
C. 271648359
D. 271643859
E. NDA

Ideia original de: Zhenlei Ji

MO405 - Questão para a prova oral

Número:

Enunciado:
A seguir o grafo G:

Analise as afirmações abaixo e assinale a alternativa correta:
I - O grafo G é hamiltoniano;
II - χ(G)=3;
III - χ'(G)=3;
IV- O grafo dual de G possui 10 faces

A. Somente II e III
B. Somente IV
C. II, III, IV
D. I, II e III
E. NDA

Ideia original de: Zhenlei Ji

MO405 - Questão para a prova oral

Número:

Enunciado:
Seja G um grafo simples. Qual dos grafos a seguir pertence a Classe 1? Sabendo que a Classe 1 é representada por χ(G) = Δ(G).

A. Grafo Completo K7
B. Petersen
C. Grafo Completo K5
D. Grafo k-regular
E. NDA

Ideia original de: Zhenlei Ji

MO405 - Questão para a prova oral

Número:

Enunciado:
Sabendo que a "espessura" de um grafo G é o número mínimo de grafos planares em uma decomposição de G em grafos planares. E o "número de cruzamentos" de um grafo G é o número mínimo de cruzamentos em um desenho de G no plano. O valor da espessura e o número de cruzamentos do grafo de Peterson são respectivamentes:

A. 1 e 1
B. 1 e 2
C. 2 e 1
D. 2 e 2
E. NDA

Ideia original de: Zhenlei Ji

MO405 - Questão para a prova oral

Número:

Enunciado:
Um grafo planar G com duas faces de tamanho 3 e três faces de tamanho 4. Sabendo que G é um grafo simples e regular, i.e. que todos os seus vértices têm o mesmo grau, determine o número V de vértices e o grau d comum a todos o vértices de G.

A. V = 6 e d = 4
B. V = 4 e d = 6
C. V = 6 e d = 3
D. V = 8 e d = 3
E. NDA

Ideia original de: Zhenlei Ji