MO405 - Questão para a prova oral

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

MO405 - Questão para a prova oral

MO405 - Questão para a prova oral


Número:

Enunciado: Sobre a Multiplicação de Vértices de um grafo G por um vetor h de inteiros não negativos - onde se gera o grafo G ○ h -  é incorreto afirmar que: 

a) Se G é bipartido, então o grafo G ○ h também é bipartido.

b) Se G é imperfeito, então G ○ h nunca será perfeito.

c) χ(G ○ h) = ω( G  ○ h ) para todo grafo perfeito G e qualquer h.
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

MO405 - Questão para a prova oral


Número:

Enunciado: Um grafo G é perfeito se χ(H) = ω(H) para todo subgrafo induzido H de G. Sabendo disso,  analise as afirmações abaixo e assinale a alternativa correta.

I   - Grafos cordais são perfeitos.

II - Grafos bipartidos são perfeitos; o que não é válido para seus respectivos grafos linha.

III  - Grafos de intervalos são perfeitos.

IV  - Todo grafo perfeito possui uma imersão planar.

a) Apenas a afirmação IV está incorreta.
b) As afirmações I, II e IV estão corretas.
c) As afirmações II e IV estão incorretas.
d) Apenas a afirmação I está correta.
e) N.D.A.


Ideia original de: Leandro Teófilo

Questão extra

MO405 - Questão para a prova oral


Número:

Enunciado: Sendo G um grafo cúbico que possui um nowhere-zero 4-fluxo, é 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


Número:

Enunciado: Sendo G o grafo abaixo, analise as afirmações que se seguem e assinale a alternativa correta.

I - G é Hamiltoniano.
II - G é um snark.
III - G possui coloração de Tait.
IV - G não possui um corte não-trivial de 3 arestas.



a) Apenas a afirmação I está correta.
b) Apenas a afirmação IV está incorreta.
c) As afirmações II e IV estão corretas.
d) Apenas a afirmação II está correta.
e) N.D.A.


Ideia original de: Leandro Teófilo

MO405 - Questão para a prova oral (Extra)

Número:

Enunciado: Sabendo que G é um grafo simples que possui como fechamento (closure) o grafo K₅, analise as afirmações abaixo e assinale a alternativa correta.

  

I - G é Hamiltoniano.
II - A conectividade de G é maior ou igual ao seu número de independência, ou seja: κ(G) ≥ α(G).
III - O grau mínimo de G é maior ou igual ao seu número de vértices dividido por 2, ou seja: δ(G) ≥ n(G)/2.
IV - G possui um ciclo gerador de tamanho 6.

a) Apenas a afirmação I está correta.
b) Apenas a afirmação IV está incorreta.
c) As afirmações II e IV estão incorretas.
d) Todas as afirmações estão corretas.
e) N.D.A.


Ideia original de: Leandro Teófilo

MO405 - Questão para a prova oral

Número:

Enunciado: Sendo G o grafo abaixo, assinale a opção incorreta:

a)  χ'(G) =  4 _.

b) O número cromático do grafo linha de G, denotado χ(L(G)) é igual a ∆(G).
c) O grafo é Classe 1.
d) O grafo possui um Ciclo Hamiltoniano.
e) N.D.A


Ideia original de: Leandro Teófilo