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

MO405 - Questão para a prova oral

Número:

Enunciado: Dado um grafo G com um ciclo C. A aresta e pertence ao ciclo C. Com base nestas informações, o que podemos afirmar:

a) G é conexo

b) O ciclo C é um subgrafo induzido

c) A aresta e não é cut-edge

d) Todos os componentes de G são triviais

e) NDA

Ideia original de: Juliana M Destro

MO405 - Questão para a prova oral

Número:

Enunciado: Dado um grafo completo G, qual o número de arestas de G?


























Idéia original de: Juliana M Destro