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
sexta-feira, 18 de maio de 2012
MO405 - Questão para a prova oral
Número:
Enunciado: Considerando as informações I a IV, qual das alternativas é correta?
I qualquer subgrafo de um grafo planar é planar.
II qualquer subgrafo de um grafo não-planar é não-planar.
III qualquer grafo que contém um subgrafo planar também é planar.
IV qualquer grafo que contém um subgrafo não-planar também é não-planar.
a) I e III são verdadeiras.
b) II e IV são verdadeiras.
c) II e III são falsas.
d) I e IV são falsas.
e) nda
Ideia original de: Heber A. Scachetti
sexta-feira, 11 de maio de 2012
MO405 - Questão para prova oral
Número:
Enunciado: A respeito de grafos cordais, qual das alternativas a seguir é correta?
a) Todo grafo completo é cordal.
b) Todo grafo planar é cordal.
c) Todo grafo bipartido completo é cordal.
d) O grafo de Petersen é cordal.
e) nda
Ideia original de: Heber A. Scachetti
sexta-feira, 4 de maio de 2012
MO405 - Questão para prova oral (11° semana)
Número:
Enunciado: Considerando grafos simples com 8 vertices e número cromático 4, qual das alternativas a seguir é correta?
a) O grafo contendo estas características possui no máximo 24 arestas.
b) O grafo contendo estas características possui no máximo 48 arestas.
c) O grafo contendo estas características possui no máximo 32 arestas.
d) O grafo contendo estas características possui no máximo 16 arestas.
e) nda
Ideia original de: Heber A. Scachetti
sexta-feira, 27 de abril de 2012
MO405 - Questão para prova oral (9° semana)
Número:
Enunciado: Considerando o resultado do produto cartesiano entre o grafo de Petersen (figura a seguir) e o K3, qual das alternativas a seguir é correta?
a) O número de vértices é 23.
b) O número de arestas é 18.
c) O número cromático é 2.
d) O número cromático é 3.
e) nda
Ideia original de: Heber A. Scachetti
sexta-feira, 13 de abril de 2012
MO 405 - Questão para prova oral (7° semana)
Número:
Enunciado: A respeito de conectividade em grafos é correto dizer:
a) A conectividade de vertice de um grafo Km,n é max(m,n).
b) Em todo grafo simples, a conectividade de vertices é sempre maior ou igual a conectividade de aresta.
c) Em um grafo completo de m vertices, a conectividade de aresta é m - 1.
d) A conectividade de vertice de um grafo completo de n vertices é n.
e) nda
Ideia original de: Heber A. Scachetti
quinta-feira, 5 de abril de 2012
MO 405 - Questão para prova oral (6° semana)
Número:
Enunciado: Dado o grafo a seguir, qual é o tamanho do emparelhamento máximo:
a) 6.
b) 8.
c) 7.
d) 10.
e) nda
Ideia original de: Heber A. Scachetti
sexta-feira, 30 de março de 2012
MO 405 - Questão para prova oral (5° semana)
Número:
Enunciado: Considerando um grafo bipartido é incorreto dizer:
a) O índice de estabilidade (independence number) nem sempre é igual ao tamanho de uma das partições.
b) O máximo tamanho de emparelhamento sempre é igual ao mínimo tamanho de cobertura de vértice.
c) O máximo tamanho de conjunto independente sempre é igual ao mínimo tamanho de cobertura de aresta.
d) Seja k > 0. Todo grafo bipartido k-regular possui um emparelhamento perfeito.
e) nda
Ideia original de: Heber A. Scachetti
sexta-feira, 23 de março de 2012
MO 405 - Questão para prova oral (4° semana)
Número:
Enunciado: Dado um conjunto de vértices de tamanho 10, o número de árvores que pode ser formado com este conjunto é:
a) 108
b) 810
c) 1010
d) 1012
e) nda
Ideia original de: Heber A. Scachetti
sexta-feira, 16 de março de 2012
MO 405 - Questão para prova oral (3° semana)
Número:
Enunciado: A respeito de digrafos, qual das opções a seguir é incorreta?
a) A somatória dos graus de entrada dos vértices é igual a somatória dos graus de saída.
b) Todo digrafo fortemente conexo é euleriano.
c) Todo digrafo com o valor 1 para o grau de saida mínimo possui um ciclo.
d) Todo digrafo com n > 1 vertices contendo um ciclo de tamanho n é euleriano.
e) nda
Ideia original de: Heber A. Scachetti
MO 405 - Questão para prova oral (3° semana)
Número:
Enunciado: Qual das opções a seguir não é característica de uma árvore com n vertices (n > 1)?
a) G é conectado e não possui ciclos.
b) G é conectado e possui n - 1 arestas.
c) G possui n - 1 arestas e não possui ciclos.
d) Para u, v E V(G), G possui caminhos u, v.
e) nda
Ideia original de: Heber A. Scachetti
quinta-feira, 1 de março de 2012
Ch. 1: What is a graph?
Número:
Enunciado: Qual das alternativas a seguir está incorreta? Considere apenas grafos simples.
a) Todo grafo completo possui um clique.
b) O complemento de um grafo completo é um grafo sem arestas.
c) A cintura de um grafo triangulo é igual a cintura de um grafo casa.
d) O grau de cada vertice em um grafo completo é igual ao número de vertices menos 1.
e) NDA
Ideia original de: Heber A. Scachetti
Assinar:
Postagens (Atom)