Número:
Enunciado: Para a criação de uma imersão de um cubo achatado, utiliza-se a numeração por profundidade de uma árvore geradora feita à partir de uma busca em largura. Seja G o grafo abaixo e T a árvore geradora representada pelas arestas em destaque. Seja a discrepância dada por c(i, j) = dT(i, j) - dG(i, j), com dT(i, j) e dG(i, j) a distância entre os vértices i e j em T e G, respectivamente. Assinale a alternativa correta.
a) c(6, 2) = 2 e c(3, 0) = 0
b) c(2, 3) = 0 e c(3, 6) = 2
c) c(1, 4) = 0 e c(5, 1) = 0
d) c(0, 6) = 1 e c(4, 3) = 0
e) NDA
Ideia original de: Rafael de Oliveira Werneck
sexta-feira, 22 de junho de 2012
sexta-feira, 15 de junho de 2012
MO405 - Questão para a prova oral
Número:
Enunciado: Sejam três grafos tais que G é um grafo gravata borboleta (bow-tie), H é um grafo casa (house) e I é um grafo pata (paw). Assinale a alternativa correta em relação à largura de banda dos grafos acima.
a) B(G) = 2; B(H) = 2; B(I) = 2
b) B(G) = 3; B(H) = 3; B(I) = 3
c) B(G) = 2; B(H) = 2; B(I) = 3
d) B(G) = 4; B(H) = 3; B(I) = 2
e) NDA
Ideia original de: Rafael de Oliveira Werneck
Enunciado: Sejam três grafos tais que G é um grafo gravata borboleta (bow-tie), H é um grafo casa (house) e I é um grafo pata (paw). Assinale a alternativa correta em relação à largura de banda dos grafos acima.
a) B(G) = 2; B(H) = 2; B(I) = 2
b) B(G) = 3; B(H) = 3; B(I) = 3
c) B(G) = 2; B(H) = 2; B(I) = 3
d) B(G) = 4; B(H) = 3; B(I) = 2
e) NDA
Ideia original de: Rafael de Oliveira Werneck
sexta-feira, 8 de junho de 2012
MO405 - Questão para a prova oral
Número:
Enunciado: Dado o grafo a seguir, assinale a alternativa que corresponde à ordenação de eliminação simplicial dada pelo algoritmo MCS (Maximum Cardinality Search), considerando que os vértices são escolhidos em ordem alfabética.
a) d, e, g, f, c, b, a
b) c, d, g, e, f, b, a
c) d, e, g, c, f, b, a
d) d, c, g, e, f, b, a
e) NDA
Ideia original de: Rafael de Oliveira Werneck
Enunciado: Dado o grafo a seguir, assinale a alternativa que corresponde à ordenação de eliminação simplicial dada pelo algoritmo MCS (Maximum Cardinality Search), considerando que os vértices são escolhidos em ordem alfabética.
a) d, e, g, f, c, b, a
b) c, d, g, e, f, b, a
c) d, e, g, c, f, b, a
d) d, c, g, e, f, b, a
e) NDA
Ideia original de: Rafael de Oliveira Werneck
quinta-feira, 24 de maio de 2012
MO405 - Questão para a prova oral
Número:
Enunciado: Qual é o número cromático de arestas do produto cartesiano dos grafos Cn e Cm, χ'(Cn □ Cm), com n, m ≥ 3.
a) min{n, m}
b) n*m
c) 4
d) n + m
e) NDA
Ideia original de: Rafael de Oliveira Werneck
Enunciado: Qual é o número cromático de arestas do produto cartesiano dos grafos Cn e Cm, χ'(Cn □ Cm), com n, m ≥ 3.
a) min{n, m}
b) n*m
c) 4
d) n + m
e) NDA
Ideia original de: Rafael de Oliveira Werneck
sexta-feira, 18 de maio de 2012
MO405 - Questão para a prova oral
Número:
Enunciado: Seja G um grafo com número de vértice n, número de arestas e e cintura g. Assinale a expressão que corresponde à fórmula do número máximo de arestas para que o grafo G seja planar.
a) (g - 1)(n - 2) / (g - 2) ≥ e
b) g(n - g) / 2(g - 2) ≥ e
c) g(n - 2) / (g - 2) ≥ e
d) (2g + 1)(n - 2) / (g - 2) ≥ e
e) NDA
Ideia original de: Rafael de Oliveira Werneck
Enunciado: Seja G um grafo com número de vértice n, número de arestas e e cintura g. Assinale a expressão que corresponde à fórmula do número máximo de arestas para que o grafo G seja planar.
a) (g - 1)(n - 2) / (g - 2) ≥ e
b) g(n - g) / 2(g - 2) ≥ e
c) g(n - 2) / (g - 2) ≥ e
d) (2g + 1)(n - 2) / (g - 2) ≥ e
e) NDA
Ideia original de: Rafael de Oliveira Werneck
quinta-feira, 10 de maio de 2012
MO405 - Questão para a prova oral
Número:
Enunciado: Dado as seguintes afirmações, assinale a incorreta.
a) Se um grafo plano G é bipartido, então seu grafo dual (G*) é euleriano.
b) Um grafo cordal possui uma ordenação simplicial.
c) O grafo dual de um grafo dual não é, necessariamente, o grafo original.
d) A soma dos comprimentos das faces é igual ao número de arestas.
e) NDA
Ideia original de: Rafael de Oliveira Werneck
Enunciado: Dado as seguintes afirmações, assinale a incorreta.
a) Se um grafo plano G é bipartido, então seu grafo dual (G*) é euleriano.
b) Um grafo cordal possui uma ordenação simplicial.
c) O grafo dual de um grafo dual não é, necessariamente, o grafo original.
d) A soma dos comprimentos das faces é igual ao número de arestas.
e) NDA
Ideia original de: Rafael de Oliveira Werneck
sexta-feira, 4 de maio de 2012
MO405 - Questão para a prova oral
Número:
Enunciado: Assinale a alternativa incorreta à respeito da construção de Mycielski.
a) O grafo a ser construído possui o dobro mais um vértices do que o grafo original.
b) Todos vértices criados formam um conjunto independente.
c) O número cromático do grafo original é menor do que o do grafo construído.
d) Os vértices duplicados do grafo original possuem a mesma coloração dos vértices originais.
e) NDA
Ideia original de: Rafael de Oliveira Werneck
Enunciado: Assinale a alternativa incorreta à respeito da construção de Mycielski.
a) O grafo a ser construído possui o dobro mais um vértices do que o grafo original.
b) Todos vértices criados formam um conjunto independente.
c) O número cromático do grafo original é menor do que o do grafo construído.
d) Os vértices duplicados do grafo original possuem a mesma coloração dos vértices originais.
e) NDA
Ideia original de: Rafael de Oliveira Werneck
quinta-feira, 26 de abril de 2012
MO405 - Questão para a prova oral
Número:
Enunciado: Assinale a alternativa incorreta em relação ao limite superior de coloração.
a) χ(G) ≤ Δ(G) + 1, pela coloração gulosa.
b) χ(G) ≤ 1 + max_i min{d_i, i - 1}, em que d_1 ≥ d_2 ≥ ... ≥ d_n é a sequencia de graus de G.
c) χ(G) ≤ Δ(G), se o grafo é completo.
d) χ(G) ≤ 1 + max_{H ⊆ G} δ(H), sendo H subgrafo k-crítico de G.
e) NDA
Ideia original de: Rafael de Oliveira Werneck
Enunciado: Assinale a alternativa incorreta em relação ao limite superior de coloração.
a) χ(G) ≤ Δ(G) + 1, pela coloração gulosa.
b) χ(G) ≤ 1 + max_i min{d_i, i - 1}, em que d_1 ≥ d_2 ≥ ... ≥ d_n é a sequencia de graus de G.
c) χ(G) ≤ Δ(G), se o grafo é completo.
d) χ(G) ≤ 1 + max_{H ⊆ G} δ(H), sendo H subgrafo k-crítico de G.
e) NDA
Ideia original de: Rafael de Oliveira Werneck
sexta-feira, 20 de abril de 2012
MO405 - Questão para a prova oral
Número:
Enunciado: Considerando a rede abaixo, assinale a alternativa que corresponda ao fluxo em cada aresta após a 3ª iteração do algoritmo de fluxo máximo.
OBS: A escolha do vértice a ser visitado é feita na ordem alfabética.
a)
b)
c)
d)
e) NDA
Ideia original de: Rafael de Oliveira Werneck
Enunciado: Considerando a rede abaixo, assinale a alternativa que corresponda ao fluxo em cada aresta após a 3ª iteração do algoritmo de fluxo máximo.
OBS: A escolha do vértice a ser visitado é feita na ordem alfabética.
a)
b)
c)
d)
e) NDA
Ideia original de: Rafael de Oliveira Werneck
sexta-feira, 13 de abril de 2012
MO405 - Questão para a prova oral
Número:
Enunciado: Dadas as seguintes afirmações, assinale a alternativa correta:
I - Um path Pn possui n-1 blocos.
II - O grafo K5 possui 2 1-factor e 1 2-factor.
III - Um path e uma estrela, com o mesmo número de vértices, possuem a mesma quantidade de blocos.
IV - Seja F um bond de um grafo, então |F| = δ(G).
a) As alternativas I e II estão corretas.
b) As alternativas I e III estão corretas.
c) As alternativas II e IV estão corretas.
d) As alternativas III e IV estão corretas.
e) NDA
Ideia original de: Rafael de Oliveira Werneck
sexta-feira, 30 de março de 2012
MO405 - Questão para a prova oral
Número:
Enunciado: Seja G um grafo, avalie as seguintes alternativas:
a) Para qualquer k > 0, todo G k-regular tem um matching perfeito.
b) Se n(G) for ímpar, G não possui um matching perfeito.
c) O tamanho de um matching de G é igual à metade do número de arestas de G
d) Seja G um n-path, o β(G) = n/2
e) NDA
Ideia original de: Rafael Werneck
sexta-feira, 23 de março de 2012
MO405 - Questão para a prova oral
Número:
Enunciado: Dada a seguinte sequência de Prüfer (11111), podemos afirmar:
b) O grafo é uma estrela.
c) O grafo é desconexo.
d) Pode-se gerar dois ou mais grafos à partir dessa sequência.
e) NDA
Enunciado: Dada a seguinte sequência de Prüfer (11111), podemos afirmar:
a) O grafo possui 8 vértices.
b) O grafo é uma estrela.
c) O grafo é desconexo.
d) Pode-se gerar dois ou mais grafos à partir dessa sequência.
e) NDA
sexta-feira, 16 de março de 2012
MO405 - Questão para a prova oral
Número:
Enunciado: Dado o dígrafo a seguir, qual é a alternativa correta?
b) O dígrafo é fracamente conectado.
c) Contém uma trilha euleriana.
d) É um dígrafo funcional.
e) NDA
Enunciado: Dado o dígrafo a seguir, qual é a alternativa correta?
a) O dígrafo possui um kernel.
b) O dígrafo é fracamente conectado.
c) Contém uma trilha euleriana.
d) É um dígrafo funcional.
e) NDA
quinta-feira, 1 de março de 2012
MO405 - Questão para a prova oral
Número:
Enunciado: Dado o seguinte grafo a seguir, qual é o seu número cromático?
a) 1
b) 2
c) 3
d) 4
e) NDA
Enunciado: Dado o seguinte grafo a seguir, qual é o seu número cromático?
a) 1
b) 2
c) 3
d) 4
e) NDA
Assinar:
Postagens (Atom)