Questão extra 3 - 27/04

MO405 - Questão para a prova oral

Número:

Enunciado: Sobre o produto cartesiano de grafos, é incorreto afirmar que:

a)  A operação de produto cartesiano é simétrica, ou seja G□H é isomorfo a H□G
b)  χ(G□H) = max (χ(G),χ(H) )
c)  O conjunto de vértices de G□H é o produto cartesiano dos conjuntos de vértices de G e H

d)  K2□K₂ é um ciclo de tamanho 4.
e) N.D.A

Ideia original de: Leandro Teófilo

Questão extra 2 - 27/04

MO405 - Questão para a prova oral

Número:

Enunciado: Sobre coloração de vértices, assinale a alternativa incorreta:

a)  O grafo de Petersen não admite 3-coloração.
b)  Seja G um grafo com caminho máximo P, então χ(G) ≤ n(P).
c)  Para todo grafo G,  χ(G) < n(G) - δ(G)

d)  Para todo grafo G bicolorível, χ(G) > ω(G).
e) N.D.A

Ideia original de: Leandro Teófilo

Questão extra - 27/04

MO405 - Questão para a prova oral

Número:

Enunciado: Sobre as afirmações abaixo, assinale a alternativa correta:

I   -  Uma k-coloração própria de um grafo k-cromático é uma coloração ótima.
II  -  Um grafo é 2-colorível apenas se o grafo for bipartido.
III -  Para todo grafo G, χ(G) ≥ ω(G) e χ(G) ≥ α(G)/n(G)
IV - Para todo grafo G, χ(G) - 1 ≤ ∆(G)


a)  Apenas as alternativasI e II estão corretas
b)  Apenas a alternativa II está incorreta
c)  Apenas as alternativas I, II e III estão corretas
d)  Apenas a alternativa III está incorreta
e) N.D.A

Ideia original de: Leandro Teófilo

Questão dia 27/04

MO405 - Questão para a prova oral

Número:

Enunciado: Sobre coloração de vértices, assinale a alternativa incorreta:

a) Uma k-coloração é própria se vértices adjacentes têm diferentes cores.
b) Um grafo é k-colorível se sua k-coloração é própria.
c)  Um grafo é k-cromático se seu número cromático é igual a k
d)  O clique number de um grafo G é o clique de maior tamanho em G.
e) N.D.A

Ideia original de: Leandro Teófilo

Questão dia 13/04

MO405 - Questão para a prova oral

Número:

Enunciado: Sendo G o grafo abaixo, selecione a opção que indica quais das componentes  selecionadas (1 a 5) não representam um bloco?

a) 1 e 5
b) 2 e 3 
c) 2 e 5
d) 4 e 5
e) N.D.A


Ideia original de: Leandro Teófilo

Questão dia 06/04

MO405 - Questão para a prova oral

Número:

Enunciado: Dentre as alternativas abaixo, assinale a incorreta:

a) O menor grafo com um matching maximal que não é um matching máximo é P4.
b) Um matching perfeito pode ser representado por uma matriz que só possui um 1 em cada coluna, bem como em cada linha.
c) O tamanho de um matching é calculado através do número de vértices do grafo.
d) Dado um grafo G e M um matching de G. Caso consigamos adicionar uma aresta a  a M de forma que M+a' continue sendo um matching de G, então concluímos que M não era um matching maximal.
e) N.D.A

Ideia original de: Leandro Teófilo