MO405 - Questão para a prova oral

Número:

Enunciado: Qual dos grafos a seguir, descritos utilizando a representação por interseção, possui uma 4-coloração total ?

A. {1}, {1,2}, {1,3}, {2,4}, {3,4}.
B. {1}, {1,2}, {1,2}, {2,3}, {3}.
C. {1,2}, {1,3,5}, {2,4,6}, {3,4}, {5,6}.
D. Todas as alternativas anteriores.
E. NDA.

Ideia original de: Lucas

MO405 - Questão para a prova oral

Número:

Enunciado: Dado um grafo simples G, podemos afirmar que temos um matróide se os conjuntos independentes são todos os subconjuntos de E(G) que:

A. Possuem ao menos um ciclo.
B. São caminhos.
C. Formam um subgrafo de G com grau máximo menor ou igual a 2.
D. São cliques.
E. NDA.

Ideia original de: Lucas

MO405 - Questão para a prova oral

Número:

Enunciado: Seja G um grafo simples com n vértices númerados de 1 a n (v₁, ... , v_n). A multiplicação de vértices de um grafo G por um vetor de inteiros não-negativos h = (h₁, ... , h_n) consiste em um grafo H contendo h_i cópias do vértice v_i de G. Além disso, dois vértices u_i e u_j em H, cópias dos vértices v_i e v_j em G, respectivamente, são adjacentes se, e somente se, os vértices v_i e v_j são adjacentes. Se H é o grafo obtido do resultado da multiplicação de vértices de G por h, e d(v_i) é o grau do vértice v_i em G, podemos afirmar que:

A. χ(H) > χ(G).
B. ω(H) > ω(G).
C. α(H) > α(G).
D. e(H) = ( d(v₁)h₁ + ... + d(v_n)h_n ) / 2.
E. NDA.

Ideia original de: Lucas

MO405 - Questão para a prova oral

Número:

Enunciado: Pode-se afirmar que o grafo abaixo:

A. É hamiltoniano.
B. É um Snark.
C. É 2-aresta-colorível.
D. Não possui um cycle double cover (CDC).
E. NDA.

Ideia original de: Lucas