domingo, 24 de junho de 2012

MO405 - Questão para a prova oral

Número: 125

Enunciado: Sobre a Multiplicação de Vértices de um grafo G por um vetor h de inteiros não negativos - onde gera-se o grafo G ○ h - é incorreto afirmar que:

a) Se G é bipartido, então o grafo G ○ h também é bipartido.

b) χ(G ○ h) = ω( G ○ h ) para todo grafo perfeito G e para todo h.

c) Se G é imperfeito, então G ○ h pode ser perfeito.

d) Mesmo G não sendo bipartido, G ○ h pode ser bipartido.

e) N.D.A.

Ideia original de: Leandro Teófilo

sábado, 23 de junho de 2012

MO405 - Questão para a prova oral

Número: 124

Enunciado: Suponha que um grafo G represente uma rede de fofocas da seguinte forma. Cada vértice é uma pessoa fofoqueira e cada aresta é uma via de comunicação bidirecional entre duas pessoas. Cada pessoa conhece um segredo que nenhuma outra sabe, e, quando duas pessoas se comunicam através de uma aresta, cada extremidade conta à outra tudo o que sabe. Seja f(G) o número mínimo de comunicações bidirecionais necessárias para que todas as pessoas de G saibam os segredos de todas as outras.

Com relação a f(C₅), qual das afirmações a seguir é FALSA ?

a) Se excluirmos um canal de comunicação, f aumenta, ou seja, f(C₅− e) > f(C₅).

b) É possível diminuir f apenas reorganizando melhor os canais de comunicação: existe um grafo G com n(G) = n(C₅), e(G) = e(C₅) e f(G) < f(C₅).

c) É possível diminuir f incluindo um novo canal de comunicação: f(C₅+ e) < f(G) para alguma aresta e.

d) Se uma nova pessoa for incluída ao grupo e possuir ao menos um canal de comunicação com as outras fofoqueiras, f aumentará: f(G) > f(C₅) para qualquer grafo conexo G de seis vértices.

e) NDA

MO405 - Questão para a prova oral

Número: 123

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: 122

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" é pelo menos 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

MO405 - Questão para a prova oral

Número: 121

Enunciado:
Seja G um grafo aleatório de 4 vértices onde cada aresta está presente com uma probabilidade p. Sabendo que a probabilidade de G ser um grafo completo é igual a 0,000064, qual é a probabilidade do grafo G ser um ciclo?

A. 0,000256

B. 0,001024

C. 0,004096

D. 0,016384

E. NDA

Ideia original de: Zhenlei Ji

sábado, 16 de junho de 2012

MO405 - Questão para a prova oral

Número: 120

Enunciado: Quantas das seguintes propriedades o grafo G abaixo possui: bipartido, euleriano, hamiltoniano, perfeito, planar, classe 1?

a) 3

b) 5

c) 4

d) 2

e) NDA

MO405 - Questão para a prova oral

Número: 119

Enunciado: Seja G um grafo conexo com polinômio cromático

k⁴ − 4k³ + 5k² − 2k.

Não podemos afirmar que:

a) G é perfeito.

b) G é planar e seu grafo dual é Euleriano.

c) G possui um matching perfeito.

d) G possui pelo menos um vértice de corte e uma aresta de corte.

e) NDA

MO405 - Questão para a prova oral

Número: 118

Enunciado: Qual das expressões abaixo é igual a χ'( G □ K₂ ) para todo grafo simples G ?

a) χ'(G)

b) χ'(G) + 1

c) χ'(G) + 2

d) Δ(G) + 1

e) N.D.A

Ideia original de: Gustavo Waku

MO405 - Questão para a prova oral

Número: 117

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: 116

Enunciado: Dados pesos nos elementos de um matróide M, considere o algoritmo (guloso) A a seguir: partindo do conjunto vazio, adicionar iterativamente o elemento de maior peso cuja adição ao conjunto independente selecionado gera um outro conjunto independente. Sobre o algoritmo A, marque a alternativa CORRETA:

a) Se M for um matróide cíclico (os circuitos são os ciclos de um grafo), o algoritmo A consiste no algoritmo de Kruskal.

b) Se M for um matróide cíclico (os circuitos são os ciclos de um grafo), o algoritmo A consiste no algoritmo de Dijkstra.
c) Se M for um matróide cíclico (os circuitos são os ciclos de um grafo), o algoritmo A consiste no algoritmo de Prim.

d) Nem sempre A gera um conjunto independente maximal.

e) N.D.A

Ideia original de: Thierry Pinheiro Moreira

MO405 - Questão para a prova oral

Número: 115

Enunciado: Determine o número de colorações próprias do grafo abaixo, utilizando 3 cores, dado que o polinômio cromático de C_n é:

χ (C_n; k) = (k - 1)ⁿ + (-1)ⁿ(k - 1)

a) 90

b) 100

c) 150

d) 180

e) NDA

Ideia original de: Jefferson Capovilla

MO405 - Questão para a prova oral

Número: 114

Enunciado: Em um sistema hereditário M sobre E, sendo I o conjunto de seus conjuntos independentes, B o conjunto das bases, e C o dos circuitos, qual das seguintes afirmações NÃO é equivalente à definição de rank (posto)?

a) rank é o número de elementos do maior subconjunto em B

b) rank é o número de elementos do maior subconjunto em E-C

c) rank é o número de elementos do maior subconjunto em I

d) rank é o número de elementos do maior subconjunto em I-C

e) N.D.A

Ideia original de: Marlon F. de Alcantara

MO405 - Questão para a prova oral

Número: 113

Enunciado: Quais das afirmativas abaixo estão INCORRETAS?

I - Todos os grafos perfeitos possuem ordenação perfeita
II - Nem todos os grafos fortemente perfeitos possuem ordenação perfeita
III - Todos os subgrafos induzidos de um grafo imperfeito minimal possuem ordenação perfeita

a) I e III

b) I e II

c) III

d) II

e) NDA

sexta-feira, 15 de junho de 2012

MO405 - Questão para a prova oral

Número: 112

Enunciado: Seja G uma árvore e H um ciclo. Das afirmações abaixo, quantas são FALSAS?

i) O produto cartesiano entre G e H é um grafo perfeito.
ii) Todo subgrafo próprio de H é perfeito.

iii) Se incluirmos uma aresta em G, o grafo obtido será imperfeito.
iv) Se incluirmos ⌈n(H)/2⌉ arestas em H, mantendo-o simples, o grafo obtido será perfeito.

a) 1

b) 2

c) 3

d) 4

e) NDA

MO405 - Questão para a prova oral

Número: 111

Enunciado: Dado o grafo a seguir, assinale a alternativa que corresponde à inversa da ordem dada pelo algoritmo MCS (Maximum Cardinality Search), considerando que os empates são decididos em favor do vértice que vem antes na 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: 110

Enunciado: Considere a aplicação do algoritmo MCS (Maximum Cardinality Search) em um grafo bipartido completo Km,n. Qual seria o rótulo do último vértice a ser numerado?

a) 0

b) max(m,n)

c) min(m,n)

d) m + n - 1

e) N.D.A

Ideia original de: Marlon F. de Alcantara

MO405 - Questão para a prova oral

Número: 109

Enunciado: Sobre o algoritmo Maximum Cardinality Search(MCS), marque a alternativa CORRETA.

a) Encontra uma ordem de eliminação simplicial em qualquer grafo.

b) Pode dar um mesmo número a mais de um vértice. Isto acontece em situações em que a ordem de remoção dos vértices de mesmo número não faz diferença.

c) Opera de forma gulosa, buscando vértices com mais vizinhos visitados.

d) A ordem de eliminação simplicial é a ordem em que os vértices são numerados pleo algoritmo.

e) N.D.A

Ideia original de: Thierry Pinheiro Moreira

MO405 - Questão para a prova oral

Número: 108

Enunciado:

Considerando o grafo G acima como entrada do algoritmo MCS (Maximum Cardinality Search), qual seria uma possível ordem de visita dos vértices?

A. 271643589
B. 635412879
C. 872416359
D. 345162789
E. NDA

Ideia original de: Zhenlei Ji

MO405 - Questão para a prova oral

Número: 107

Qual das seguintes ordens NÃO pode ser obtida aplicando-se o algoritmo de busca de maior cardinalidade (MCS) no grafo abaixo, dado que a busca inicia-se pelo vértice b?

A) b, a, c, e, d, f, g, h

B) b, e, c, d, a, f, g, h

C) b, c, e, f, d, a, h, g

D) b, d, e, a, c, f, h, g

E) NDA

Ideia original de: Jefferson Capovilla

domingo, 10 de junho de 2012

MO405 - Questão para a prova oral

Número: 106

Enunciado: Sendo G um grafo cúbico que possui um 4-fluxo positivo, é incorreto afirmar que:

a) G é 3-aresta-colorível
b) G não possui um Cycle Double Cover.
c) G não é o grafo de Petersen.
d) G é formado pela união de dois grafos pares.
e) N.D.A.

Ideia original de: Leandro Teófilo

MO405 - Questão para a prova oral

Número: 105

Enunciado: Qual o menor k estritamente positivo tal que o grafo abaixo é k-fluível?

a) 1

b) 2

c) 3

d) 4

e) N.D.A

Ideia original de: Marlon F. de Alcantara

MO405 - Questão para a prova oral

Número: 104

Enunciado: Quais dos grafos a seguir são hamiltonianos?

a) Apenas I

b) Apenas II

c) Apenas I e II

d) Apenas II e III

e) N.D.A

Ideia original de: Gustavo Waku

sexta-feira, 8 de junho de 2012

MO405 - Questão para a prova oral

Número: 103

Enunciado: Assinale a alternativa incorreta:

A) Existem grafos G hamiltonianos tal que seus complementos também sejam hamiltonianos.

B) Se um grafo G possui um caminho hamiltoniano, então G ∨ K₁ possui um ciclo hamiltoniano.

C) Se um grafo simples G possui mais de 3 vértices e o grau mínimo é maior ou igual a n(G)/2, então G contem um ciclo hamiltoniano.

D) Se um grafo G possui um caminho hamiltoniano e é 2-conexo, então G possui um ciclo hamiltoniano.

E) NDA

Ideia original de: Diogo Ditzel Kropiwiec

MO405 - Questão para a prova oral

Número: 102

Enunciado: Considere o grafo G a seguir:

Analise as afirmações abaixo e assinale a alternativa correta:

I - O grafo G é hamiltoniano;
II - χ(G)=3;
III - χ'(G)=3;
IV- O grafo dual de G possui 10 faces

A. Somente II e III
B. Somente IV
C. II, III, IV
D. I, II e III
E. NDA

Ideia original de: Zhenlei Ji

MO405 - Questão para a prova oral

Número: 101

Enunciado: Assinale a alternativa incorreta:

A) Todo grafo k-regular com n vértices, onde k > n/2 é um grafo hamiltoniano.

B) Os grafos completos com número ímpar de vértices são hamiltonianos.

C) Se A é um ciclo ímpar e B é um ciclo par temos χ'(A) ≠ χ'(B).

D) O índice cromático de um grafo é sempre maior ou igual a seu número cromático.

E) NDA

Ideia original de: Luciano Antonio Digiampietri

MO405 - Questão para a prova oral

Número: 100

Enunciado: Qual das afirmativas está correta:

A. O fecho (grafo closure) de um ciclo G é o próprio G.

B. Se G é um grafo simples, conexo e com uma aresta de corte e, então, G possui um caminho hamiltoniano se, e somente se, as componente de G - e possuírem um caminho hamiltoniano.

C. Se G não possui um ciclo hamiltoniano, então o grafo linha de G também não possui um ciclo hamiltoniano.

D. K₅ é o menor grafo completo que possui dois ciclos hamiltonianos disjuntos nas arestas.

E. NDA.

Ideia original de: Lucas

MO405 - Questão para a prova oral

Número: 099

Enunciado: Identifique a alternativa INCORRETA:

A) Todo grafo cúbico hamiltoniano possui emparelhamento perfeito.

B) Todo grafo cúbico hamiltoniano é classe 1, ou seja, tem 3-coloração de arestas.

C) Todo cubo Q_k, para k >=2, é hamiltoniano.

D) O grafo de Petersen é classe 1.

E) NDA

Ideia original de: Cândida Nunes da Silva

MO405 - Questão para a prova oral

Número: 098

Enunciado: Identifique a alternativa CORRETA com base nas afirmações a seguir:

I - Existe triangulação cúbica (3-regular).
II - Todo grafo cúbico planar 2-aresta-conexo possui 4-coloração própria de faces.
III - Existe snark planar.

A) I e II são verdadeiras.

B) Apenas II é verdadeira.

C) Apenas I é verdadeira.

D) II e III são verdadeiras.

E) NDA

Ideia original de: Cândida Nunes da Silva

quinta-feira, 31 de maio de 2012

MO405 - Questão para a prova oral

Número: 097

Enunciado: As figuras abaixo correspondem a colorações das faces de C₃ □ C₃ imerso num toro (identificando a borda esquerda com a direita, e a borda superior com a inferior). Qual delas representa uma coloração própria?

e) NDA

Ideia original de: Edgard H. Santos

MO405 - Questão para a prova oral

Número: 096

Enunciado: Dado o grafo G abaixo, o que podemos afirmar sobre o L(G)?

a) L(G) é Hamiltoniano e χ’(L(G))= 4

b) L(G) é planar, mas não é Hamiltoniano

c) L(G) é classe 1, mas não é planar

d) L(G) é Hamiltoniano, mas não é classe 1

e) NDA

MO405 - Questão para a prova oral

Número: 095

Enunciado: Sabendo que G é um grafo simples que possui como fecho (closure) o grafo K₅, analise as afirmações abaixo e assinale a alternativa correta.

I - G é Hamiltoniano.
II - A conectividade de G é maior ou igual ao seu número de independência, ou seja: κ(G) ≥ α(G).
III - O grau mínimo de G é maior ou igual ao seu número de vértices dividido por 2, ou seja: δ(G) ≥ n(G)/2.
IV - G possui um ciclo gerador de tamanho 6.

a) Apenas a afirmação I está correta.

b) Apenas a afirmação IV está incorreta.

c) As afirmações II e IV estão incorretas.

d) Três destas afirmações estão corretas.

e) N.D.A.

Ideia original de: Leandro Teófilo

MO405 - Questão para a prova oral

Número: 094

Enunciado: Sobre o grafo abaixo:

assinale a alternativa INCORRETA :

a) Δ(G) = χ'(G)

b) χ'(G) = χ( L(G) )

c) κ(G) ≥ α(G) , e portanto possui um ciclo hamiltoniano.

d) χ(G) = ω(G)

e) N.D.A

Ideia original de: Gustavo Waku

sábado, 26 de maio de 2012

MO405 - Questão para a prova oral

Número: 093

Enunciado: Qual das afirmações abaixo é incorreta sobre o produto cartesiano Cn □ Cm dos grafos Cn e Cm, para n, m ≥ 3?

a) Cn □ Cm pode ser imerso na esfera, sem cruzamentos.

b) se n for par ou m for par, χ'(Cn □ Cm) = 4

c) se k ≤ n, então Ck □ Cm é um menor de Cn □ Cm

d) se ambos n e m forem ímpares, χ'(Cn □ Cm) = 5

e) NDA

Ideia original de: Rafael de Oliveira Werneck

domingo, 20 de maio de 2012

MO405 - Questão para a prova oral

Número: 092

Enunciado: Seja G um grafo simples 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: 091

Enunciado: O crossing number do grafo de Petersen, desenhado abaixo, é igual a:

a) 1

b) 2

c) 3

d) 4

e) N.D.A

Ideia original de: Gustavo Waku

MO405 - Questão para a prova oral

Número: 090

Enunciado: Considere um grafo simples G que possui uma imersão(embedding) em uma esfera sem cruzamento de arestas. Sobre este grafo é INCORRETO afirmar que:

a) G possui espessura (thickness) estritamente maior que 1.

b) G possui uma imersão (embedding) planar.

c) G pode ser colorido com 5 cores.

d) G não possui uma subdivisão do K₅ nem do K_3,3

e) N.D.A

Ideia original de: Marlon F. de Alcantara

MO405 - Questão para a prova oral

Número: 089

Enunciado: Sobre imersões planares, podemos afirmar que:

A. Todo grafo planar possui uma imersão cujas faces são polígonos convexos.

B. Se H é um menor de G, então G contém uma subdivisão de H.

C. Se H é um subgrafo de G, então ν(G) ≤ ν(H).

D. O crossing number do K_3,5 é 4.

E. NDA.

Ideia original de: Lucas

MO405 - Questão para a prova oral

Número: 088

Enunciado: Identifique a alternativa CORRETA:

A) O gênus de todo grafo imersível no toro é 1.

B) Todo grafo 4-colorável é imersível no plano.

C) A espessura (thickness) de um grafo é sempre menor ou igual ao seu número de cruzamento mais um (ni(G)+1).

D) O grafo de Petersen contém uma subdivisão do K_5.

E) NDA

Autor(a): Cândida Nunes da Silva

MO405 - Questão para a prova oral

Número: 087

Enunciado: Qual o número de faces do grafo G gerado pelo produto cartesiano entre P₂ e K_1,100?

A) G não é planar

B) 101 faces

C) 198 faces

D) 202 faces

E) NDA

Ideia original de: Vinicius José Fortuna

sábado, 12 de maio de 2012

MO405 - Questão para a prova oral

Número: 086

Enunciado: Sobre as afirmações a seguir:

I - Se G* é o grafo dual do grafo plano G, pode-se dizer que G* e G têm o mesmo número de arestas e vértices;
II - Os grafos duais das imersões no plano de um grafo planar G têm o mesmo número de arestas e vértices;
III - Se G é bipartido completo e δ(G) ≤ 2, então G é planar;

podemos dizer que:

a) Apenas I é verdadeira.
b) Apenas I e II são verdadeiras.
c) Apenas II é verdadeira.
d) Apenas III é verdadeira.
e) NDA

Ideia original de: Vitor Afonso

MO405 - Questão para a prova oral

Número: 085

Enunciado: De quantas maneiras podemos colorir as regiões A, B, C e D abaixo utilizando 4 cores distintas? Nota: regiões que compartilham uma fronteira devem ter cores distintas.

a) 84

b) 48

c) 96

d) 64

e) NDA

Ideia original de : Junior Fabian

MO405 - Questão para a prova oral

Número: 084

Enunciado: Considere o grafo abaixo:

Os números de colorações próprias, usando 3 e 4 cores, respectivamente, são:

a) 15, 240

b) 15, 160

c) 30, 120

d) 30, 240

e) N.D.A.

Ideia original de: Gustavo Waku

MO405 - Questão para a prova oral

Número: 083

Enunciado: Qual é o polinômio cromático do grafo abaixo?

a) k²(k-1)⁵(k-2)

b) k(k-1)⁴ (k-2)³

c) k²(k-1)³(k-2)³

d) k(k-1)⁵(k-2)²

e) NDA

Ideia original de: Juliana Medeiros Destro

MO405 - Questão para a prova oral

Número: 082

Enunciado: A respeito de grafos cordais, qual das alternativas a seguir é correta?

a) Todo grafo sem ciclos é cordal.

b) Todo grafo planar é cordal.

c) Todo grafo bipartido completo é cordal.

d) O grafo de Petersen é cordal.

e) NDA

MO405 - Questão para a prova oral

Número: 081

Enunciado: Considere dois grafos G e H, onde H=G-e (H é obtido pela remoção de uma aresta e de G). Quantas das afirmações abaixo são falsas?

(I) Se G é um K₅,então H é planar.

(II) Se G é perfeito, então H é perfeito.
(III) Se G é planar, então H é planar e o dual de H é G.e (contração da aresta e em G).

a) 3

b) 2

c) 1

d) 0

e) NDA

MO405 - Questão para a prova oral

Número: 080

Enunciado: Dado as seguintes afirmações, assinale a incorreta.

a) A soma dos comprimentos das faces de um grafo plano G é igual ao dobro do número de arestas de G.

b) O grafo dual do grafo dual de um grafo plano G não é, necessariamente, isomorfo a G.

c) Se um grafo plano G é bipartido, então seu grafo dual (G* é euleriano.

d) Um grafo cordal possui uma ordenação simplicial.

e) NDA

Ideia original de: Rafael de Oliveira Werneck

MO405 - Questão para a prova oral

Número: 079

Enunciado: Determine a soma dos comprimentos de todas as faces do grafo plano abaixo:

a) 20

b) 21

c) 22

d) 23

e) NDA

Ideia original de: Jefferson Capovilla

domingo, 6 de maio de 2012

MO405 - Questão para a prova oral

Número: 078

Enunciado: Considere as afirmações a seguir, referentes a coloração de vértices.

I) Todo grafo estrela é crítico.

II) Todo grafo Kn é n-crítico e, portanto, é (n-1)-aresta-conexo.

III) O grafo Kx ∨ Cy, com x>0 e y>0, é crítico.

Podemos dizer que:

a) Apenas I é verdadeira.
b) Apenas I e II são verdadeiras.
c) Apenas II é verdadeira.
d) Apenas II e III são verdadeiras.
e) NDA

Ideia original de: Vitor Afonso

MO405 - Questão para a prova oral

Número: 077

Enunciado: De acordo com as afirmações abaixo, e lembrando que o produto cartesiano G □ H de G e H é definido como:

V(G □ H) = V(G) × V(H), e

E(G □ H) = {(u,v)(u',v') | (u ∈ V(G) e v'v ∈ E(H)) ou (uu' ∈ E(G) e v ∈ V(H))},

assinale a alternativa correta:

I. O produto cartesiano de grafos bipartidos é um grafo bipartido;
II. Se o produto cartesiano de G e Km tem um conjunto independente de tamanho k, então G tem um subgrafo induzido de ordem k com número cromático no máximo m;
III. Nenhum ciclo pode ser representado por um grafo de intervalos.

a) Somente I e II estão corretas;

b) Somente I e III estão corretas;

c) Somente I está correta;

d) Todas estão corretas;

e) NDA.

Ideia original de: Rafael L. Gomes