Número:
Enunciado:
Considerando list coloring, qual das alternativas é correta?
a) O "chromatic number" é sempre menor que o "list chromatic number".
b) Computar o "list chromatic number" é tão difícil quanto computar "chromatic number".
c) O valor do maior grau de um grafo qualquer é sempre menor que o "list chromatic number".
d) O "list chromatic number" de um grafo planar é sempre maior que o valor do maior grau + 1.
e) nda
sexta-feira, 22 de junho de 2012
sexta-feira, 15 de junho de 2012
MO405 - Questão para a prova oral
Número:
Enunciado: Considerando grafos simples, qual das alternativas é correta?
a) Toda árvore com no mínimo três vértices tem no mínimo 3 folhas.
b) Se um grafo é 2-conexo então o grafo obtido da subdivisão de todas as suas arestas também é 2-conexo.
c) O número cromatico de um grafo qualquer é sempre menor ou igual ao seu número de clique.
d) Todo grafo planar simples possui um vértice com grau máximo 3.
e) nda
Enunciado: Considerando grafos simples, qual das alternativas é correta?
a) Toda árvore com no mínimo três vértices tem no mínimo 3 folhas.
b) Se um grafo é 2-conexo então o grafo obtido da subdivisão de todas as suas arestas também é 2-conexo.
c) O número cromatico de um grafo qualquer é sempre menor ou igual ao seu número de clique.
d) Todo grafo planar simples possui um vértice com grau máximo 3.
e) nda
Ideia original de: Heber A. Scachetti
sexta-feira, 8 de junho de 2012
MO405 - Questão para a prova oral
Número:
Enunciado: Considerando o grafo (parcialmente colorido) da figura a seguir, o vertice v a ser colorido e cadeias de Kempe (as quais fizeram o colega Heber levar um negativo), qual das alternativas é correta?
a) A cadeia formada pelo caminho 6-2-1 com as cores amarela e azul permite que v seja colorido com a cor azul alterando apenas a cor dos vértices da cadeia.
b) A cadeia formada pelo caminho 6-2-3-1 com as cores amarela e azul permite que v seja colorido com a cor azul alterando apenas a cor dos vértices da cadeia.
c) A cadeia formada pelo caminho 5-3-1 com as cores amarela e azul permite que v seja colorido com a cor amarela vermelha alterando apenas a cor dos vértices da cadeia.
d) A formação apenas de cadeias de kempe neste grafo não é suficiente para 4 colorir seus vértices.
e) nda
Ideia original de: Heber A. Scachetti
sexta-feira, 1 de junho de 2012
MO405 - Questão para a prova oral
Número:
Enunciado: Considerando as afirmações de I a III, qual das alternativas é correta?
I todo grafo cúbico planar 2-aresta-conexo é hamiltoniano.
II Todo grafo que possui uma coloração de Tait pode ser 4-aresta-colorido.
III Um snark não possui coloração de Tait.
a) Todas são verdadeiras.
b) Todas são falsas.
c) I e III são falsas.
d) III é verdadeira.
e) nda
Ideia original de: Heber A. Scachetti
Assinar:
Postagens (Atom)