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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

MO405 - Questão para a prova oral

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

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

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

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

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

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