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