MO405 - Questão para a prova oral

Número:

Enunciado: Com base no grafo G abaixo, assinale a alternativa INCORRETA:

a) G-a é bipartido

b) G é hamiltoniano

c) G é euleriano

d) χ(G) = 3

e) NDA

MO405 - Questão para a prova oral

Número:

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) II

c) III

d) I e II

e) NDA

MO405 - Questão para a prova oral

Número: 

Enunciado: Quais das afirmações abaixo sobre fluxos são verdadeiras?

I - O grafo de Petersen possui um nowhere-zero 3-fluxo
II - O grafo de Petersen possui um nowhere-zero 2-fluxo
III - Todos os grafos cúbicos possuem nowhere-zero 3-fluxo

a) I

b) I e III

c) II

d) III

e) NDA

MO405 - Questão para a prova oral

Número:

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

a) L(G) possui 6 vértices, 9 arestas e χ’(L(G))= 4

b) L(G) possui 6 vértices, 9 arestas e χ’(L(G))= 3

c) L(G) possui 6 vértices, 10 arestas e χ’(L(G))= 4

d) L(G) possui 6 vértices, 10 arestas e χ’(L(G))= 5

e) NDA

MO405 - Questão para a prova oral

Número:

Enunciado: Qual a polinomial cromática 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:

Enunciado: Em relação ao grafo de Turán T(n,r), o que é correto afirmar:

a) n/ χ < α(T(n,r))

b) e(T(n,r)) = n( χ-n/ χ)/2

c) r = (n/ χ)/2

d) e(T(n,r)) = n( n-n/ χ)/2

e) NDA

Ideia original de: Juliana M Destro

MO405 - Questão para a prova oral

Número:

Enunciado: Marque a alternativa correta considerando um grafo bipartido Km,n com bipartição X,Y:

a) o grafo tem um cut vertex em X se e somente se m < n

b) Km,n é n-conectado se e somente se n < δ(Km,n)

c) κ(Km,n) < κ’(Km,n)

d) Km,n é n-conectado se e somente se n < m

e) NDA


Ideia original de: Juliana M Destro

MO405 - Questão para a prova oral

Número:

Enunciado: Dado o grafo G abaixo, o que podemos afirmar?


a) α' (G)+β(G)=n(G)

b) α(G)=β(G)

c) β(G)≤α(G)

d) α' (G)+β' (G)≤n(G)

e) NDA

Ideia original de: Juliana M Destro

MO405 - Questão para a prova oral

Número:

Enunciado: Determine a sequência de Prüfer do grafo abaixo:



a) (1,2,3,4,5,7)

b) (3,3,4,5,4,6)

c) (3,3,4,7,4,6)

d) (3,4,5,4,6,6)

e) NDA

Ideia original de: Juliana M Destro