MO405 - Questão para a prova oral

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

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

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

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

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

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

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