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